用映射的观点分析排列组合问题

第19卷第2期Vol .19No .2 三明高等专科学校学报JOURNAL OF SANM ING COLLEGE 2002年6月Jun .2002[收稿日期]2002-01-09[作者简介]张金良(1969-),男,福建寿宁人,福建省建阳师范学校讲师、硕士。

用映射的观点分析排列组合问题张金良(福建省建阳师范学校,福建建阳　354200)[摘要]本文用映射的观点对排列组合问题进行了分析与思考,论述了单射个数与满射个数的计算公式及其在一些排列组合问题中的应用。

[关键词]单射;满射;排列组合[中图分类号]O157.1 [文献标识码]A [文章编号]1671-1343(2002)02-0065-04排列与组合是组合数学中的基础内容,是中学数学课程中的一个难点。

处理排列组合问题要掌握排列与组合的基本概念,加法、乘法原理以及分类、分步的思想方法。

除此之外,如果能够用映射的观点对排列组合问题进行分析与思考,那么对排列组合问题将会有实质性的理解,有助于释疑排难,找到正确的解题途径。

1　映射的有关概念(1)单射:设f 是从集合A 到集合B 的一个映射,若任给x 1,x 2∈A ,只要x 1≠x 2,就有f (x 1)≠f (x 2),那么称f 是从集合A 到集合B 的一个单射。

(2)满射:设f 是从集合A 到集合B 的一个映射,如果f (A )=B ,那么称f 是从集合A 到集合B 上的一个满射。

2　单射个数与满射个数的计算公式及其应用在日常生活中,我们常把若干个事物的集合A 的成员放在集合B 中的一个位置上,A 成员在B 的位置上的特殊分布就是一个排列或组合。

例1　有四本书a 、b 、c 、d ,我们要将其中的三本分别放在三个抽屉内。

第一个抽屉放b ,第二个抽屉放c ,第三个抽屉放a ,这种放书方法实质上是从四本书中取三本放在三个抽屉内的一种排列(b ,c ,a )。

如果从映射的角度看,那么这种放书方法构成了从抽屉集合A ={1,2,3}到书本集合B ={a ,b ,c ,d }的一个映射f :f (1)=b f (2)=c f (3)=a即:A :B:一般地,设n 个事物的集合为N n ={b 1,b 2,b 3,…,b n },前m 个自然数的集合为N m ={1,2,3,…,m }(m ≤n )。

从n 个事物的集合N n 中选m 个事物的排列就是一个单射f :N m →N n 。

选出的第一个事物为f (1),第二个事物为f (2),…,第m 个事物为f (m )。

因此,单射的个数即为排列数个数。

命题1　从n 个相异元数中取m 个元素的无重复的排列数P n m 等于从N m 到N n (m ≤n )内单射的个数。

即:#I (N m ,N n )=P n m其中I (N m ,N n )表示所有从N m 到N n 的单射,#I (N m ,N n )表示从N m 到N n 的单射的个数。

证明　方法1:从n 个相异元素b 1、b 2、…、b n 中取m 个无重复的排列(b i1,b i2,…,b im )的集合,与从N m ={1,2,3,…,m }到N n ={b 1,b 2,b 3,…,b n }内单射的集合可以建立如下的一一对应关系:(b i 1,b i2,…,b i m ) f i :f i (1)=b i1……f i (m )=b im其中b ij (1≤j ≤m )是N n 中的m 个元素,且互不相同。

所以排列数P n m 等于从N m 到N n (m ≤n )内单射的个数。

即:#I (N m ,N n )=P n m方法2:(用数学归纳法)(1)当m =0时,N 0= ,规定#I (N 0,N n )=1当m =1时,N1={1},N n ={b 1,b 2,b 3,…,b n },则f :N 1→N n 有n 个单射,所以,#I (N 1,N n )=n =P n 1(2)假设命题对m -1成立,即:#I (N m -1,N n )=P n m -1=n !(n -m +1)!,现考虑m 时的情况: N m N n 记N m ={1,2,3,…,m -1}∪{m }=N m -1∪N 1N n ={b 1,b 2,…,b m -1}∪{b m ,…,b n }=N m -1∪N n -(m -1)求N m 到N n 单射的个数#I (N m ,N n )分二步完成:第一步求出#I (N m -1,N n )。

第二步求出第m 个元素集合N 1单射的个数,即N 1到N n -(m -1)单射个数,此时由(1)知:#I (N 1,N n -(m -1))=n -(m -1)。

∴#I (N m ,N n )=#I (N m -1,N n )·#I (N 1,N n -(m -1)=P n m -1·[n -(m -1)]=n !(n -m +1)!·(n -m +1)=n !(n -m )!=P n m 由(1)(2)可知命题成立。

例2:在一块并排10垄的田地中,选择2垄分别种A 、B 两种作物,每种作物种1垄。

