资源描述：
《用映射的观点分析排列组合问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第19卷第2期三明高等专科学校学报2002年6月Vol.19No.2JOURNALOFSANMINGCOLLEGEJun.2002用映射的观点分析排列组合问题张金良(福建省建阳师范学校,福建建阳354200)[摘要]本文用映射的观点对排列组合问题进行了分析与思考,论述了单射个数与满射个数的计算公式及其在一些排列组合问题中的应用。[关键词]单射;满射;排列组合[中图分类号]O157.1[文献标识码]A[文章编号]1671-1343(2002)02-0065-04排列与组合是组合数学中的基础内容,是中学数学课程中的一个难点。处理排列组合问题要掌握排列与组合的基本概
2、念,加法、乘法原理以及分类、分步的思想方法。除此之外,如果能够用映射的观点对排列组合问题进行分析与思考,那么对排列组合问题将会有实质性的理解,有助于释疑排难,找到正确的解题途径。1映射的有关概念(1)单射:设f是从集合A到集合B的一个映射,若任给x1,x2∈A,只要x1≠x2,就有f(x1)≠f(x2),那么称f是从集合A到集合B的一个单射。(2)满射:设f是从集合A到集合B的一个映射,如果f(A)=B,那么称f是从集合A到集合B上的一个满射。2单射个数与满射个数的计算公式及其应用在日常生活中,我们常把若干个事物的集合A的成员放在集合B中的一个位置上,A成员在
3、B的位置上的特殊分布就是一个排列或组合。例1有四本书a、b、c、d,我们要将其中的三本分别放在三个抽屉内。第一个抽屉放b,第二个抽屉放c,第三个抽屉放a,这种放书方法实质上是从四本书中取三本放在三个抽屉内的一种排列(b,c,a)。如果从映射的角度看,那么这种放书方法构成了从抽屉集合A={1,2,3}到书本集合B={a,b,c,d}的一个映射f:f(1)=bf(2)=cf(3)=aA:即:B:一般地,设n个事物的集合为Nn={b1,b2,b3,…,bn},前m个自然数的集合为Nm={1,2,[收稿日期]2002-01-09[作者简介]张金良(1969-),男,福
4、建寿宁人,福建省建阳师范学校讲师、硕士。653,…,m}(m≤n)。从n个事物的集合Nn中选m个事物的排列就是一个单射f:Nm→Nn。选出的第一个事物为f(1),第二个事物为f(2),…,第m个事物为f(m)。因此,单射的个数即为排列数个数。m命题1从n个相异元数中取m个元素的无重复的排列数Pn等于从Nm到Nn(m≤n)内单射的个数。即:m#I(Nm,Nn)=Pn其中I(Nm,Nn)表示所有从Nm到Nn的单射,#I(Nm,Nn)表示从Nm到Nn的单射的个数。证明方法1:从n个相异元素b1、b2、…、bn中取m个无重复的排列(bi1,bi2,…,bim)的集合,
5、与从Nm={1,2,3,…,m}到Nn={b1,b2,b3,…,bn}内单射的集合可以建立如下的一一对应关系:fi(1)=bi1(bi1,bi2,…,bim)fi:……fi(m)=bimm其中bij(1≤j≤m)是Nn中的m个元素,且互不相同。所以排列数Pn等于从Nm到Nn(m≤n)内单射的个数。即:m#I(Nm,Nn)=Pn方法2:(用数学归纳法)(1)当m=0时,N0=,规定#I(N0,Nn)=1当m=1时,N1={1},Nn={b1,b2,b3,…,bn},则f:N1→Nn有n个单射,所以,#I(N1,1Nn)=n=Pnm-1n!(2)假设命题对m-1成
6、立,即:#I(Nm-1,Nn)=Pn=,现考虑m时的情(n-m+1)!况:记Nm={1,2,3,…,m-1}∪{m}=Nm-1∪N1Nn={b1,b2,…,bm-1}∪{bm,…,bn}=Nm-1∪Nn-(m-1)NmNn求Nm到Nn单射的个数#I(Nm,Nn)分二步完成:第一步求出#I(Nm-1,Nn)。第二步求出第m个元素集合N1单射的个数,即N1到Nn-(m-1)单射个数,此时由(1)知:#I(N1,Nn-(m-1))=n-(m-1)。66∴#I(Nm,Nn)=#I(Nm-1,Nn)·#I(N1,Nn-(m-1)m-1=Pn·[n-(m-1)]n!n!m
7、=·(n-m+1)==Pn(n-m+1)!(n-m)!由(1)(2)可知命题成立。例2:在一块并排10垄的田地中,选择2垄分别种A、B两种作物,每种作物种1垄。为有利于作物生长,要求A、B两种作物的间隔不少于6垄,则不同的选垄共有多少种?(1999年全国高考题)解:根据题意,A、B两种作物间隔不少于6垄。也就是说,在10垄田地中有4垄可以任意种植。令Nm={A,B},Nn={a,b,c,d},则不同的选垄种数等于从Nm到Nn的单射个数:#Im2(Nm,Nn)=Pn=P4=12种。例3:用0到9这十个数字,可以组成多少个没有重复数字的三位数?解:令Nm={a,b
8、,c},Nn={0,1,2,…,9},
