1、【重、难点解析】（一）排 列1无重复元素的排列（线排列）从 n 个元素的集合 S 中选出 r 个元素的排列，称为 r-排列。其个数为：)!()1()2(1),( nnrP从 n 个元素的集合 S 中选出 n 个元素的排列，称为全排列。其个数为：!),(p2无重复元素的圆排列（环排列）从 n 个元素的集合 S 中选出 r 个元素排列成圆环，称为 r-圆排列。其个数为：)!(),(rnP公式解释 n 个元素的 r-排列有 个，而其中的任何一个排列 的顺, ra,21序移动： 共 r 个。因此 n 个元素的 r-圆排11214312 ,;,;, rr aaa列数为：)!(),(rnrP当 n=r 时
2、，n 个元素的集合 S 的全圆排列数为： )!1(),3重复排列设 ，则 S 所有元素的不同的 n-重复排列数为：,21kbnbnS!)(21kn 设 ，则 S 的 r-可重复全排列数为 nr。,21nbbS(二)组 合1无重复元素的组合数从 n 个元素的集合 S 中选出 r 个元素组成一组，称为 r-组合。其个数为： )!(!)1()2(1!),( nrnnrPCk 2 n个元素的集合 S的 r-可重复组合数从 n 个元素的集合 S 中选出 r 个元素的 r-可重复组合数，记作 F（n,r）:1),(nnCF公式解释 设有 n 个元素 ，与自然数 1,2,n，建立一一对应关系。,21nbS所
3、考虑的任何 r-组合可以看作是一个 r 个数的数组（b 1, b2, bn） 。由于是数组，不妨认为 bi 按大小顺序排列，相同的 bi（可以重复）连续地排在一起，如按 b1b 2b rn排列。令 di= bi+i-1(i=1,2,r)，于是,1,21 rddr由于 最大可取 n，那么 最大可取 。有i in)1(,2121 rnrr从而将问题转化为求集合（1,2,，n+r-1 ）的 r-组合问题，易见，有一种b 1, b2, br的取法，就有一种d 1, d2, dr的取法。它们一一对应。这样，允许重复地从 n 个不同元素中取 r 个元素的组合数和不允许重复地从 n+r-1 元素中取 r 个
4、元素的组合数是相同的。故有公式1),(nrrnCf3组合恒等式（1） 1rnrnC（2） nknnn C0210 2（3） nkknnnnC0210 )1()1(（4） rkknr0)(（5） nknC112（6） 12nmnn C（7） ki knmikni0（三）筛法原理筛法原理也称为容斥原理，又称包含排列原理。筛法原理是用以解决集合的元素计数个数、概率中一般和事件的概率计算公式。在计数问题中，常采用间接计算一个集合的元素个数，比直接计算容易些。如，某单位集会，共有 187 人到会。由于某种需要，想知道男来宾的人数。但是，女来宾人数易计算出来。二者之差即为男来宾数。在集合计数中： | |
5、| | 3213231321 212121 AAASA 推而广之： jijimiiS| 12kji rkjiA)1(| |)1(|222mmii iir r设 S 是有 N 个元素的集合，A 1 是 S 的具有性质 P（1）的子集，其元素个数| A1|记作N1；A 2 是 S 的具有性质 P（2 ）的子集，其元素个数|A 2|记作 N2； 是 S 的同时具21ii有性质 P（i 1）和 P（i 2）的子集，其元素个数| |记作 ；21iiA21,i是 S 的同时具有性质 P（i 1）P（i 2） P（i r）的子集，其元素个数|riii21|记作 ； 的不具有 P（i ） （i=1,2,m）r
6、iii A21 riiN,21 Sm是2任何性质的子集，其元素个数| |记作 N（0） 。于是上面式改写成：A miiir iijiimiNkk ,21, ,1)()(02121 3212121 这正是本章第 3 节的公式（4-3-1） 。（四）递推公式与分部1初等几何问题平面上 n 条一般直线（任何两直线不平行，任何三条直线不共点） ，将平面分成几个部分（区域）？用 Pn 表示 n 条直线所分平面的部分数（区域数） ，有：当 n=0 时，没有直线，平面是一个整体，即;10P当 n=1 时，一条直线，将平面分成 2 个部分，即 ;001nP当 n=2 时，2 条直线，将平面分成 4 个部分，即
7、;2112nPP当 n=3 时,3 条直线，将平面分成 7 个部分，即如图（4-7）;3223n=0 n=1 n=2 n=3图 4-7 直线分割平面示意图依此类推，一般地，有公式 Pn1且 nPn1 12)()1(2(321)(2 nn2递推公式与斐波那契（ Fibonacci）数列例 有一个人把一对（雌雄各一）的大兔子放在自家的院子里饲养，他想知道一年后能生出多少对兔子，假定这对大兔子每月可生雌雄各一的一对小兔子，而新生的一对小兔子经过一个月可以长成大兔子，以后也是每月产雌雄各一的一对小兔子。问：一年后（也就是到第 13 个月开始）能生出多少对兔子？解 由题设知，第一个月有一对兔子，第二个月
8、开始时有两对兔子（大、小兔子各一对） ，第三个月开始，新出生的小兔子刚长成大兔子还不能产仔，只有原来的一对大兔子产仔一对，共有 2+1=3 对兔子，它是第一、第二两个月兔子对数的总和。第四个月开始时，除第三个月出生的一对兔子不产仔外，其余的两对兔子都能产仔，共产小兔子 2 对，与第二个月兔子的对数相同，因此共有 2+3=5 对，它等于第二、第三两个月兔子对数的总和。一般地，可这样考虑：我们用 f(n)表示第 n 个月初兔子的对数。因为第 n 个月开始时，除第 n-1 个月新生的兔子不能产仔外，其余的兔子，即在第 n-2 个月时已有的兔子都能产仔，而第 n-2 个月共有兔子数为 f(n-2)对，
9、故第 n 个月新生的小兔子共有 f(n-2)。又因为第 n 个月的兔子是由两部分组成，一部分是在第 n-1 个月时已有的兔子，共f(n-1)对；另一部分是第 n 个月新生的小兔子，有 f(n-2)对。因此，第 n 个月共有：f(n)= f(n-1)+ f(n-2) 公式给出了连续多年兔子数之间的关系，我们称公式为递推公式。我们已经知道：f(1)=1 ,f(2)=2,当 n3 时，利用公式可以计算出 f(n)的值如下：f(3)=1+2=3 f(4)=3+2=5f(5)=5+3=8 f(6)=8+5=13f(7)=13+8=21 f(8)=21+13=34f(9)=34+21=55 f(10)=5
10、5+34=89f(11)=89+55=144 f(12)=144+89=233f(13)=233+144=377解得：一年后（即第 13 个月）有兔子 377 对。若规定 f(0)=1，f(1) =1，由递推公式可得到数列1,1,2,3,5,8,13,21,34,55,89,144,233,377,数学界把这个数列叫做斐波那契数列，以纪念最先得到这个数列的数学家斐波那契（Leon ardo Fibonacci）,(约 11701250)，是意大利数学家 。由于这个数列在数学、物理、化学领域经常出现，又具有很奇特的性质，所以美国数学会每三个就出版一本专门对这种数列进行研究的季刊，称为斐波那契季刊
11、 。递推公式的另一解释为：设 n-样本 集合，若 只能取 0 或 1，求不),(21na i允许连续出现两个 0 的样本个数，用 f(n)表示。记 f(0)=1，当 n=1 时，即 1-样本 取 0 或 1，有 2 个样本：（0） ， （1） ；故 f(1)=2；1)(a当 n=2 时，即 2-样本 。有样本（11） ， （01） ， （10） ，故 f(2)=3;2当 n=3 时，即 3-样本（ ） 。有样本（111） ， （101） ， （110） ， （011） ， （010） 。即，31a1=1 时，样本个数为 f(n-1)=f(2)=3；a1=0 时，a 2 只能取 1，样本个数为
12、f(n-2)=f(1)=2故 f(3)=5=f(2)+f(1)=f(n-1)+f(n-2)当 n=4 时，即 4-样本（a 1a2a3a4） 。有样本(1111)， （1011） ， （1010） ， （1101） ，（1110） ， （0111） ， （0110） ， （0101） 。故 f(4)=8=f(3)+f(2)=f(n-1)+f(n-2)以此类推，同样能得到递推公式f(n)=f(n-1)+f(n-2)3扰乱排列设 S=1,2,，n， （a 1,a2,，a n）和（b 1,b2,bn）是 S 的两个排列，对于一切i，i=1,2,n,有 ，则称（b 1,b2,bn）是（a 1,a2,，
13、 an）的一个扰乱排列，或称错位ii排列、移位排列。即每个数码都不在原来位置上的排列。如（4321）和（3412）都是（1234）的扰乱排列。而（1324）和（1432）都不是（1234）和扰乱排列，因为不是每个数码都不在原位置。用 D（n）表示 n 个元素的扰乱排列的个数。设 A 是 S 的所有排列的集合： !|nA令 为第 i 个元素定位在 i 的 S 的所有排列。 表示第 i 个元素定位在 i 的的排列i |i数，i=1,2,n。|)(1inAD因为元素 i 定位在 i 的所有排列数为（n-1）! ，即 =（n-1）!(i=1,2,，n)|iS 的两个元素的定位排列数为 )!2(|nji
14、S 的 k 个元素的定位排列数为 |1kAik由筛法原理： |)(| 1211 injininin ACCA!0)!()!( 1n所以 )(432)D !1!1! nn容易证明： )2()()(Dn4定位排列设 S 是一个排列（a 1,a2,，a n） ，如果有 r 个 ai=i 排列，则称为 S 的 r 定位排列。如 S 的一个排列（1234） ，则（1243）和（1432）是 S 的一个 2 定位排列，而（1342）不是 S 的 2 定位排列，只是 1 定位排列。S 是 r 定位排列数用 N（r ）表示。因为有 r 定位排列，剩余 n-r 是扰乱排列，有 D（n-r ）.而 n 个元素选
15、r 个的方式有个。rnC于是 n 个元素的集合 S 的 r 定位排列数为：)!(1)!4132!1()() rnrnDr 5从 n个数码的集合中取出 k个数码，不出现两个连续数码的个数设 S 是 n 个数码1,2,n的集合，从 S 中取出 k 个数码，不出现有 2 个连续数码的个数是knCf1),(当 n,1 视为连续数时，从 S 中取出 k 个数码，不出现有 2 个连续数码的个数为：kng),(6数 Un的计算niin aCIJper21)(其中 J 是元素全为 1 的 n 阶方阵，I 是 n 阶恒等矩阵（单位矩阵） ，C 是上次对角线为1，即 ，其余元素为 0 的 n 阶方阵： 表示矩阵)
16、(23naa niia21J-I-C 的所有不同行不同列的 n 个元素乘积之和。其中 i1 不能取 1,2； i2 不能取 2,3；i n 不能取 n,1。显然 的值要么是 1，要么是 0。nii21或用下公式计算：)!2(,)!(!12ngCUnn0,13,g其中 （见教材本章定理 4.7） 。knk),(7分 部分部就是将正整数表成若干个正整数之和。分 出 的 正 整 数 不 能 重 复不 可 重 复 现分 出 的 正 整 数 可 重 复 出可 重 复无 序 部 分 分 出 的 正 整 数 不 能 重 复不 可 重 复 现分 出 的 正 整 数 可 重 复 出可 重 复有 序 分 部分 部
17、 现以正整数 4 的分部为例，说明各个概念，见下表。表 4-1 4 的分部表有 序 分 部 无 序 分 部 备 注不允许重复 4=4，4=1+3，4=3+1 4=4，4=3+1允许重复 4=44=1+3， 4=3+14=2+2， 4=2+1+14=1+2+1，4=1+1+24=1+1+1+14=44=1+34=2+2， 4=2+1+14=1+1+1+1在一个分部中数字重复出现设 n 是正整数，则不定方程),21,0(21 kixxik 的正整数解就称为 n 的分部。如表 4-1 中，正整数 4 的有序不重复分部有 3 个；无序不重复分部有 2 个；有序重复分部有 8 个，无序重复分部有 5 个
18、。我们着重讨论允许重复的分部。（1）n 的可重复的 k 个有序正整数解的个数不定方程 的 k 个可重复的有序正整数解的),21,0(21ixxik 个数，记作 Pk(n),有：1)(knkCP举例验证。如 n=7:k=1,即 7 表成 1 个正整数之和，显然 x1=7.则06)(knCPk=2,即 7 表成 2 个正整数之和： ，有 2+5，5+2，4+3，3+4，6+1，1+6 共7216 个，则 162)7(knk=3,即 7 表成 3 个正整数之和： ，有7321x1+1+5， 1+5+1，5+1+1，2+1+4，2+4+1，1+2+4，1+4+2，4+1+2，4+2+1 ，3+3+1，
19、3+1+3，1+3+3 ，2+2+3，2+3+2，3+2+2共 15 个，则126315)7(knCPk=4,即 7 表成 4 个正整数之和： ，有：7432xx1+1+1+4，1+1+4+1，1+4+1+1，4+1+1+1，1+1+2+3，1+1+3+2，1+2+3+1 ，1+3+2+1，2+3+1+1， 3+2+1+1，1+2+1+3，1+3+1+2，2+1+3+1，3+1+2+1，2+1+1+3 ，3+1+1+2，1+2+2+2，2+1+2+2，2+2+1+2，2+2+2+1共 20 个。则 136420)7(knCPk=5,即 7 表成 5 个正整数之和： ，有：754321xx1+1
20、+1+1+3，1+1+1+3+1，1+1+3+1+1，1+3+1+1+1，3+1+1+1+1，1+1+2+1+2，1+2+1+1+2，2+1+1+1+2，2+1+1+2+1 ，2+1+2+1+1 ，2+2+1+1+1，1+2+2+1+1，1+1+2+2+1，1+1+1+2+2，2+1+1+1+2，共 15 个，则14651)7(knCPk=6,即 7 表成 6 个正整数之和： ，有：7654321 xx1+1+1+1+1+2，1+1+1+1+2+1, 1+1+1+2+1+1, 1+1+2+1+1+1, 1+2+1+1+1+1, 2+1+1+1+1共 6 个，则 1566)(knCPk=7,即
21、7 表成 7 个正整数之和： ，只有7654321 xxx1+1+1+1+1+1+1共 1 个。 1567)(knCP（2）n 的可重复的 k 个无序正整数解的个数不定方程 个可重复的无序正整数解的个kixxik 的),21,0(21 数，仍记作 ,有)(PkkiknP1)()(易知， 。0,)(，nk时当举例验证。如：当 n=1 时，k=1,即 1=1，所以 P1（1）=1。当 n=2 时，k=1,即 2=2，所以 P1（2）=1；k=2,即 2=1+1，所以 P2（2）=1。当 n=3 时，k=1,即 3=3，所以 P1（3）= P 1（2）=1 ； k=2,即 3=1+2，所以 P2（3
22、）= P 1（1）+ P 2（1）=1 ；k=3,即 3=1+1+1，所以 P3（3）=1。 当 n=4 时，k=1,即 4=4，所以 P1（4）= P 1（3）=1 k=2,即 4=2+2 或 1+3，所以 P2（4）= P 1（2）+ P2（2）=1+1=2k=3,即 4=3+1，所以 P3（4）= P 1（1）+ P 2（1）+ P3（1）=1+0+0+1 k=4,即 4=1+1+1+1，所以 P4（4）=1。当 n=5 时，k=1,即 5=5，所以 P1（5）= P 1（4）=1 k=2,即 5=1+4 或 2+3，所以P2（5）= P1（3）+ P 2（3）=1+1=2k=3,即 5
23、=2+2+1，3+1+1，所以P3（5）= P1（2）+ P 2（2）=1+1=2k=4,即 5=1+1+1+2，所以P4（5）= P1（1）+ P 2（1）=1+0=1k=5,即 5=1+1+1+1+1,所以 P5（5）=18用母函数计算组合问题母函数又叫生成函数。它是解决计数问题的一个有力工具，我们先看两个例子。例 1 袋内有 4 个红球，3 个白球，2 个黑球。从袋中任取 4 个球，问有多少种不同的取法。解 考虑如下表达式： )1)(1)() 232432 xxxxf961在第 1 个括号中 xk 的指数 k 可认为代表 k 个红球，第 2 个括号中 xk 的指数 k 可认为代表 k 个
24、白球，第 3 个括号中的 xk 的指数 k 可认为代表 k 个黑球。如果用 ，那么kii个 括 号 里 的表 示 第)(4)3(2)1(x就是一种（取法）方案，它表示取 1 个红球，2 个白球，1 个黑球的一种取法；而40)3(4)(xx也是一种方案，它表示取红球 4 个，白球、黑球都不取的一种取法。每次取 4 个球，所有不同的取法个数就是 f(x)的展开式中 x 的系数 11。例 2 若有 1g,2g,3g,4g 的砝码各一枚，问能称出哪几种重量？有几种可能的方案？ 1)(1)(432xx 10987652xx这里第 1 个括号中 x 的指数 1 可认为代表 1g 的砝码 1 枚，第 2 个
25、括号中 x 的指数 2 可认为代表 2g 的砝码 1 枚，余类推。在展开式中：如 2x5 的指数 5 表示可称 5g 重物，系数 2 则表示称 5g 重物有 2 种方案（因为 ，即用 2g 与 3g 砝码各一枚，可称出 5g 的重量；用 1g 和 4g 的4352砝码各一枚，也能称出 5g 的重量） 。从展开式知道，用 1g,2g,3g 和 4g 的砝码各一枚，能称出 1g 和 10g 的重量。展开式中各项的系数，便是方案数。下面考虑多重集。设 ,21nakakA它表示集合 A 有 。n个个个 ,21设想有标号分别为 1,2,n 的盒子在第 i 个盒子里放有 个球 。ik),21(nia所谓多
26、重集 A 的一个 r-组合，就是指由 A 中的可重复的 r 个元素构成的一个组合，那么多重集 A 的一个如下的 5-组合： 321a则对应于从第 1 个盒子里取出 2 个球，第 2 个盒子里取出 2 个球，第 3 个盒子里取出 1 个球的一种取法；同样，多重集 A 的一个 7-组合：431对应于从第 1 个盒子里取 3 个球，第 3 个盒子里取 2 个球，第 4 个盒子里取 2 个球的一种取法。反之，从第 1 个盒子里取 1 个球，第 2 个盒子里取 3 个球，第 4 个盒子里取 1 个球，则对应于多重集 A 的一个 5-组合。421a所以，多重集 A 的 r-组合数就等于从 n 个盒子里一共取出 r 个球的不同取法数。如果 x 代表球， 代表从第 1 个盒子里取出 i1 个球， 代表从第 2 个盒子里取出 i2 个球，并且1ix 2ix满足条件riin21 ),1,(njkij 那么项