为有利于作物生长,要求A 、B 两种作物的间隔不少于6垄,则不同的选垄共有多少种?(1999年全国高考题)解:根据题意,A 、B 两种作物间隔不少于6垄。

也就是说,在10垄田地中有4垄可以任意种植。

令N m ={A ,B },N n ={a ,b ,c ,d },则不同的选垄种数等于从N m 到N n 的单射个数:#I (N m ,N n )=P n m =P 42=12种。

例3:用0到9这十个数字,可以组成多少个没有重复数字的三位数?解:令N m ={a ,b ,c },N n ={0,1,2,…,9},则所求相当于求f :N m →N n 的单射个数(其中f (a )表示百位上的数,故f (a )≠0)。

而当f (a )=0时f :N m →N n 的单射个数,相当于g :N ′m ={b ,c }→N ′n ={1,2,…,9}的单射个数。

故所求为:#I (N m ,N n )-#I (N ′m ,N ′n )=P 103-P 92=648命题2:设f :N n →N m ,其中0≤m ≤n ,并记函数集S (N n ,N m )={f f 是N n →N m 的满射},此函数集的元素个数记作:#S (N n ,N m )=e n ,m则:(1)若n <m ,满射不存在,故e n ,m =0(2)若n =m ,则f 是双射,故e n ,m =P n n =n !(3)若m =0≤n ,仅有一种满射,故e n ,0=1若m =1≤n ,也仅有一种满射,故e n ,l =1(4)若n >m >1,则e n ,m =m (e n -1,m +e n -1,m -1)现证明第(4)种情况,并把f 限制在N n -1上进行讨论。

由于原有的所有满射必然分为两部分:一部分是舍弃掉N n 中的一个元素后,仍是满射;另一部分则舍弃掉N n 中的一个元素后,不是满射。

这样,全体满射的个数即为这两部分映射的个数之和。

即:f Nn -1=是满射不是满射当f Nn -1是满射时,根据满射个数计算的定义,对于N n -1中的每一个满射个数记为e n -1,m ,而f (n )可以取N m 中的任何一个元素,故有m 种,每一个元素均对应着有这样的e n -1,m 个。

所以f N n -1是满射时,f N n 满射的个数有me n -1,m 个。

当f Nn -1不是满射时。

在N n -1的基础上考虑N m -1的情况:这时,由于在N n 中减少了一个“原像”,相应在N m 中减少一个“像”。

这样从两个集合中各减少一个元素后,N n -1→N m -1的映射必仍为满射,而其个数为e n -1,m -1个。

因f (n )可以取N m 中的任何一个元素,故有m 种,每一种均对应着有这样的e n -1,m -1个。

故f Nn -1不是满射时,f Nn 满射的个数有me n -1,m -1个。

所以,f Nn 满射的个数共有:#S(N n,N m)=e n,m=me n-1,m+me n-1,m-1=m(e n-1,m+e n-1,m-1)例4:把4封信投入3个信箱,每个信箱至少有一封信,有多少种不同的投法?解:令信的集合为N n={a,b,c,d},信箱的集合为N m={1,2,3}。

把4封信投入3个信箱,每个信箱至少有一封信,不同的投法数相当于求满射f:N n→N m的个数:#S(N n,N m)= e n,m=e4,3∵e4,3=3(e3,3+e3,2)=3(3!+e3,2)　e3,2=2(e2,2+e2,1)=2(2!+1)=6∴e4,3=3×(6+6)=36即不同的投法数为36。

例5:一名教师和4名获奖同学排成一排照相留念。

若教师不排在两端,有多少种不同排法?(1993年上海高考题)解:教师与学生共有5人,教师不排在两端,则教师只能排在中间三个位置,排法数相当于单射f:N1={教师}→N3={2,3,4}的个数:#I(N1,N3)=P31;余下的四个位置由4名获奖同学来排,排法数相当于满射g:N4={甲、乙、丙、丁}→N′4={a,b,c,d}的个数:#S(N4,N4′)= e4,4,所以不同的排法数有:N=#I(N1,N3)×#S(N4,N4′)=P31×e4,4=3×4!=72[参考文献][1]张荣堂.从高考题看排列组合建立模型教学的重要性[J].中学数学杂志,2000,(1):14-15.[2]贺晓军.对排列、组合单元教学的思考[J].数学教学研究,2000,(6):35-36.[3]张奠宙,邹一心.现代数学与中学数学[M].上海教育出版社,1991.44-54.(责任编辑:叶　普)Analyzing the Problem of Permutations and Combinationsin the Viewpoint of MappingZHANG Jin-liang(Jianyang Normal Scho ol,Jianyang354200,China)A bstract:T his thesis analy zes and ponders the problem of permutations and combinations in the viewpoint of mapping.I t ex pounds the calculting fo rmulas o f single mapping and full mapping and ex plains their application in solving the problem of permutatio ns and combinations.Key words:sing le mapping;full mapping;permutations and combinations。