组合数学PPT课件.ppt

《组合数学PPT课件.ppt》由会员分享，可在线阅读，更多相关《组合数学PPT课件.ppt（360页珍藏版）》请在金锄头文库上搜索。

1、组合数学课件1 1. .课程简介相关课程使用教材数学分析高等代数离散数学书名：组合数学（第三版）作者：孙淑玲 出版社：中国科学技术大学出版社 本课程针对计算机科学中的一个重要学科组合数学，组合数学是数学的一个分支，它研究事物在结定模式下的配置，研究这种配置的存在性，所有可能配置的计数和分类以及配置的各种性质。组合数学在计算机科学中有着极其广泛的应用。组合学问题求解方法层出不穷、干变万化，应以理解为基础，善于总结各种技巧，掌握科学的组织和推理方法。2 2. .目录（1 1）引言第1 1章 排列与组合 1.1 加法法则和乘法法则 1.2 排列 1.3 组合 1.4 二项式定理 1.5 组合恒等式及

2、其含义 1.6 模型转换 本章小结 习题第2 2章 鸽笼原理 2.1 鸽笼原理 2.2 鸽笼原理的推广 2.3 Ramsey定理 本章小结 习题第3章 容斥原理 3.1 容斥原理 3.2 重集r-组合 3.3 错排问题 3.4 有限制排列 3.5* 一般有限制排列 3.6* 广义容斥原理 本章小结 习题第4 4章 母函数 4.1 母函数的基本概念 4.2 母函数的基本运算 4.3 在排列组合中的应用 4.4 整数的拆分 4.5 Ferrers图目录3. .目录（2 2） 4.6* 在组合恒等式中的应用 本章小结 习题第5 5章 递推关系 5.1 递推关系的建立 5.2 常系数线性齐次递推关系

3、5.3 常系数线性非齐次递推关系 5.4 迭代法与归纳法 5.5 母函数在递推关系中的应用 5.6* 典型的递推关系 本章小结 习题第6 6章 Plya定理 6.1 群的概念 6.2 置换群 6.3 循环、奇循环与偶循环 6.4 Burnside引理 6.5 Plya定理 6.6 Plya定理的应用 6.7 母函数形式的Plya定理 6.8* 图的计数 6.9* Plya定理的若干推广 本章小结 习题*课程总结注：加*的章节一般性了解4 4. . 存在性问题 计数和枚举 优化问题 构造性问题 科学的组织 科学的推理 古老 年轻 练习 思考总结 笔记5 5. .组合数学研究的中心问题是按照一定的

4、规则来安排有限多个对象 如果人们想把有限多个对象按照它们所应满足的条件来进行安排，当符合要求的安排并非显然存在或显然不存在时，首要的问题就是要证明或者否定它的存在。这就是存在性问题。如果所要求的安排存在，则可能有多种不同的安排，这又经常给人们提出这样的问题：有多少种可能的安排方案？如何对安排的方案进行分类？这就是计数问题。如果一个组合问题有解，则往往需要给出求其某一特定解的算法，这就是所谓的构造性问题。如果算法很多，就需要在一定的条件下找出一个或者几个最优或近乎最优的安排方案，这就是优化问题。6 6. .本章重点介绍以下的基本计数方法： 加法法则和乘法法则 排列 组合 二项式定理的应用 组合恒

5、等式7 7. . 相互独立的事件 A、B 分别有 k k 和 l 种方法产生，则产生 A 或 B 的方法数为 k k+ +l 种。1.1 加法法则1.1.11.1.1加法法则若|A|= =k k，|B|= =l ，且AB= = ，则|AB|=k k+ +l 。设S是有限集合，若，且时，则有。8 8. .1.1 加法法则例11.1.11.1.1加法法则例1 1、有一所学校给一名物理竞赛优胜者发奖，奖品有三类，第一类是三种不同版本的法汉词典；第二类是四种不同类型的物理参考书；第三类是二种不同的奖杯。这位优胜者只能挑选一样奖品。那么，这位优胜者挑选奖品的方法有多少种？解：设S是所有这些奖品的集合，S

6、i是第i类奖品的集合( (i=1,2,=1,2,3) )，显然，SiSj j= = ( (ij j) )，根据加法法则有9 9. .1.1 加法法则例2、31.1.11.1.1加法法则例2 2、大于0 0小于1010的奇偶数有多少个？例3、小于2020可被2 2或3整除的自然数有多少个？解：设S是符合条件数的集合，S1 1、S2 2分别是符合条件的奇数、偶数集合，显然，S1 1S2 2= = ，根据加法法则有1010. .若|A|= =k k，|B|= =l ，AB= =( (a, ,b) )|aA，bB，则|AB|=k kl 。1.1 乘法法则1.1.21.1.2乘法法则 相互独立的事件 A

7、、B 分别有 k k 和 l 种方法产生，则选取A以后再选取B 的方法数为 k kl 种。设 是有限集合，且，则有。1111. .1.1 乘法法则例41.1.21.1.2乘法法则例4 4、从A 地到B地有二条不同的道路，从B地到C C地有四条不同的道路，而从C C地到D地有三条不同的道路。求从A地经B、C C两地到达D地的道路数。解：设S是所求的道路数集合，S1 1、S2 2、S3分别是从A到B、从B到C C、从C C到D的道路集合，根据乘法法则有1212. .1.1 乘法法则例51.1.21.1.2乘法法则例5 5、由数字1,2,1,2,3,4,5,4,5可以构成多少个所有数字互不相同的四位

8、偶数？解：所求的是四位偶数，故个位只能选2 2或4 4，有两种选择方法；又由于要求四位数字互不相同，故个位选中后，十位只有四种选择方法；同理，百位、千位分别有三种、两种选择方法，根据乘法法则，四位数互不相同的偶数个数为2 2 4 4 3 2=482=481 13. .1.1 乘法法则例61.1.21.1.2乘法法则例6 6、求出从8 8个计算机系的学生、 9 9个数学系的学生和1010个经济系的学生中选出两个不同专业的学生的方法数。解：由乘法法则有选一个计算机系和一个数学系的方法数为8 89=729=72选一个数学系和一个经济系的方法数为9 910=9010=90选一个经济系和一个计算机系的方

9、法数为10108=808=80由加法法则，符合要求的方法数为72+90+80=24272+90+80=2421414. .1.1 重集的概念1.1.1.1.3 计数问题的分类 有序安排或有序选择允许重复/ /不允许重复 无序安排或无序选择允许重复/ /不允许重复 标准集的特性：确定、无序、相异等。 重集：B= =k k1 1*b1 1, k, k2 2*b2 2, , k kn*bn，其中：bi为n个互不相同的元素，称 k ki为bi的重数， i=1,2,=1,2,n，n=1,2,=1,2, ，k ki=1,2,=1,2, 。1515. .1.2 线排列1.2.11.2.1线排列从n个不同元素

10、中，取r个(0(0rn) )按一定顺序排列起来，其排列数P( (n, ,r) )。设A= =an ，从A中选择r个(0(0rn) )元素排列起来，A的r 有序子集，A的r 排列。如n, ,rZ且nr0,0,P( (n, ,r)=)=n!/(!/(n-r)! )!。如n= =r，称全排列P( (n, ,n)=)=n! !；如nr, ,P( (n, ,r)=0)=0；如r=0,=0,P( (n, ,r)=1)=1。证明：构造集合A的r 排列时，可以从A的n各元素中任选一个作为排列的第一项，有n种选法；第一项选定后从剩下的n-1 1个元素中选排列的第二项有n-1 1种选法；由此类推，第r项有n-r+

11、1+1种选法。根据乘法法则有1616. .1.2 线排列推论11.2.11.2.1线排列推论1.1.11.1.1：如n, ,rN且nr2 2，则P( (n, ,r)=)=nP( (n-1 1, ,r-1)1)。证明：在集合A的n个元素中，任一个元素都可以排在它的r 排列首位，故首位有n种取法；首位取定后，其他位置的元素正好是从A的另n-1 1个元素中取r-1 1个的排列，因此有P( (n-1, 1,r-1)1)种取法。由乘法法则有P( (n, ,r)=)=nP( (n-1 1, ,r-1)1)证毕。1717. .1.2 线排列推论21.2.11.2.1线排列推论1.1.11.1.1：如n, ,

12、rN且nr2 2，则P( (n, ,r)=)=nP( (n-1 1, ,r-1)1)。推论1.1.21.1.2：如n, ,rN且nr2 2，则P( (n, ,r)=)=rP( (n-1 1, ,r-1)+1)+P( (n-1 1, ,r) )。证明：当r2 2时，把集合A的r 排列分为两大类：一类包含A中的某个固定元素，不妨设为a1 1，另一类不包含a1 1。第一类排列相当于先从A-a1 1中取r-1 1个元素进行排列，有P( (n-1, 1,r-1)1)种取法，再将a1 1放入每一个上述排列中，对任一排列，a1 1都有r种放法。由乘法法则，第一类排列共有rP( (n-1 1, ,r-1)1)

13、个。第二类排列实质上是A-a1 1的r 排列，共有P( (n-1 1, ,r) )个。再由加法法则有P( (n, ,r)=)=rP( (n-1 1, ,r-1)+1)+P( (n-1 1, ,r) )证毕。1818. .1.2 线排列例11.2.11.2.1线排列例1 1、由数字1,2,1,2,3,4,5,4,5可以构成多少个所有数字互不相同的四位数？解：由于所有的四位数字互不相同，故每一个四位数就是集合1,2,1,2,3,4,5,4,5的一个44排列，因而所求的四位数个数为1919. .1.2 线排列例21.2.11.2.1线排列例 2 2、 将 具 有 9 9个 字 母 的 单 词FRAG

14、MENTS进行排列，要求字母A总是紧跟在字母R的右边，问有多少种这样的排法？如果再要求字母M和N必须相邻呢？解：由于A总是R的右边，故这样的排列相当于是8 8个元素的集合F, ,RA, ,G, ,M, ,E, ,N, ,T, ,S的一个全排列，个数为如果再要求M和N必须相邻，可先把M和N看成一个整体 = =M, ,N，进行7 7个元素的集合F, ,RA, ,G, ,E, ,T, ,S, , 的全排列，在每一个排列中再进行 M, ,N的全排列，由乘法法则，排列个数为2020. .1.2 线排列例31.2.11.2.1线排列例3、有多少个5 5位数，每位数字都不相同，不能取0 0，且数字7 7和9

15、 9不能相邻？解：由于所有的5 5位数字互不相同，且不能取0 0，故每一个5 5位数就是集合1,2,91,2,9的一个5 5-排列，其排列数为P(9,5)(9,5)，其中7 7和9 9相邻的排列数为c(7,(7,3)4!2)4!24 42 2P(7,(7,3) )，满足题目要求的5 5位数个数为2121. .1.2 圆排列1.2.21.2.2圆排列设A= =an ，从A中取r个(0(0rn) )元素按某种顺序（如逆时针）排成一个圆圈，称为圆排列（循环排列）。设A= =an，A的r圆排列个数为P( (n, ,r)/ )/r。证明：由于把一个圆排列旋转所得到另一个圆排列视为相同的圆排列，因此线排列

16、a1 1a2 2ar，a2 2a3ara1 1，ara1 1a2 2ar-1 1在圆排列中是一个，即一个圆排列可产生r个不同的线排列；同理， r个不同的线排列对应一个圆排列。而总共有P( (n, ,r) )个线排列，故圆排列的个数为P( (n, ,r)/ )/r=n!/(!/(r( (n-r)!)!)证毕。2222. .1.2 圆排列例41.2.21.2.2圆排列例4 4、有8 8人围圆桌就餐，问有多少种就座方式？如果有两人不愿坐在一起，又有多少种就座方式？解：由上述定理知8 8人围圆桌就餐，有8!/8=7!=50408!/8=7!=5040种就座方式。又有两人不愿坐在一起，不妨设此二人为A、

17、B，当A、B坐在一起时，相当于7 7人围圆桌就餐，有7!/7=6!7!/7=6!种就座方式。 而A、B坐在一起时，又有两种情况，或者A在B的左面，或者A在B的右面，因此A、B坐在一起时，共有2 26!6!种就座方式，因此如果有两人不愿坐在一起，就座方式为7!7!-2 26!=56!=56!=6!=36006002 23. .1.2 圆排列例51.2.21.2.2圆排列例5 5、4 4男4 4女围圆桌交替就座有多少种就座方式？解：显然，这是一个圆排列问题。首先让4 4个男的围圆桌就座，有4!/4=4!/4=3! !种就座方式。 因为要求男女围圆桌交替就座，在男的坐定后，两两之间均需留有一个空位，

18、女的就座相当于一个4 4元素集合的全排列，就座方式数为4!4!。由乘法法则知，就座方式数为3! !4!=1444!=1442424. .1.2 重排列1.2.1.2.3 重排列从n个不同元素中，可重复选取r个按一定顺序排列起来，称为重排列。从重集B= =k k1 1*b1 1, k, k2 2*b2 2, , k, , kn*bn中选取r个按一定顺序排列起来。重集B= =*b1 1, ,*b2 2,*bn 的r 排列的个数为nr。证明：构造B的r 排列如下：选择第一项时可从n个元素中任选一个，有n种选法，选择第二项时由于可以重复选取，仍有n种选法，同理，选择第r项时仍有n种选法，根据乘法法则，

19、可得出r 排列的个数为nr。证毕。2525. .1.2 重排列例61.2.1.2.3 重排列例6 6、由数字1,2,1,2,3,4,5,6,4,5,6这六个数字能组成多少个五位数？又可组成多少大于345004500的五位数？解：一个五位数的各位数字可重复出现，是一个典型的重排列问题，相当于重集B= =*1, 1,*2,2,*6 6的55排列，所求的五位数个数为6 65 5=7776=7776。大于345004500的五位数可由下面三种情况组成：万位选4,5,64,5,6中的一个，其余4 4位相当于重集B的44排列，由乘法法则知，共有3 6 64 4个五位数；万位是3，千位5,65,6中的一个，

20、其余3位相当于重集B的3 排列，由乘法法则知，共有2 2 6 63个五位数；万位是3，千位4 4中的一个，百位选5,65,6中的一个，其余2 2位相当于重集B的22排列，由乘法法则知，共有2 2 6 62 2个五位数；由加法法则知，大于345004500的五位数个数为36 64 4+ + 2 26 63 + + 2 26 62 2=4=4392922626. .1.2 重排列计数1.2.1.2.3 重排列重集B= =n1 1*b1 1, ,n2 2*b2 2,nk k*bk k的全排列个数为证明：将B中的ni个bi看作不同的ni个元素，赋予上标1,2,1,2,ni，即 ，如此，重集B就变成具有

21、n1 1+ +n2 2+nk k= =n个不同的元素集合显然，集合A的全排列个数为n! !。又由于ni个bi赋予上标的方法有ni! !种，于是对重集B的任一个全排列，都可以产生集合A的n1 1! !n2 2! !nk k! !个排列（由乘法法则），故重集B的全排列个数为证毕。注：利用组合数的计数方法同样可以得出证明。2727. .1.2 重排列例71.2.1.2.3 重排列例6 6、有四面红旗，三面蓝旗，二面黄旗，五面绿旗可以组成多少种由1414面旗子组成的一排彩旗？解：这是一个重排列问题，是求重集4 4*红旗, ,3*蓝旗,2 ,2*黄旗,5 ,5*绿旗的全排列个数，根据定理，一排彩旗的种数

22、为2828. .1.2 重排列例81.2.1.2.3 重排列例8 8、用字母A、B、C C组成五个字母的符号，要求在每个符号里，A至多出现2 2次，B至多出现1 1次，C C至多出现3次，求此类符号的个数。解：这也是一个重排列问题。根据分析，符合题意的符号个数相当于求重集M= =2 2*A,1 ,1*B, ,3*C C的55排列个数，可分为三种情况：需要分别求M-A、M-B和M-C C的全排列个数。根据加法法则，此类符号个数为2929. .1.2 项链排列1.2.41.2.4项链排列对圆排列，通过转动、平移、翻转、可重合的，即可看作项链排列。如n个不同元素的r 项链排列个数为P( (n, ,r

23、)/(2)/(2r) )，具体参照Plya定理。30 0. .1.3 无重组合1. 1.3.1.1（无重）组合设A= =an，从A中选择r个(0(0rn) )元素组合起来，A的r 无序子集，A的r 组合。如rn，有C C( (n, ,r)=)=P( (n, ,r)/ )/r!=!=n!/(!/(r!( !(n-r)!)!)。如nr=0=0，C C( (n, ,r)=1)=1；如nr，C C( (n, ,r)=0)=0。从n个不同元素中，取r个(0(0rn) )不考虑顺序组合起来，其组合数C C( (n, ,r) )或。证明：从n个不同元素中取r个元素的组合数为C C( (n, ,r) )，而r

24、个元素可组成r! !个r 排列，即一个r 组合对应r! !个r 排列。于是C C( (n, ,r) )个r 组合对应r! !C C( (n, ,r) )个r 排列，这是从n个不同元素中取r个元素的r 排列数P( (n, ,r) )，因此有31 1. .1.3 无重组合推论11. 1.3.1.1（无重）组合推论1.5.11.5.1：C C( (n, ,r)=)=C C( (n, ,n-r) )证明：实际上，从n个不同元素中选出r个元素的同时，就有n-r个元素没有被选出，因此选出r个元素的方式数等于选出n-r个元素的方式数，即C C( (n, ,r)=)=C C( (n, ,n-r) )。得证。另

25、外，也可通过计算得出证明如下32 2. .1.3 无重组合推论21. 1.3.1.1（无重）组合推论1.5.11.5.1：C C( (n, ,r)=)=C C( (n, ,n-r) )推论1.5.2(1.5.2(Pascal公式) )：C C( (n, ,r) )= =C C( (n-1 1, ,r)+)+C C( (n-1 1, ,r-1)1)证明：利用组合分析法。在集合A的n个不同元素中固定一个元素，不妨设为a1 1，从n个元素中选出r个元素的组合由下面两种情况组成： r个元素中包含a1 1。相当于从除去a1 1的n-1 1个元素中选出r-1 1个元素的组合，再加上a1 1而得到，组合数为

26、C C( (n-1 1, ,r-1)1)； r个元素中不包含a1 1。相当于从除去a1 1的n-1 1个元素中选出r个元素的组合而得到，组合数为C C( (n-1 1, ,r) )。由加法法则即得C C( (n, ,r)=)=C C( (n-1 1, ,r)+)+C C( (n-1 1, ,r-1)1)另外，也可通过计算得出证明如下33. .1.3 无重组合推论31. 1.3.1.1（无重）组合推论1.5.11.5.1：C C( (n, ,r)=)=C C( (n, ,n-r) )推论1.5.2(1.5.2(Pascal公式) )：C C( (n, ,r)=)=C C( (n-1 1, ,r)

27、+)+C C( (n-1 1, ,r-1)1)推论1.5.1.5.3：C C( (n, ,r)=)=C C( (n-1 1, ,r-1)+1)+C C( (n-2 2, ,r-1)+1)+C C( (r-1 1, ,r-1)1)证明：反复利用Pascal公式，即可证明。或利用组合分析法，在集合A= =an的n个不同元素选出r个元素的组合可分为以下多种情况： 如r个元素中包含a1 1，相当于从除去a1 1的n-1 1个元素中选出r-1 1个元素的组合，再加上a1 1而得到，组合数为C C( (n-1 1, ,r-1)1)；如r个元素中不包含a1 1但包含a2 2，相当于从除去a1 1, ,a2

28、2的n-2 2个元素中选出r-1 1个元素的组合，再加上a2 2而得到，组合数为C C( (n-2 2, ,r-1),1),同理如r个元素中不包含a1 1, ,a2 2,an-r，但包含an-r+1+1，相当于从剩下的r-1 1个元素中选出r-1 1个元素的组合，再加上an-r+1+1而得到，组合数为C C( (r-1 1, ,r-1)1)。由加法法则得C C( (n, ,r)=)=C C( (n-1 1, ,r-1)+1)+C C( (n-2 2, ,r-1)+1)+C C( (r-1 1, ,r-1)1)34 4. .1.3 无重组合例11. 1.3.1.1（无重）组合例1 1、有5 5本

29、日文书，7 7本英文书，1010本中文书，从中取两本不同文字的书，问有多少种方案？若取两本相同文字的书，问有多少种方案？任取两本书，有多少种方案？解：从三种文字的书中取两种共有C C( (3,2)=,2)=3种取法。根据乘法法则有：日英各一本的方法数为5 57=7=35 5，中英各一本的方法数为10107=707=70，中日各一本的方法数为10105=50=50，由加法法则得35+70+50=1555+70+50=155取两本相同文字的，有两本中文、两本英文或两本日文三种方式，由加法法则得C C(5,2)+(5,2)+C C(7,2)+(7,2)+C C(10,2)=76(10,2)=76任取

30、两本书，相当于从5+7+10=225+7+10=22本书中取两本的组合，即C C(22,2)=2(22,2)=231 135 5. .1.3 无重组合例21. 1.3.1.1（无重）组合例2 2、从1 130000之间任取3个不同的数，使得这3个数的和正好被3除尽，问共有几种方案？解：所有的整数可分为以下3个分类：模3余0 0、模3余1 1和模3余2 2， 故 1 130000的 30000个 数 可 以 分 为 3个 集 合 ： A= =1,4,2981,4,298，B= =2,5,2992,5,299，C C= =3,6,6,30000。任取3个数其和正好被3整除的情况如下：三个数同属于集

31、合A，有C C(100,(100,3) )种方案；三个数同属于集合B，有C C(100,(100,3) )种方案；三个数同属于集合C C，有C C(100,(100,3) )种方案；三个数分别属于集合A, ,B,C,C，由乘法法则有1001003种方案。由加法法则得，所求的方案数为3C C(100,(100,3)+100)+1003=1485100=148510036 6. .1.3 无重组合例31. 1.3.1.1（无重）组合例3、某车站有1 1到6 6个入口处，每个入口处每次只能进一个人，问一小组9 9个人进站的方案数有多少？解I：按照从入口1 1到入口6 6的顺序可得到9 9个人一个排列

32、，再把两个入口间设上一个标志，加上这5 5个标志相当于每一个排列有1414个元素，其中5 5个标志没有区别，但其位置将区分各入口的进站人数，相当于1414个元素集合的55组合，故进站方案数为9!9! C C(14,5)=726485760(14,5)=726485760解II：同上分析，问题转化为重集1 1*p1 1,1 ,1*p2 2,1,1*p9 9,5 ,5*标志的全排列（pi代表9 9个人，i=1,9=1,9），故进站方案数为14!/5!=72648576014!/5!=726485760解III：考虑9 9个人选择方案，第1 1个人有6 6种选择，第2 2个人除了选择入口，还要考虑在

33、第1 1个人的前面或后面，故有7 7种选择同理，第9 9个人有1414种选择，根据乘法法则，故进站方案数为6 6 7 7 14=72648576014=72648576037 7. .1.3 无重组合例41. 1.3.1.1（无重）组合例4 4、求5 5位数中至少出现一个6 6，而被3整除的数的个数。解：1010进制数被3整除的充要条件是各位数的和能被3整除。据此可进行如下讨论：从左往右计，如最后一个6 6出现在个位，则十百千位各有1010种选择，万位有3种可能，根据乘法法则，总个数为310103 ；如最后一个6 6出现在十位，则个位有9 9种选择，百千位各有1010种选择，万位有3种可能，根

34、据乘法法则，总个数为310102 29 9 ；如最后一个6 6出现在百位，则个十位各有9 9种选择，千位有1010种选择，万位有3种可能，根据乘法法则，总个数为310109 92 2；如最后一个6 6出现在千位，则个十百位各有9 9种选择，万位有3种可能，根据乘法法则，总个数为39 93；如最后一个6 6出现在万位，则个十百位各有9 9种选择，千位有3种可能，根据乘法法则，总个数为39 93 ；根据加法法则，符合条件的整数个数为310103+310102 29+9+310109 92 2+39 93+39 93=12504=1250438 8. .1.3 无重组合例51. 1.3.1.1（无重

35、）组合例5 5、求1000!1000!的末尾有几个零。解：此问题在于求将1000!1000!分解为素数的乘积时，2 2和5 5的幂是多少。末尾零的个数应该等于2 2和5 5的幂中较小的那个数。1 110001000中5 5的倍数的数共200200个，其中有4040个5 52 2的倍数，这4040个数中有8 8个5 53的倍数，而这8 8个数中又有1 1个5 54 4的倍数，故1000!1000!分解为素数的乘积时， 5 5的幂应该是200+40+8+1=249200+40+8+1=249显然，2 2的幂必然大于249249，因此1000!1000!的末尾有249249个零。39 9. .1.3

36、 无重组合例61. 1.3.1.1（无重）组合例6 6、求能除尽14001400的正整数数目（1 1除外），其中包含多少个奇数？ 解：1400=21400=235 52 27 7，故除尽14001400的正整数分解为素数的乘积的形式应该为2 2l5 5m7 7n，其中0 0l3,0 ,0m2,02,0n1 1，但应排除l= =m= =n=0=0的情况。故满足条件的数目为( (3+1)+1)(2+1)(2+1)(1+1)(1+1)-1=21=23其中包含的奇数为(1)(1)(2+1)(2+1)(1+1)(1+1)-1=51=54040. .1.3 重复组合1. 1.3.2.2重复组合从n个不同元

37、素中，可重复选取r个不考虑顺序组合起来，其组合数F( (n, ,r) )。从重集B= =k k1 1*b1 1, k, k2 2*b2 2, , k, , kn*bn中取r个元素不考虑顺序的组合。重集B= =*b1 1, ,*b2 2,*bn 的r 组合数F( (n, ,r)=)=C C( (n+ +r-1,1,r) )证明：设n个元素b1 1, ,b2 2,bn和自然数1,2,1,2,n一一对应。于是任何组合皆可看作是一个r个数的组合c1 1, ,c2 2,cr。由于是组合，不妨认为各ci是按照大小顺序排列的，相同的ci连续排在一起，不妨设c1 1c2 2cr 。又令di= =ci+ +i-

38、1(1(i=1,2,=1,2,r) )，即d1 1= =c1 1, ,d2 2= =c2 2+1,+1,dr= =cr+ +r-1 1。因1 1cin，故1 1din+ +r-1 1，得到一个集合1,2,1,2,n+ +r-1 1的r 组合 d1 1, ,d2 2, , ,dr ( (d1 1d2 2dr) )。显然有一种c1 1, ,c2 2,cr的取法，就有一种d1 1, ,d2 2, , ,dr的取法，反之亦然，这两种取法是一一对应的，从而这两种取法是等价的。如此，从n个不同元素中可重复选取r个的组合数，和从n+ +r-1 1个不同元素中不重复选取r个的组合数是相同的，故F( (n, ,

39、r)=)=C C( (n+ +r-1,1,r) )4141. .1.3 重复组合例71. 1.3.2.2重复组合r个无区别的球放入n个有标志的盒子里，每盒的球数可多于1 1个，则共有F( (n, ,r) )种方案。例7 7、试问( (x+ +y+ +z) )4 4的展开式有多少项？证明：这是一个允许重复组合的典型问题，实质上定理1.61.6的另一种说法。由于每盒的球数不受限制，相当于重集*a1 1, ,*a2 2,*an的r 组合。解：( (x+ +y+ +z) )4 4展开式每一项都是4 4次方的，相当于从3个不同元素中可以重复的选择4 4个，或者相当于将4 4个无区别的球放到3个有标志的盒

40、子里。故展开项个数为F( (3,4)=,4)=C C( (3+4+4-1,4)=151,4)=154242. .1.3 重复组合例8、91. 1.3.2.2重复组合例8 8、某餐厅有7 7种不同的菜，为了招待朋友，一个顾客需要买1414个菜，问有多少种买法？例9 9、求n个无区别的球放入r个有标志的盒子里( (nr) )而无一空盒的方案数。解 ： 这 个 问 题 相 当 于 重 集*1, 1,*2,2,*7 7的1414组合。根据定理1.61.6知买菜的方法数为F(7,14)=(7,14)=C C(7+14(7+14-1,14)=48451,14)=4845解：由于每个盒子不能为空，故每个盒子

41、里可先放一个球，这样还剩n-r个球，再将这n-r个球防到r个盒子里，由于这时每盒的球数不受限制，相当于重集*a1 1, ,*a2 2,*ar的n-r 组合。根据定理1.61.6知，其组合数为F( (r, ,n-r)=)=C C( (r+ +n-r-1, 1,n-r)=)=C C( (n-1, 1,r-1)1)4 43. .1.3 重复组合例101. 1.3.2.2重复组合例1010、在由数0,1,90,1,9组成的r位整数所组成的集合中，如果将一个整数重新排列得到另一个整数，则称这两个整数是等价的。那么，有多少不等价的整数？如果0 0和9 9最多只能出现一次，又有多少不等价的整数？解：分析题意

42、知，一个r位整数只和所取的数字有关，与其顺序无关，因而是个组合问题。又每一整数的每一位可从0,1,90,1,9中任取，故不等价的r位整数相当于重集*0, 0,*1,1,*9 9的r 组合。根据定理1.61.6知，其组合数为F(10,(10,r)=)=C C(10+(10+r-1, 1, r)=)=C C(9+(9+r, ,r) )0 0和9 9最多只出现一次，可分为三种情况：均不出现时相当于重集B= =*1, 1,*2,2,*8 8的r 组合，组合数为F(8,(8,r)=)=C C( (r+7,+7,r) )；只出现其一，若0 0出现，相当于B的r-11组合，然后加入0 0，组合数为F(8,(

43、8,r-1)=1)=C C( (r+6,+6,r-1)1)，同理9 9出现的组合数为C C( (r+6,+6,r-1)1)；均出现一次，相当于B的r-22组合，然后加入0,90,9，组合数为F(8,(8,r-2)=2)=C C( (r+5,+5,r-2)2)，由加法法则知，符合题意的整数个数为C C( (r+7,+7,r)+2)+2 C C( (r+6,+6,r-1)+1)+C C( (r+5,+5,r-2)2)4444. .1.3 重复组合例111. 1.3.2.2重复组合例1111、求方程x1 1+ +x2 2+xn= =r的非负整数解的个数，其中n, ,r为正整数。解：设重集B= =*b

44、1 1, ,*b2 2,*bn， B的任一个r 组合 都 具 有 形 式 x1 1*b1 1, ,x2 2*b2 2,xn*bn， 其 中xi( (i=1,2,=1,2,n) )是非负整数且满足方程x1 1+ +x2 2+xn= =r 。反之，每一个满足方程x1 1+ +x2 2+xn= =r的非负整数解x1 1, ,x2 2,xn都对应重集B的一个r 组合。因此，方程x1 1+ +x2 2+xn= =r的非负整数解的个数就等于重集B的r 组合数F( (n, ,r) )。4545. .1.3 不相邻组合1.3 组合（3）1. 1.3. .3 不相邻组合从序列A= =1,2,1,2,n个中选取r

45、个，其中不存在i, ,i+1+1两个相邻的数同时出现于一个组合的组合。从序列A= =1,2,1,2,n个中选取r个作不相邻的组合，其组合数为C C( (n-r+1,+1,r) )证明：设d1 1, ,d2 2, , ,dr是所求的一个不相邻组合，不妨设d1 1d2 2dr。令ci= =di-i+1(+1(i=1,2,=1,2,r) )，即c1 1= =d1 1, ,c2 2= =d2 2-1,1,cr= =dr-r+1+1。因1 1din，故1 1cin-r+1+1，得到一个集合1,2,1,2,n-r+1+1的r 组合。显然有一种d1 1, ,d2 2, , ,dr的取法，就有一种c1 1,

46、,c2 2,cr的取法。反之亦然，集合1,2,1,2,n-r+1+1的一个r 组合c1 1, ,c2 2,cr，不妨设c1 1 c2 2 cr。 令 di= =ci+ +i-1(1(i=1,2,=1,2,r) )， 即 d1 1= =c1 1, ,d2 2= =c2 2+1,+1,dr= =cr+ +r-1 1。因1 1cin-r+1+1，故1 1din，得到一个集合1,2,1,2,n的不相邻组合d1 1, ,d2 2, , ,dr 。显然有一种c1 1, ,c2 2,cr的取法，就有一种d1 1, ,d2 2, , ,dr的取法。故这两种取法是一一对应的，从而这两种取法是等价的。从n个不同元

47、素中可选取r个的不相邻组合数，和从n-r+1+1个不同元素中选取r个的组合数是相同的，即C C( (n-r+1,+1,r) )。4646. .1.4 二项式定理证明：因为( (x+ +y) )n=(=(x+ +y)( )(x+ +y)()(x+ +y) )，等式右端有n个因子，项xk kyn-k k是从这n个因子中选取k k个因子，k k=0,1,=0,1,n。在这k k个( (x+ +y) )里都取x，而从剩下的n-k k个因子( (x+ +y) )中选取y作乘积得到，因此xk kyn-k k的系数为上述选法的个数C C( (n, ,r) )。故有证毕。注：可用数学归纳法证明，证明略；C C

48、( (n, k, k) )又称二项式系数。4747. .1.4 二项式定理推论1推论1.9.11.9.1：推论1.9.21.9.2：推论1.9.1.9.3：证明：在推论1.9.21.9.2中令x=1=1，即可得证。利用组合分析，等式左端相当于从A= =an中任意选择k k(0(0k kn) )个元素的所有可能数目，即对n个元素，每一个都有被选择和不被选择的可能，总的可能数为2 2n。另外，该等式还表明A的所有子集个数为2 2n。4848. .1.4 二项式定理推论2推论1.9.11.9.1：推论1.9.21.9.2：推论1.9.1.9.3：推论1.9.41.9.4：证明：在推论1.9.21.9

49、.2中令x= =-1 1，即可得证。另外，该等式还表明A= =an的偶数子集个数和奇数子集个数相等。4949. .1.4 广义二项式定理广义二项式系数为：牛顿二项式定理：5050. .1.4 广义二项式定理推论1推论1.10.11.10.1：推论1.10.21.10.2：证明：5151. .1.4 广义二项式定理推论2推论1.10.11.10.1：推论1.10.21.10.2：推论1.10.1.10.3：推论1.10.41.10.4：推论1.10.51.10.5：证明：当=1/2=1/2时，C C( (,0)=1,0)=1，而对于k k0 0，有将上式代入推论1.10.11.10.1即可得证。

50、5252. .1.4 广义二项式定理推论3推论1.10.11.10.1：推论1.10.21.10.2：推论1.10.1.10.3：推论1.10.41.10.4：推论1.10.51.10.5：推论1.10.61.10.6：5 53. .1.5 组合恒等式及其含义1恒等式1 1：如n, ,k kN，有C C( (n,k ,k)=()=(n/ /k k) )C C( (n-1, 1,k k-1)1)证明：从n个元素中取k k个的组合可先从n个元素中取1 1个，再从剩下的n-1 1个元素中选择k k-1 1个，组合数为C C( (n-1, 1,k k-1)1)。选出的k k个元素都有可能被第一次选中，

51、因是组合，故重复度为k k。得证。或通过计算证明：5454. .1.5 组合恒等式及其含义2恒等式2 2：证明：考虑盒子1 1中有n个有区别的球，从中取一个球放入盒子2 2中，再取任意多个球放入盒子3中。等式左端表示先从盒子1 1中取k k( (k k=1,2,=1,2,n) )个球，再从中取一个放入盒子2 2中，剩下的k k-1 1个球放入盒子3中。等式右端表示先从盒子1 1中取一个放入盒子2 2中，剩下的n-1 1个球是否放入盒子3中均有两种可能。显然两种取法结果是一样的。得证。或通过计算证明：5555. .1.5 组合恒等式及其含义3恒等式3：证明：将等式两边对x微分得在上式中，令x=

52、=-1 1得即得证。注：如令x=1=1，即可证明恒等式2 2。5656. .1.5 组合恒等式及其含义4、5恒等式5 5：恒等式4 4：证明：将等式两边对x微分得将等式两边同乘以x后再对x微分得在上式中，令x=1=1得得证。注：如令x= =-1 1，即可证明恒等式5 5。5757. .1.5 组合恒等式及其含义6恒等式6 6：证明：将等式两边对x从0 0到1 1积分得即得证。5858. .恒等式7 7：Vandermonde恒等式，如n, ,mN且rmin( (m, ,n) )，有C C( (m+ +n, ,r)=)=C C( (m,0),0)C C( (n, ,r)+)+C C( (m, ,

53、1)1)C C( (n, ,r-1)+1)+C C( (m, ,r) )C C( (n,0),0)1.5 组合恒等式及其含义7证明：设A= =am, ,B= =bn, ,且AB= =，则AB= =C C有m+ +n个元素。C C的r 组合个数为C C( (m+ +n, ,r) )，而C C的每个r 组合无非是先从A中取k k个元素，再从B中取出r-k k个元素组成( (k k=0,1,=0,1,r) )。由乘法法则共有C C( (m, ,k k)C()C(n, ,r-k k) )种取法，再由加法法则即可得证。或通过比较系数法证明：比较等式两边xr的系数即可得证。5959. .1.5 组合恒等式

54、及其含义8、9恒等式8 8：恒等式9 9：恒等式7 7：Vandermonde恒等式，如n, ,mN且rmin( (m, ,n) )，有C C( (m+ +n, ,r)=)=C C( (m,0),0)C C( (n, ,r)+)+C C( (m, ,1)1)C C( (n, ,r-1)+1)+C C( (m, ,r) )C C( (n,0),0)6060. .1.5 组合恒等式及其含义10、11恒等式1010：如p, ,q, ,nZ且p, ,q, ,n0 0，有 恒等式1111：如p, ,q, ,nZ且p, ,q, ,n0 0，有6161. .1.5 组合恒等式及其含义12恒等式1212：证明

55、：利用组合分析法，在集合A= =an+1+1的n+1+1个不同元素选出k k+1+1个元素的组合可分为以下多种情况：如k k+1+1个元素中包含a1 1，相当于从除去a1 1的n个元素中选出k k个元素的组合，组合数为C C( (n,k ,k) )；如不包含a1 1但包含a2 2，相当于从除去a1 1, ,a2 2的n-1 1个元素中选出k k个元素的组合，再加上a2 2而得到，组合数为C C( (n-1 1,k ,k),),同理如不包含a1 1, ,a2 2,an-k k+1+1，但包含an-k k+2+2，相当于从剩下的k k个元素中选出k k个元素的组合，再加上an-k k+2+2而得到

56、，组合数为C C( (k,kk,k) )；注意，ik k时，C C( (k,kk,k)=0)=0。由加法法则得或对固定的k k，对n使用归纳法，当n=0=0时，有可见，当n=0=0时，等式成立。如对任意n等式成立，则有可见等式对n+1+1也成立。由归纳原理，得证。6262. .1.5 组合恒等式及其含义13恒等式1 13：证明：注意，这个恒等式与前面的有一个很不一样的地方，就是C C( (+ +j j, ,j j), ),C C( (+ +k k+1,+1,k k) )是广义的二项式系数。根据广义的二项式系数的定义，Pascal公式C C( (, ,k k)=)=C C( (-1, 1,k k

57、)+)+C C( (-1, 1,k k-1)1)对实数和整数k k同样成立。与恒等式1 1类似，反复使用Pascal公式即可得证。6 63. .1.5 组合恒等式及其含义14-1恒等式1414：如n, ,rN，有C C( (n+ +r+ +1 1, ,r) )= C= C( (n+ +r, ,r)+)+C C( (n+ +r-1 1, ,r-1)+1)+C C( (n+ +1 1, ,1)1)+C+C( (n, ,0)0)证明I：反复利用Pascal公式，即可证明。或利用组合分析法，在集合A= =an+ +r+1+1的n+ +r+1+1个不同元素选出r个元素的组合可分为以下多种情况：如r个元素

58、中不包含a1 1，相当于从除去a1 1的n+ +r个元素中选出r个元素的组合，组合数为C C( (n+ +r, ,r) )；如r个元素中包含a1 1但不包含a2 2，相当于从除去a1 1, ,a2 2的n+ +r-1 1个元素中选出r-1 1个元素的组合，再加上a1 1而得到，组合数为C C( (n+ +r-1 1, ,r-1),1),同理如r个元素中包含a1 1, ,a2 2,ar-1 1，但不包含ar，相当于从剩下的n+1+1个元素中选出1 1个元素的组合，再加上a1 1, ,a2 2,ar-1 1而得到，组合数为C C( (n+1+1, ,1)1)；如r个元素中包含a1 1, ,a2 2

59、,ar，相当于从剩下的n个元素中选出0 0个元素的组合，组合数为C C( (n, ,0)0)。由加法法则得C C( (n+ +r+ +1 1, ,r) )= C= C( (n+ +r, ,r)+)+C C( (n+ +r-1 1, ,r-1)+1)+C C( (n+ +1 1, ,1)1)+C+C( (n, ,0)0)6464. .1.5 组合恒等式及其含义14-2恒等式1414：如n, ,rN，有C C( (n+ +r+ +1 1, ,r) )= C= C( (n+ +r, ,r)+)+C C( (n+ +r-1 1, ,r-1)+1)+C C( (n+ +1 1, ,1)1)+C+C( (

60、n, ,0)0)证明II：等式的左端可看作是在集合A= =an+2+2的n+2+2个不同元素允许重复的选出r个元素的组合，可分为以下多种情况：如r个元素中不包含a1 1，相当于从除去a1 1的n+1+1个元素中允许重复的选出r个元素的组合，组合数为C C( (n+ +r, ,r) )；如r个元素中只包含一个a1 1，相当于从除去a1 1的n+1+1个元素中允许重复的选出r-1 1个元素的组合，再加上a1 1而得到，组合数为C C( (n+ +r-1 1, ,r-1)1)；如r个元素中包含两个a1 1，相当于从除去a1 1的n+1+1个元素中允许重复的选出r-2 2个元素的组合，再加上两个a1

61、1而得到，组合数为C C( (n+ +r-2 2, ,r-2),2),同理如r个元素中包含r个a1 1，其组合数为C C( (n, ,0)0)。由加法法则得C C( (n+ +r+ +1 1, ,r) )= C= C( (n+ +r, ,r)+)+C C( (n+ +r-1 1, ,r-1)+1)+C C( (n+ +1 1, ,1)1)+C+C( (n, ,0)0)6565. .1.5 组合恒等式及其含义15恒等式1515：如n, ,l, ,rN, ,lr，有C C( (n, ,l) )C C( (l, ,r) )=C=C( (n, ,r) )C C( (n-r, ,l-r) )证明：等式的

62、左端可看作是先从n个元素中取l个的组合，从所得的l个元素中再选择r个组合。由此形成了三个组合，所得的全部结果相当于直接从n个元素中取r个的组合，再从剩下的n-r个元素中选择l-r个。得证。或通过计算证明：6666. .1.5 组合恒等式证明方法 数学归纳法 二项式系数公式，特别是Pascal 公式 比较级数展开式中的系数（二项式定理或母函数法） 积分微分法 组合分析法6767. .1.6 模型转换方法 分析对象属性 合理分类 明确分步 模型转换如排列 组合 计数的难易程度 方式的转换 1 1 1 111 一组（等价）6868. .1.6 模型转换例1例1 1、在100100名选手之间进行淘汰赛

63、（即一场的比赛结果，失败者退出比赛） ，最后产生一名冠军，问要举行几场比赛？证明：第1 1轮要进行5050场比赛，留下5050名选手；第2 2轮要进行2525场比赛，留下2525名选手；第3轮要进行2525场比赛，1 1名轮空，留下1 13名选手；第4 4轮要进行6 6场比赛，1 1名轮空，留下7 7名选手；第5 5轮要进行3场比赛， 1 1名轮空，留下4 4名选手；第6 6轮要进行2 2场比赛，留下2 2名选手；最后一场决赛，产生1 1名冠军。 根据加法法则，共需要进行50+25+12+6+50+25+12+6+3+2+1=99+2+1=99场比赛。其实，最后产生1 1名冠军需要淘汰9999

64、人，一场比赛淘汰1 1人，两者一一对应，需要9999场比赛进行。6969. .1.6 模型转换例2-1例2 2、简单格路问题从(0,0)(0,0)点出发沿X轴或Y轴的正方向每步走一个单位，最终走到( (m, ,n) )点，有多少条路径？解：设从(0,0)(0,0)点水平方向向前进一步为x，垂直方向向上进一步为y。于是从(0,0)(0,0)点到( (m, ,n) )点，水平方向走m步，垂直方向走n步。一条从(0,0)(0,0)点到( (m, ,n) )点的路径与重集m*x, ,n*y的一个全排列一一对应，故所求路径数为( (m+ +n)!/()!/(m! !n!)=!)=C C( (m+ +n,

65、 ,m) )。另外，垂直方向需要走n步，相当于在X轴0,1,0,1,m共m+1+1个端点处重复的选择n个位置向上走，与一条从(0,0)(0,0)点到( (m, ,n) )点的路径一一对应，故所求路径数为F( (m+1,+1,n)=)=C C( (m+ +n, ,n) )。Y(m-1, 1,n)( )(m, ,n) )(m, ,n-1)1)(0,0)(0,0)X7070. .1.6 模型转换例2-2 另外，一条从(0,0)(0,0)点到( (m, ,n) )点的路径可分为两类情况，一种是从(0,0)(0,0)点到( (m, ,n-1)1)点的路径，另一种是从(0,0)(0,0)点到( (m-1,

66、 1,n-1)1)点的路径，根据上述结论，有C C( (m+ +n, ,n)=)=C C( (m+ +n-1, 1,m)+)+C C( (m+ +n-1, 1,m-1)1)这是Pascal公式的另一种形式。例2 2、简单格路问题从(0,0)(0,0)点出发沿X轴或Y轴的正方向每步走一个单位，最终走到( (m, ,n) )点，有多少条路径？Y(m-1, 1,n)( )(m, ,n) )(m, ,n-1)1)(0,0)(0,0)X7171. .1.6 模型转换例3证明：这是上一小节的组合恒等式。等式左端表示从(0,0)(0,0)点到( (n+1,+1,r) )点的路径数，右端第1 1项表示从(0,

67、0)(0,0)点到( (n, ,r) )点的路径数，右端第2 2项表示从(0,0)(0,0)点到( (n, ,r-1)1)点的路径数，右端最后1 1项表示从(0,0)(0,0)点到( (n,0),0)点的路径数。这说明从(0,0)(0,0)点到( (n+1,+1,r) )点的路径根据是否经过( (n, ,i) )到( (n+1,+1,i)( )(i=0,1,0,1,r) )，可分为r+1+1类，根据加法法则即可得证。Y(n, ,r)( )(n+1,+1,r) ) (0,0)(0,0)(n,0),0)X例3、如n, ,rN，有C C( (n+ +r+ +1 1, ,r) )=C=C( (n+ +

68、r, ,r)+)+C C( (n+ +r-1 1, ,r-1)1)+C C( (n+ +1 1, ,1)1)+C+C( (n, ,0)0)7272. . Y P(0,(0,n)P1 1(1,(1,n-1)1) X(0,0)(0,0)Q( (n,0),0)1.6 模型转换例4例4 4、如nN，有C C( (n, ,0)0)+C+C( (n, ,1)+1)+C C( (n, ,n)=2)=2n组合含义：这是推论1.9.1.9.3。等式左端第1 1项表示从(0,0)(0,0)点到P(0,(0,n) )点的路径数，第2 2项表示从(0,0)(0,0)点到P1 1(1,(1,n-1)1)点的路径数，左端

69、最后1 1项表示从(0,0)(0,0)点到Q( (n,0),0)点的路径数。这说明从(0,0)(0,0)点到PQ上各格子点的路径总和为2 2n。也说明2 2n个人从(0,0)(0,0)点出发，每到一个十字路口便分成两组，直至到达PQ线为止，能保证每个人所走的路径不同。7 73. .1.6 模型转换例5例5 5、Vandermonde恒等式如n, ,mN, ,rmin( (m, ,n) )，有C C( (m+ +n, ,r)=)=C C( (m,0),0)C C( (n, ,r) )+C C( (m, ,1)1)C C( (n, ,r-1)1)+C C( (m, ,r) )C C( (n,0),

70、0)证明：等式左端表示从(0,0)(0,0)点到( (m+ +n-r, ,r) )点的路径数。从(0,0)(0,0)点到 ( (m+ +n-r, ,r) )点 的 每 一 条 路 径 均 穿 过 PQ线 上 的 格 子 点 ( (m-l, ,l), ),l=0,1,=0,1,r，从(0,0)(0,0)点到( (m-l, ,l) )点的路径数为C C( (m, ,l) )，再从( (m-l, ,l) )点到( (m+ +n-r, ,r) )点的路径数为C C( (n, ,r-l) )，由乘法法则，从(0,0)(0,0)点出发经过( (m-l, ,l) )点到( (m+ +n-r, ,r) )点的

71、路径数为C C( (m, ,l) )C C( (n, ,r-l) )，再由加法法则，即可得证。 YP( (m-r, ,r)()(m+ +n-r, ,r) ) (0,0)(0,0)Q( (m,0),0)X( (m-l, ,l) )7474. .1.6 模型转换例6-1例6 6、从(0,0)(0,0)点到( (m, ,n) )点( (mn) )的，要求中间经过的每一个格子点( (a, ,b) )恒满足ab关系，问有多少条路径？解：从(0,0)(0,0)点到( (m, ,n) )点的路径数为C C( (m+ +n, ,m) )，但需要排除碰到或穿过y= =x格子点的路径数，即去掉ab的情况。第一步必

72、须从(0,0)(0,0)点到(1,0)(1,0)点，因此问题等价于求从(1,0)(1,0)点到( (m, ,n) )点的路径数。因为mn，故从(0,1)(0,1)点到( (m, ,n) )点的路径必然穿过y= =x上的格子点。下面建立从(0,1)(0,1)点到( (m, ,n) )点的每一条路径，与从(1,0)(1,0)点到( (m, ,n) )点但经过y= =x上的格子点的路径时一一对应的。 Y ( (m, ,n) ) (0,1)(0,1)(0,0)(1,0)(0,0)(1,0)Q( (m,0),0)X7575. .1.6 模型转换例6-2 Y ( (m, ,n) ) (0,1)(0,1)(

73、0,0)(1,0)(0,0)(1,0)Q( (m,0),0)X 若从(0,1)(0,1)点到( (m, ,n) )点的路径与y= =x的交点从左往右数最后一个是P，作从(1,0)(1,0)点到P点关于y= =x的与上述(0,1)(0,1)点到P点的路径对称的一条路径，于是从(0,1)(0,1)点到( (m, ,n) )点的一条路径，就有一条从(1,0)(1,0)点到( (m, ,n) )点但经过y= =x上的格子点的路径与之对应。反之，一条从(1,0)(1,0)点到( (m, ,n) )点但经过y= =x上的格子点的路径，必存在一条从(0,1)(0,1)点到( (m, ,n) )点的一条路径与

74、之对应。故所求的路径数为C C( (m+ +n-1, 1,n) )-C C( (m+ +n-1, 1,n-1)=(1)=(m-n)( )(m+ +n-1)!/(1)!/(m! !n!) !)例6 6、从(0,0)(0,0)点到( (m, ,n) )点( (mn) )的，要求中间经过的每一个格子点( (a, ,b) )恒满足ab关系，问有多少条路径？7676. .第1章 小结 本章讨论了基本的组态（满足一定条件的优先集合的安排）的计数问题。主要用加法法则和乘法法则解决最基本的几种组合模型，包括排列（线排列，圆排列，重排列，项链排列）、组合（无重组合，重复组合）的计数问题。并介绍了二项式系数，广义

75、二项式系数，多项式系数，及证明的组合恒等式的几种不同证明方法。 重点是要掌握如何使用基本的组合模型来证明组合恒等式，要特别注意如何利用合理分类和组合模型的转换进行组合计数。7777. .第1章 习题P22221 1、6 6、8 8、1010、1111、1414、1616、2020、2222。7878. .回顾前一章计数：本章重点介绍鸽笼原理及其在排列组合中的（存在性）应用： 例子、意义 鸽笼原理及其推广 Ramsey定理 Ramsey数排列组合组合恒等式7979. .2.1 鸽笼原理定理鸽笼原理（抽屉原理）若把n+1+1个物体放到n （n1 1）个盒子中去，则至少有一个盒子放有至少2 2个物体

76、。证明：用反证法证明。如果n个盒子中每个盒子至多放入一个物体，则放入n个盒子中的物体总数至多为n个。这与假设有n+1+1个物体矛盾。从而定理得证。注：鸽笼原理只指出了至少存在这样的盒子，并没有给出“确定哪一个盒子有此性质的方法”，因此，它只能用来解决存在性问题。4=4+0+04=4+0+0=3+1+0+1+0=2+2+0=2+2+0=2+1+1=2+1+18080. .2.1 鸽笼原理例1、2、3例1 1、一年有36565天，今有36666个人，则其中至少有两个人生日相同。 证明：此例中把“天”当作盒子，相当于36565个盒子放入36666个物体。得证。例2 2、抽屉里有1010双相同的手套，

77、从中取1111只出来，其中至少有两只是完整配对的。 证明：此例中把“每双手套”当作盒子，相当于1010个盒子放1111个物体。得证。例3、一个教师每周上7 7次课，则这教师至少有一天要上至少2 2次课（星期天不上课除外）。 证明：此例中把“天”当作盒子，相当于6 6个盒子放7 7个物体，从而得证。8181. .2.1 鸽笼原理解释依据？方法？目的？8282. .例4 4、某次会议由n位代表参加，每一位代表至少认识其余n-1 1位中的一位，则n位代表中，至少有两位认识的人数相等（n2 2） 。 证明：n个代表认识的人数有1,2,1,2,n-1 1，相当于n-1 1盒子，根据鸽笼原理可知至少有两人

78、认识的人数相等。例5 5、某次会议由n位代表参加，每一位代表至少认识其余n-1 1位中的一位，则n位代表中，至少有两位认识的人数相等（n2 2） 。成立吗？ 证明：n个代表认识的人数只能取0,1,2,0,1,2,n-1 1。（1 1）若每一位代表至少认识其余n-1 1位中的一位，则这种情况例4 4中已经讨论。（2 2）但若有一位代表认识的人数为0 0，即此代表和其他人都不认识，则其他n-1 1人认识的人数只有0 0,1,2,1,2,n-2 2共n-1 1种可能，所以根据鸽笼原理，这种情况下也至少有两人认识的人数相等。 2.1 鸽笼原理例4、58 83. .2.1 鸽笼原理例6证明：设所取n+1

79、+1个数是a1 1, ,a2 2,an, ,an+1+1，对该序列中的每一个数去掉一切2 2的因子，直至剩下一个奇数为止，即 ri=ai/2/2x ，x=0,1,2,=0,1,2,。结果得由奇数组成的序列R：r1 1, ,r2 2,rn, ,rn+1+1。1 1到2 2n中只有n个奇数，故序列R中至少有两个数是相同的。设为，对应的有，则ai是aj j的倍数。例6 6、从1 1到2 2n的正整数中任取n+1+1个，则这n+1+1个数中至少有一对数，其中一个数是另一个数的倍数（n1 1） 。 8484. .2.1 鸽笼原理例7 7证明：构造一个序列则此时有两种可能：（1 1）若这m个和中有一个sh

80、(1(1hm) )是m 的倍数，则结论成立。（2 2）若这m个和中没有一个 是m 的倍数，则这些和被m除时必有1,2,1,2,m-1 1这样的余数。由于有m个和，且只有m-1 1个余数，于是我们可以构造m-1 1个盒子，第i个“盒子”是被m除余数为i的数，( (i=1,2,=1,2,m-1)1)。由鸽笼原理知，用m除各和时，至少有两个和的余数是相同的。则存在整数k k和l( (k kl) )，使得sk k和sl 被m除有相同的余数，即sk ksl mod m 。故例7 7、设a1 1a2 2am是正整数的序列，则至少存 在 整 数k k和 l， 1 1k k lm， 使 得 和ak k+1+1

81、+ +ak k+2+2+al是m的倍数。 （m2 2） 8585. .2.1 鸽笼原理例8例8 8、设a1 1a2 2a100100是由1 1和2 2组成的序列，已知从其中任意一个数开始的顺序1010个数的和不超过1616，即对于1 1i9191恒有ai+ +ai+1+1+ai+9+91616。则至少存在h和k k，k kh1 1，使得ah+ +ah+1+1+ak k= =39 9。证明：作序列由于每个ai都是正的整数，故而且故根据假设有做序列最后的项但序列（S）共200200项，为从1 1到199199的整数。根据鸽笼原理，其中必有两项相等。但序列（S）中前100100项为单调增，后1001

82、00项也为单调增，故存在h和k k，使则即或8686. .2.1 鸽笼原理例9例9 9、证明：把5 5个顶点放到边长为2 2的正方形中，至少存在两个顶点，它们之间的距离小于或等于。证明：把边长为2 2的正方形分成四个全等的边长为1 1的小正方形，则每个小正方形的对角线长为。如果把每个小正方形当作一个盒子，由鸽笼原理知，把5 5个顶点放到4 4个盒子中，必有一个盒子中放入了两个顶点。即必有一个小正方形中有2 2个顶点；而小正方形的对角线长为，也就是说小正方形中任意两点的最大距离为。这就证明了本题。8787. .鸽笼原理的一般形式设qi为正整数( (i=1,2,=1,2,n) )， ，如把q个物体

83、放入n个盒子中，则至少存在一个i，使得第i个盒子中至少有qi个物体。 2.2 鸽笼原理一般形式证明：用反证法证明。假设结论不成立，即对每一个i，第i个盒子至多放有ni个物体，从而这n个盒子放入物体的总数为这与矛盾。从而定理得证。8888. .2.2 鸽笼原理的推论1 1推论2.2.12.2.1：若把m个物体放到n个盒子中去，则至少有一个盒子放有不少于 ( (m-1)/1)/n +1+1个物体。 证明：用反证法证明。假设结论不成立，即对每个盒子中至多放有 ( (m-1)/1)/n 个物体， 从而这n个盒子放入物体的总数最多为n ( (m-1)/1)/n m-1 1这与假设矛盾。8989. .2.

84、2 鸽笼原理的推论2 2推论2.2.12.2.1：若把m个物体放到n个盒子中去，则至少有一个盒子放有不少于 ( (m-1)/1)/n +1+1个物体。 推论2.2.22.2.2：若把n( (r-1)+11)+1个物体放到n个盒子中去，则至少有一个盒子放有不少于r个物体。 证明：这是定理2.22.2当q1 1= =q2 2=qn= =r时的特殊情况。9090. .2.2 鸽笼原理的推论3推论2.2.2.2.3：若mi为正整数( (i=1,2,=1,2,n),),，则至少存在一个i，使得mir 。推论2.2.12.2.1：若把m个物体放到n个盒子中去，则至少有一个盒子放有不少于 ( (m-1)/1

85、)/n +1+1个物体。 推论2.2.22.2.2：若把n( (r-1)+11)+1个物体放到n个盒子中去，则至少有一个盒子放有不少于r个物体。 证明：用反证法证明。假设结论不成立，即对每个i ，mir-1 1，则这与假设矛盾。9191. .2.2 鸽笼原理推广例1-1例1 1、设A= =a1 1a2 2a2020时有1010个0 0和1010个1 1组成的某一2020位2 2进制数，B= =b1 1b2 2b2020是任意的2020位2 2进制数，先把A、B分别计入图（A）、（B）两个2020个格子，分别得（A）、（B）两种图像，并把两个B联接的4040位的2 2进制数C C= =b1 1b

86、2 2b2020 b1 1b2 2b2020，它的图像为（C C）。则存在某个i，1 1i2020，使得cici+1+1ci+19+19与a1 1a2 2a2020至少有1010位对应相等。. .ABC C第 i 格第 i +19+19格1219201219201219201219201212192011920192011920. . . . . .9292. .2.2 鸽笼原理推广例1-2证明：在C C =c1 1c2 2c4040中，当 i 遍历1,2,201,2,20时，每一个bj j, ,j=j=1,1,2,202,20，历遍 a1 1, ,a2 2,a2020。因A中有1010个0

87、0和1010个1 1，每一个bj j都有1010位次对应相等，从而当 i历遍1,2,201,2,20时，共有101020=20020=200位次对应相等。故对每个 i平均有200/20=10200/20=10位相等，因而对某个 i 至少有1010位对应相等。. .ABC C第 i 格第 i +19+19格1219201219201219201219201212192011920192011920. . . . . .9 93. .2.2 鸽笼原理推广例2例2 2、将两个大小不一的圆盘分别分成200200个相等的扇形。在大圆盘上任取100100个扇形染成红色，另外的100100个扇形染成蓝色，并

88、将小圆盘上的扇形任意染成红色或蓝色，然后将小圆盘放在大圆盘上且中心重合时，转动小圆盘可使其每一扇形都叠放于大圆盘的某一扇形内。证明：当适当转动小圆盘可使叠放的扇形对中，同色者至少100100对。 证明：设使大小两盘中心重合，固定大盘，转动小盘，则有200200个不同的位置使小盘上的每个小扇形含在大盘上的小扇形中， （将这200200种可能的位置看作200200个不同的盒子）。由于大盘上的200200个小扇形中有100100个染成红色，100100个染成蓝色，所以小盘上的每个小扇形在转动过程中，无论染成红色或蓝色，在200200个可能的重合位置上恰好有100100次与大盘上的小扇形同色（将同色的

89、扇形看作放入盒子的物体）。因而小盘上的200200个小扇形在200200个重合位置上共同色100100 200=20000200=20000次。而2000020000200(100200(100-1)+11)+1，由推论2.2.22.2.2知，存在着某个位置，使同色的小扇形数大于等于100100个。9494. .2.2 鸽笼原理推广例3例3、将1,671,67划分为个子集，必有一个子集中有一数是同子集中的两数之差（或和）。证明：设从1 1到6767的整数任意分成4 4部分p1 1, ,p2 2, ,p3, ,p4 4，作如下分析：由鸽笼原理知， 1 1到6767的整数中必有一部分，不妨设为p1

90、 1, ,至少有 (67(67-1)/41)/4 +1=17+1=17个元素。并设这1717个元素为a1 1a2 2a1717，若ai中存在一个元素是某两个元素之差，则命题得证。否则，令b1 1= =a2 2-a1 1, ,b2 2= =a3-a1 1,b1616= =a1717-a1 1，显然1 1bi6767，故bi不属于p1 1，属于p2 2, ,p3或p4 4。 同理，bi中至少有 (17(17-1)/1)/3 +1=6+1=6个元素属于p2 2，设这6 6个元素为c1 1c2 2c6 6，若ci中存在一个元素是某两个元素之差，则命题得证。否则，令d1 1= =c2 2-c1 1, ,

91、d2 2= =c3-c1 1,d5 5= =c6 6-c1 1，显然1 1di6767，且存在1 1l, ,m17,17,di= =ci-c1 1= =al-am, ,i= =1,2,1,2,5 5，故di不属于p1 1, ,p2 2，属于p3, ,p4 4。di中至少有 (6(6-1)/21)/2 +1=+1=3个元素属于p3，设这3个元素为f1 1f2 2f3，若fi中存在一个元素是某两个元素之差，则命题得证。否则，令g1 1= =f2 2-f1 1, ,g2 2= =f3-f1 1，显然1 1gi6767，且存在1 1l, ,m17,17,gi= =fi-f1 1= =al-am, ,

92、i= =1,21,2 ，故fi不属于p1 1, ,p2 2, ,p3，属于p4 4。若g1 1= =g2 2-g1 1，则命题得证。否则，令h= =g2 2-g1 1，显然1 1h6767，且同上可以证明h不属于p1 1, ,p2 2, ,p3, ,p4 4中任一个，与已知矛盾。9595. .2.2 鸽笼原理推广例4例4 4、证明：在每个包含n2 2+1+1个不同的实数的序列中，存在一个长度为n+1+1的递增子序列，或者存在一个长度为n+1+1的递减子序列。（一个序列的长度是指该序列的元素个数）。 证明：设是一个实数序列，并假设在这个序列中没有长度为n+1+1的递增子序列，则要证明一定有一个长

93、度为n+1+1的递减子序列。令表示以为首项的最长递增子序列的长度则对每个k k，由假设知道这相当于把个物品放入个盒子中，由推论2.2.22.2.2知，必有一个盒子里面至少有个物品，即存在及，使得对应于这些下标的实数序列必满足它们构成一长为的递减子序列。否则，若有某个使得 ，那么以为首项的最长递增子序列加上，就得到一个以为首项的递增子序列，由定义知，这与矛盾。因此，成立。这是一个长度为n+1+1的递减子序列，故结论成立。9696. .2.2 鸽笼原理推广例5例5 5、将1,2,101,2,10随机地摆成一圆，则必有某相邻三数之和至少是1717。 证明：设表示该圆上相邻三个数之和（i居中）。这样的

94、和共有1010个。而1,21,2,10,10中的每一个都出现在这十个和的三个之中，故由推论2.2.2.2.3知，存在一个i，使。9797. .2.3 Ramsey定理36 6个人中一定有3个人相互认识或相互不认识。证明：先考虑6 6个人中的任意一个人，不妨把这个人称作p。则其他的5 5个人可以分为下面的两个集合F和S。其中F= =与p相识的人的集合，S= =与p不相识的人的集合由鸽笼原理知，这两个集合中至少有一个集合包含有3个人。若F包含有3个人，则这3个人或者彼此不相识，或者有两个人彼此相识。如果F中有3个人彼此不相识，则结论成立。如果F中有2 2人相识，则由于这两个人都与p相识，因此有3人

95、彼此相识，故定理结论成立。类似的，如果S包含3个人，则这3个人或者彼此相识，或者有两个人彼此不相识。如果这3个人彼此相识，则结论成立。如果有两个人彼此不相识，则由于这两个人都与p也不相识，因此有3个人彼此不相识，故定理结论成立。9898. .2.3 Ramsey定理41010人中一定有4 4人相互认识或有3人相互不认识。 证明：在这1010个人中任意挑选一个人，不妨把这个人称作p。则其他的9 9个人可以分为下面的两个集合F和S。其中F= =与p相识的人的集合，S= =与p不相识的人的集合如果S中有4 4个（或4 4个以上）人，则或者这4 4个人（或4 4个人以上）或者彼此认识，或者有两个人彼此

96、不认识。如果有4 4个人彼此认识，则结论成立。如果在S中有2 2人彼此不认识，则由于这两个人都与p不认识，因此有3人彼此不认识，故定理结论成立。如果S中最多有3个人，则由鸽笼原理知，F中至少有6 6个人。由定理2. 2.3知，F中一定有3人相互认识或有3人相互不认识。如果有3个人彼此不认识，则定理成立。如果有3个人彼此认识，则把p加入，就有4 4个彼此认识的人，故定理得证。 9999. .2.3 Ramsey定理51010人中一定有4 4人相互认识或有3人相互不认识。1010人中一定有3人相互认识或有4 4人相互不认识。 证明：在定理2.42.4中，如果把“不认识”换成“认识”， “认识”换成

97、“不认识”，则有定理2.52.5，该定理的证明类似于定理2.42.4。100100. .2.3 Ramsey定理62020个人中一定有4 4个人相互认识或相互不认识。证明：在这2020个人中任意挑选一个人，不妨把这个人称作p。则其他的1919个人可以分为下面的两个集合F和S。其中F= =与p相识的人的集合，S= =与p不相识的人的集合由鸽笼原理知，这两个集合中至少有一个包含（至少）1010个人。如果F中有1010个（或1010个以上）人，则或者这1010个人（或1010个人以上）有3个人相互认识，或者有4 4个人彼此不认识。如果有4 4个人彼此不认识，则结论成立。如果有3人彼此认识，则由于这3

98、个人都与p认识，因此有4 4人彼此认识，故定理结论成立。如果S中有1010个（或1010个以上）人，则或者这1010个人（或1010个人以上）有3个人相互不认识，或者有4 4个人彼此认识。如果有4 4个人彼此认识，则结论成立。如果有3人彼此不认识，则由于这3个人都与p不认识，因此有4 4人彼此不认识，故定理结论成立。101101. .2.3 Ramsey推论1-1推论2. 2.3.1 .1：用图形表示这个定理，上述定理可描述为：对平面上的6 6个点用实线或虚线连结成的完全图中，其中实线表示这一对人互相认识，虚线表示这对人彼此不认识，或者存在一个实线三角形或者存在一个虚线三角形。这种三角形称之为

99、纯三角形。 102102. .2.3 Ramsey推论1-2推论2. 2.3.1 .1：用图形表示这个定理，上述定理可描述为：对平面上的6 6个点用实线或虚线连结成的完全图中，其中实线表示这一对人互相认识，虚线表示这对人彼此不认识，或者存在一个实线三角形或者存在一个虚线三角形。这种三角形称之为纯三角形。 类似可推广为纯n角形，或纯红、蓝色的n角形。即所有的边都是实线（或虚线、红色、蓝色）构成的n个顶点的完全图。10103. .第2章 小结（1） 本章讨论了鸽笼原理及其推广， Ramsey 数及其性质，Ramsey定理以及一些有趣的应用。鸽笼原理是重要的组合基本原理之一。重点是：（1 1）鸽笼原

100、理的正确使用。这是需要一定的技巧的，关键在于认清“鸽子”（放进盒子的物体）并制造“鸽笼”。而制造“鸽笼”的依据是：“待证命题成立，蕴涵有两只鸽子在同一鸽笼”。104104. .第2章 小结（2）（2 2）鸽笼原理的加强形式有多种说法，其中关于算术平均的说法应用尤广，它告诉我们，当m/ /nr时，若把m个物体放入n个盒子，那么至少有一个盒子有r+1+1个物体。运用它解题的关键仍然是正确的设置“盒子”。105105. .第2章 小结（3）（3） Ramsey定理Ramsey定理的性质可以概述为“任何一个足够大的结构中必定包含有一个给定大小的规则子结构”。在解有关Ramsey定理及其应用的问题时，最

101、重要的是正确理解定理意义，特别是r=2=2时定理的几种形象的说法。在解题时，则要正确地设计一个集合，该集合分成哪几个部分，正确的确定a1 1, ,a2 2,am以及r分别体现在哪些已知量或已知事实中。如果从更高的角度看问题，有关鸽笼原理和Ramsey定理的应用问题的解法都是模型化归方法。即把实际问题化归到“鸽子，鸽笼”的模式，化归到“一个集合的r 子集分类”的模式的方法。106106. .回顾前一章鸽笼原理： 本章重点介绍容斥原理及其在排列组合中的应用： 容斥原理 重集的r 组合 错排问题 有限制排列与棋盘多项式基本形式推广定理Ramsey定理107107. .3.1 基本技术定律3.1.1.

102、1.1引论 SA SAB 容斥原理（包含排除原理）通过研究若干有限集合的交与并等基本运算，解决实际中的计数问题。主要依据： 若A为S 的子集，则，。 De Morgan定律：若A、B为S的子集，则注：De Morgan定律可推广到n个有限子集。108108. .3.1 容斥原理定理1-13.1.2.1.2计数定理可用Venn图说明该定理的正确性。或通过组合分析法，若A代表具有性质a的元素集合，B代表具有性质b的元素集合，等式左端表示至少具有性质a、b之一的元素个数，|A|表示具有性质a的元素个数，|B|表示具有性质b的元素个数，但二者相加时，同时具有性质a、b的元素计数重复加了一次，故需要减去

103、重复的数|AB|。注：加法法则相当于该等式AB= =的一个特例。109109. .3.1 容斥原理定理1-23.1.2.1.2计数定理同样可用Venn图说明该定理的正确性。该等式表示同时不具有性质a、b的元素个数的计数方法。同时不具有性质a、b的元素个数应该在全集S中去掉|A|和|B|，但此时同时具有性质a、b的元素计数重复减了一次，故需要加上重复的数|AB|。110110. .3.1 容斥原理定理23.1.2.1.2计数定理111111. .3.1 容斥原理例13.1.2.1.2计数定理例1 1、一个学校只有三门课程：数学、物理、化学。已知修这三门科的学生分别有170170、1 130 0、

104、120120人；同时修数学物理两门课的学生有4545人；同时修数学、化学的2020人；同时修物理、化学的2222人；同时修三门科的学生3人。问这学校有多少学生？解：令M为修数学课的学生集合，P为修物理课的学生集合，C C为修化学课的学生集合。据题意有|M|=170=170，|P|=120=120，|C C|=1=130 0，|MP|=45=45，|PC C|=22=22，|C CM|=20=20，|MPC C|= =3 ， 则该学校的学生数为|MPC C|= =|M|+ +|P|+ +|C C|-|MP|-|PC C|-|C CM|+ +|MPC C|= =336 6112112. .3.1

105、容斥原理定理33.1.1.3 容斥原理若Ai ( (i=1,2,=1,2,n) ) S，且Ai是S中具有性质pi的元素的子集，则S中不具有性质pi ( (i=1,2,=1,2,n) )的元素的个数为：证明：可以利用数学归纳法证明。或用组合分析方法如下：为证明等式成立，只需证明等式右端不具有性质pi ( (i=1,2,=1,2,n) )的元素被计算的次数净值为1 1，而至少具有性质pi 中之一的元素被计算的次数净值为0 0即可。考虑S中一个不具有n个性质中任何一个性质的元素x，因为x Ai( (i=1,2,=1,2,n) )，故x被计算的次数净值为1 1-0+00+0-(-1)1)n=1=1。考

106、虑S中一个恰好具有n个性质中的m(1(1mn) )个性质的一个元素y，由于y S ，故在S中被计算的次数为C C( (m,0),0)；又由于y恰好具有m个性质，故它是Ai( (i=1,2,=1,2,n) )中的m个集合的元素，因而在中被计算的次数为C C( (m,1),1)；又因为在m个性质中取出一对性质的方法有C C( (m,2),2)个，故y是C C( (m,2),2)个集合AiAj j( (ij j) )的一个元素，在中被计算的次数为C C( (m,2),2)，因此y在等式右端被计算的次数净值C C( (m,0),0)-C C( (m,1)+,1)+C C( (m,2)+(,2)+(-1

107、)1)nC C( (m, ,n) )，由于mk k时，C C( (m, ,k k)=0)=0，有C C( (m,0),0)-C C( (m,1)+,1)+C C( (m,2)+(,2)+(-1)1)nC C( (m, ,n)=)=C C( (m,0),0)-C C( (m,1)+,1)+C C( (m,2)+(,2)+(-1)1)mC C( (m, ,m)=0)=0。因此y具有n个性质中至少一个性质时，被计算的次数净值为0 0。 定理得证。11113. .3.1 容斥原理定理43.1.1.3 容斥原理若Ai ( (i=1,2,=1,2,n) ) S，且Ai是S中具有性质pi的元素的子集，则S中

108、至少具有性质pi ( (i=1,2,=1,2,n) )的一个性质的元素个数为：证明：由于集合是S中至少具有n个性质中一个性质元素所组成的子集，所以有代入上述定理，即可得证。114114. .3.1 容斥原理例23.1.1.3 容斥原理例2 2、求a, ,b, ,c, ,d, ,e, ,f六个字母的全排列中不允许出现ace和df图像的排列数。解：令S为这六个字母的全排列集合，A为ace作为一个元素出现的排列集合，B为df作为一个元素出现的排列集合。根据题意有|S|=6!=6!，|A|=4!=4!，|B|=5!=5!，|AB|= =3! !，根据容斥原理，不允许出现ace和df的排列数为11511

109、5. .3.1 容斥原理例33.1.1.3 容斥原理例3、求从1 1到500500的整数中被3或5 5除尽的数的个数。解：令A为1 1500500中能被3除尽的整数集合，B为1 1500500中能被5 5除尽的整数集合。根据题意有根据容斥原理，从1 1到500500的整数中被3或5 5除尽的数的个数为116116. .3.1 容斥原理例43.1.1.3 容斥原理例4 4、求有a, ,b, ,c, ,d四个字符构成的n位符号串中，a, ,b, ,c至少出现一次的符号串的数目。解：令S为四个字符的所有n位符号串集合，A, ,B, ,C C分别为n位符号串中不出现a, ,b, ,c的集合。根据题意有

110、根据容斥原理， a, ,b, ,c至少出现一次的符号串数目为117117. .3.1 容斥原理例53.1.1.3 容斥原理例5 5、求不超过120120的素数个数。解：设S= =1,2,1201,2,120，因为10102 212012011112 2，故120120以内的合数必然是2, 2,3,5,7,5,7的倍数，令Ai为120120以内数i的倍数集，i=2,=2,3,5,7,5,7，有根据容斥原理，有但该计算过程排除了素数2, 2,3,5,7,5,7，又包含1 1这个非合数，故所求120120以内的合数数目为27+427+4-1=1=30 0118118. .3.1 容斥原理例63.1.

111、1.3 容斥原理例6 6、用2626个英文字母做不允许重复的全排列，要求排除dog, ,god, ,gum, ,depth, ,thing字样的出现，求满足这些条件的排列数。解：设S为2626个字母的全排列集，令Ai分别为出现dog, ,god, ,gum, ,depth, ,thing的排列集，i=1,2,=1,2,3,4,5,4,5。出现dog的排列，可把dog作为一个元素看，|A1 1|=24!=24!，同理|A2 2|= =|A3|=24!=24!，|A4 4|= =|A5 5|=22!=22!。因dog, ,god不可能同时出现，故|A1 1A2 2|=0=0，同理|A2 2A3|=

112、 =|A1 1A4 4|=|A1 1A5 5|=0=0，gum, ,dog可以在dogum中同时出现，故|A3A1 1|=22!=22!，同理|A2 2A4 4|= =|A3A4 4|= =|A5 5A2 2|= =|A5 5A3|=20!,=20!,|A4 4A5 5|=19!=19!。同理|A1 1A2 2A3|= =|A1 1A2 2A4 4|= =|A1 1A2 2A5 5| = =|A2 2A3A4 4|= =|A2 2A3A5 5|= =|A1 1A4 4A5 5|= =|A1 1A3A4 4|= =|A1 1A3A5 5|= =|A2 2A4 4A5 5|=0=0，|A3A4 4

113、A5 5|=17!=17!，其他4 4个、5 5个子集的交集均为空集。根据容斥原理，所求的排列数为26!26!-324!24!-22!+422!+420!+19!20!+19!-17!17!119119. .3.1 容斥原理例73.1.1.3 容斥原理例7 7、欧拉函数 ( (n) )是求小于n且与n互素的自然数的个数。 ( (nN) )求欧拉函数表达式。解：对任一大于1 1的正整数n都可惟一地分解为其中p1 1p2 2pk k都是不超过n的素数，且1 1, ,2 2,k k都是正整数。设S= =1,2,1,2,n， Ai为S中能被pk k整除的子集，i=1,2,=1,2,k k。显然有|S|

114、= =n, ,|Ai|= =n/ /pi,(,(i=1,2,=1,2,k k),),|AiAj j|= =n/( /(pi pj j),(),(i, ,j j=1,2,=1,2,k k; ij j),),|A1 1A2 2 Ak k|= =n/( /(p1 1p2 2pk k) )，根据容斥原理，有120120. .3.1 容斥原理例83.1.1.3 容斥原理例8 8、某校甲班共有学生6060名，其中2424个学生喜爱数学，2828个学生喜爱物理，2626个学生喜爱化学，1010个学生既喜爱数学又喜爱物理，8 8个学生既喜爱数学又喜爱化学，1414个学生既喜爱物理又喜爱化学，6 6个学生对这三

115、门学科都喜爱，问有多少学生对这三门学科都不喜爱？解：设S为6060名学生的集合，令M为喜欢数学课的学生集合，P为喜欢物理课的学生集合，C C为喜欢化学课的学生集合。根据题意有|S|=60=60，|M|=24=24，|P|=28=28，|C C|=26=26，|MP|=10=10，|PC C|=14=14， |C CM|=8=8， |MPC C |=6=6，根据容斥原理，则该班级三门学科都不喜欢的学生数为|S|-( (|M|+ +|P|+ +|C C|)+()+(|MP|+ +|PC C|+ +|C CM|) )-|MPC C |=8=8121121. .3.1 容斥原理例93.1.1.3 容斥

116、原理例9 9、求从1 1到10001000的整数中不能被5 5，6 6和8 8中任何一个整除的整数个数。解：用lcma1 1, ,a2 2,an表示n个整数a1 1, ,a2 2,an的最小公倍数。设S= =1,2,10001,2,1000，令A, ,B, ,C C分别为1 110001000中能被5,6,85,6,8除尽的整数集合。显然，其补集代表不具备被整除性质的集合。根据题意有根据容斥原理，不能被5,6,85,6,8中任何一个数整除的数目为122122. .3.1 容斥原理例103.1.1.3 容斥原理例1010、把n本不同的书放入m个有编号的箱子中去（nm) )，使得没有一个箱子为空。

117、共有多少种方法？解：设S表示n本不同的书任意放入m个有编号的箱子里的所有方法的集合，显然|S|= =mn 。令pi( (i=1,2,=1,2,m) )表示箱子i为空这一性质，Ai( (i=1,2,=1,2,m) )表示S中具有性质pi的元素组成的集合。则 表示没有一个箱子为空的元素集合。Ai表示箱子i为空，n本书只能放入其他m-1 1个箱子里，|Ai|=(=(m-1)1)n ( (i=1,2,=1,2,m) )。而AiAj j表示箱子i和箱子j j为空的方法，有|AiAj j|= =( (m-2)2)n ( (i, ,j j=1,2,=1,2,m;ij j) )。一般地，m个箱子里取k k个箱

118、子为空的组合i1 1, ,i2 2,ik k 有( (k k=1,2,=1,2,m) )。而对于k k=1,2,=1,2,m，在m个箱子里取k k个箱子共有 方法。由乘法法则和容斥原理即可得12123. .3.2 重集组合在1. 1.3中介绍了重集B= =k k1 1*b1 1, k, k2 2*b2 2, , k, , kn*bn在重数k ki=( (i=1,2,=1,2,n) )与在重数k kir( (i=1,2,=1,2,n) )时的r 组合数是相同的，下面以实例说明当重集B的元素具有任意给定的重数时，利用容斥原理求B的r 组合数。124124. .解：构造重集B= = *a, , *b

119、, , *c, , *d，令B 的所有1212组合构成的集合为S，有|S|= =F(4,12)(4,12)。令A为至少出现5 5个a的组合构成的集合，B为至少出现4 4个b的组合构成的集合， C C为至少出现5 5个c的组合构成的集合，D为至少出现6 6个d的组合构成的集合。由于A中的每一个1212组合至少含有5 5个a，故这样的一个组合相当于B 的一个77组合，反之， B 的一个77组合加上5 5个a就得到了A的一个1212组合。这两种选法是一一对应的。故|A|= =F(4,7)(4,7)，同理有|B|= =F(4,8)(4,8)，|C C|= =F(4,7)(4,7)，|D|= =F(4,

120、6)(4,6)。类似的分析可得|AB|= =F(4,(4,3) )，|AC C|= =F(4,2)(4,2)，|AD|= =F(4,1)(4,1)，|BC C|= =F(4,(4,3) )，|BD|= =F(4,2)(4,2)，|C CD|= =F(4,1)(4,1)，|ABC C|= =|ABD| = =|AC CD|= =|BC CD|= =|ABC CD|=0=0。根据容斥原理，B的1212组合数为455455-(120+162+120+84)+(20+10+4+20+4+10)=(120+162+120+84)+(20+10+4+20+4+10)=34 43.2 重集组合例1例1 1、

121、求重集B= =4 4*a, ,3*b, ,4 4*c, ,5 5*d r 组合数，其中r=12=12。r = =1 13？125125. .3.3 错排问题定理5如a1 1, ,a2 2,an为1,2,1,2,n的一排列，对所有的i，有aii，称这种排列为错排Dn 。当n1 1时，Dn= =n!(1!(1-1/1!+1/2!1/1!+1/2!-1/ 1/3!+(!+(-1)1)n/ /n!)!)= =n! !-C C( (n,1)(,1)(n-1)!+1)!+C C( (n,2)(,2)(n-2)!+(2)!+(-1)1)nC C( (n, ,n) )解：令1,2,1,2,n的所有排列的集合为

122、S，有|S|= =n! !。令Ai( (i=1,2,=1,2,n) )为具有性质ai= =i的排列的集合。因为错排是具有性质aii的排列，故有 。Ai表示数字i位置不动的排列集合，相当于其他n-1 1个数字的全排列，|Ai|=(=(n-1)!(1)!(i=1,2,=1,2,n) )。而AiAj j表示数字i和数字j j在原位置的排列，有|AiAj j|=(=(n-2)!(2)!(i, ,j j=1,2,=1,2,n;ij j) )。一般地，n个数字中有k k个数字i1 1, ,i2 2,ik k在原位置的排列有 ( (k k=1,2,=1,2,n) )。而对于k k=1,2,=1,2,n，在n

123、个数字中取k k个共有方法。由乘法法则和容斥原理得注：为定理3. .3 性质对称即只依赖于子集个数的推广。126126. .3.3 错排问题例1例1 1、数1,2,1,2,3,9,9的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。 解：偶数位置不动，相当于求1, 1,3,5,7,9,5,7,9五个数字的错排，所求的排列数为D5 5=5!(1=5!(1-1/1!+1/2!1/1!+1/2!-1/ 1/3!+1/4!+1/4!-1/5!)=441/5!)=44127127. .3.3 错排问题例2例2 2、在8 8个字母A, ,B,C,C,D, ,E, ,F, ,G, ,H的全排列

124、中，求使A,C,C,E, ,G四个字母不在原来位置上的错排数目。 解：令S为的8 8个字母的全排列的集合，有|S|=8!=8!。令Ai( (i=1,2,=1,2,3,4),4)分别表示A,C,C,E, ,G在原位置的排列的集合。显然，|Ai|=7!,(=7!,(i=1,2,=1,2,3,4),4)，|AiAj j |=6!,(=6!,(i, ,j j=1,2,=1,2,3,4 ,4;ij j) )，（参照定理3.5 .5的证明过程）。由乘法法则和容斥原理得128128. .3.3 错排问题例3例3、求8 8个字母A, ,B,C,C,D, ,E, ,F, ,G, ,H的全排列中只有4 4个元素不

125、在原来位置上的排列数。 解：8 8个字母中只有4 4个不在原来的位置上，其余4 4个不动，相当于4 4个数字的错排，首先在8 8个字母中选出4 4个不动的数字，再作其他4 4个数字的错排。根据乘法法则，所求的排列数为C C(8,4)(8,4) D4 4=6=630 0129129. .3.3 错排问题例4例4 4、求1,2,1,2,n的全排列中，正好只有r(0(0rn) )个元素在原来位置上的排列个数。 解：从1,2,1,2,n中取r个数有C C( (n, ,r) )种方式，选定r个数后，剩下的n-r个数不在原来的位置上，相当于n-r个数字的错排，根据乘法法则，所求的排列数为C C( (n,

126、,r) )Dn-r1 130 0. .3.3 错排问题例5例5 5、设有n册书分给n个学生，之后又将这n册书收回重新分给这n个学生。问有多少方式分配这n册书使得没有一个学生两次得到同一册书? 解： n册书可以用n! !种方式第一次分给n个学生。对第二次分配，据题意，这是一个n册书的错排。由乘法法则，所求的方式数为n! !Dn1 131 1. .3.3 错排问题推论1推论3.5.1.5.1：证明： 由于e-1 1可以表成下列的无穷级数：故即1 132 2. .3.3 错排问题推论2推论3.5.2.5.2：Dn=(=(n-1)(1)(Dn-1 1+ +Dn-2 2) )推论3.5.1.5.1：证明

127、： 1,2,1,2,n的错排可以分为两种互不相容的类型。对于k k 2, 2,3,n，令a1 1= =k k, ,ak k=1=1。由于a1 11 1，故选取a1 1的方法有n-1 1种。而a1 1= =k k, ,ak k=1=1的值已定，故将剩下的n-2 2个数进行错排，由乘法法则，这种类型的错排列数为( (n-1)1)Dn-2 2。对于k k 2, 2,3,n，令a1 1= =k k, ,ak k1 1。选取a1 1的方法仍有n-1 1种。由于a1 1= =k k已定，且ak k1 1，故将剩下的n-1 1个数2, 2,3,k k-1, 1,1 1, ,k k+1,+1,n进行错排（此时

128、将1 1看作k k），由乘法法则，这种类型的错排数为( (n-1)1)Dn-1 1。由于这两种类型互不相容，由加法法则有Dn=(=(n-1)(1)(Dn-1 1+ +Dn-2 2) )1 133. .3.4 有限制排列概念如a1 1, ,a2 2,an为1,2,1,2,n的一排列，计算其不允许出现12,212,23,(,(n-1)1)n的全排列个数，即相对位置有限制的排列数，记为Qn 。注：错排计算的是绝对禁用位置；有限制排列讲的是相对禁用位置 。3.4.1.4.1有限制排列 1 134 4. .3.4 有限制排列定理6当n1 1时，有Qn= =n! !-C C( (n-1,1)1,1)( (

129、n-1)!+1)!+C C( (n-1,2)1,2)( (n-2)!+(2)!+(-1)1)n-1 1C C( (n-1, 1,n-1)1)1!1!3.4.1.4.1有限制排列 证明：令1,2,1,2,n的所有排列集合为S，有|S|= =n! !。令Ai( (i=1,2,=1,2,n-1)1)为具有形式i( (i+1)+1)的排列的集合，故有 。由于Ai表示具有形式i( (i+1)+1)的排列的集合，相当于i( (i+1)+1)作为一个元素出现，|Ai|=(=(n-1)!(1)!(i=1,2,=1,2,n-1)1)。而AiAj j可分为（不妨设ij j）：i+1=+1=j j，相当于i( (i

130、+1)(+1)(i+2)+2)作为一个元素出现；i+1+1j j ，相当于i( (i+1)+1)、j j( (j j+1)+1)分别作为一个元素出现，均有|AiAj j|=(=(n-2)!(2)!(i, ,j j=1,2,=1,2,n-1 1;ij j) )。一般地，n个数字中有k k个数字i1 1, ,i2 2,ik k具有形式ij j( (ij j+1)(+1)(j j=1,2,=1,2,k k;k k=1,2,=1,2,n-1)1)，相当于n-k k个元素的排列，有 。而对于k k=1,2,=1,2,n，在n-1 1个数字中取k k个共有方法。由乘法法则和容斥原理得1 135 5. .3

131、.4 有限制排列定理7当n2 2时，Qn= =Dn+ +Dn-1 1 。3.4.1.4.1有限制排列 1 136 6. .3.4 有限制排列例1例1 1、有n名儿童围坐在一个旋转木马上，问有多少种方式改变他们的座位，使得每个儿童有一个不同的儿童坐在他们前面。 3.4.1.4.1有限制排列 解：令1,2,1,2,n的所有圆排列的集合为S，有|S|=(=(n-1)!1)!。令Ai( (i=1,2,1,2,n) )为具有形式i( (mod( (i+1,+1,n)的圆排列的集合， 故所求为方式数为 。由于Ai表示具有形式i( (mod( (i+1,+1,n) )的圆排列的集合，相当于i( (mod(

132、(i+1,+1,n) )作为一个元素出现，|Ai|=(=(n-2)!(2)!(i=1,2,=1,2,n) )。而AiAj j可分为( (不妨设ij j) )：mod( (i+1,+1,n)=)=j j，相当于i( (mod( (i+1,+1,n)()(mod( (i+2,+2,n) )作为一个元素出现；mod( (i+1,+1,n) )j j ，相当于i( (mod( (i+1,+1,n),),j j( (mod( (j j+1,+1,n)分别作为一个元素出现，均有|AiAj j|=(=(n-3)!()!(i, ,j j=1,2,=1,2,n;ij j) )。一般地，n个数字中有k k个数字i

133、1 1, ,i2 2,ik k具有形式i( (mod( (i+1,+1,n)()(j j=1,2,=1,2,k k;k k=1,2,=1,2,n) )，相当于n-k k个元素的圆排列，有 。而对于k k=1,2,=1,2,n，在n个数字中取k k个共有方法。由乘法法则和容斥原理得1 137 7. .3.4 有限制排列例2例2 2、求集合A= =a, ,b, ,c, ,d, ,e, ,f, ,g, ,h的全排列中，abc和efgh均不出现的全排列个数。 3.4.1.4.1有限制排列 解：设S为集合A的所有全排列的集合，令A1 1, ,A2 2分别表示出现abc和efgh的排列集合。根据题意有|S

134、|=8!=8!，A1 1的排列相当于集合abc, ,d, ,e, ,f, ,g, ,h的排列，有|A1 1|=6!=6!，同理|A2 2|=5!=5!，|A1 1A2 2|= =3! !。根据容斥原理，所求的全排列个数为|S|-( (|A1 1|+ +|A2 2|)+)+|A1 1A2 2|= =3948694861 138 8. .3.4 有限制排列例3例3、在重集4 4*x, ,3*y, ,2 2*z的全排列中，求不出现xxxx、yyy、zz图像的排列数。 3.4.1.4.1有限制排列 解：设S为重集合的所有全排列的集合，令A1 1, ,A2 2, ,A3分别表示出现xxxx, ,yyy,

135、 ,zz的排列集合。根据题意有|S|=9!/(2!=9!/(2!3!4!)!4!)，A1 1的排列相当于集合X, ,3*y,2 ,2*z（把4 4个x看作一个X）的排列，有|A1 1|=6!/(2!=6!/(2!3!) !)，同理|A2 2|=7!/(4!2!)=7!/(4!2!)， |A3|=8!/(4!=8!/(4!3!) !)，|A1 1A2 2|=4!/2!=4!/2!，|A2 2A3|=6!/4!=6!/4!，|A3A1 1|=5!/=5!/3! !， |A1 1A2 2A3|= =3! !。根据容斥原理，所求的全排列个数为|S|-( (|A1 1|+ +|A2 2|+ +|A3|)

136、+()+(|A1 1A2 2|+ +|A2 2A3|+ +|A3A1 1|) )-|A1 1A2 2A3|=871=8711 139 9. .3.5 棋盘排列概念3.5.1.5.1棋盘（子）多项式 n个元素的排列可看作n个棋子（車車）在nn棋盘C C上的一种布局，布子规定称无对攻规则，即同一行（列）有且仅有一个棋子。 棋盘C C可推广为任意形状，令rk k( (C C) )表示k k个棋子布列棋盘C C上的方案数，称 为棋盘C C的棋盘多项式，规定r0 0( (C C)=1)=1，包括C C= =时。如r1 1( ( )=1)=1，r1 1( )=2=2，r1 1( )=2=2，r2 2( )

137、=1=1R( ( )=1+)=1+x， R( )=1+2=1+2x， R( )=1+2=1+2x+ +x2 2140140. .3.5 棋盘排列加法3.5.1.5.1棋盘（子）多项式 设C C( (i) )为C C的某一指定格子所在行与列去掉后的所得棋盘，C C( (e) )为C C是仅去掉该格子后的所得棋盘。如C C：C C( (i) )： C C( (e) )： 显然有rk k( (C C)=)=rk k-1 1( (C C( (i) )+)+rk k( (C C( (e) ) )，R( (C C)=)=xR( (C C( (i) )+)+R( (C C( (e) ) )。如R( ( )=

138、1+)=1+x， R( )= =xR( ( )+)+R( ( )=)=x+(1+(1+x)=1+2)=1+2x， R( )=xR( ( )+)+R( ( )=)=x(1+(1+x)+(1+)+(1+x)=1+2)=1+2x+ +x2 2*141141. .3.5 棋盘排列乘法3.5.1.5.1棋盘（子）多项式 设C C由相互分离的C C1 1、C C2 2组成，即C C1 1的任一格子所在的行和列中都没有C C2 2的格。有：R( (C C)=)=R( (C C1 1) )R( (C C2 2) )。如R( )= =R( ( ) )R( ( )=(1+)=(1+x)(1+)(1+x)=1+2)

139、=1+2x+ +x2 2 R( )= =xR( ()+)+R( )= =x+(1+2+(1+2x+ +x2 2)=1+)=1+3x+ +x2 2R( )= =xR( )+ +R( )= =x(1+2(1+2x)+(1+)+(1+3x+ +x2 2)=1+4)=1+4x+ +3x2 2R( )= =xR( )+ +R( )=xR( )+ +xR( )+R( )=x(1+4(1+4x+ +3x2 2)+)+x(1+(1+3x+ +x2 2)+(1+4)+(1+4x+ +3x2 2)=1+6)=1+6x+10+10x2 2+4+4x3*142142. .3.5 禁区排列概念3.5.2.5.2有禁区的

140、排列对于1,2,1,2,3,4 ,4的一个排列P= =p1 1p2 2p3p4 4，规定p1 13，p2 21,41,4，p32,42,4，p4 42 2。这样的排列对应于有禁区的布子。如右图有影线的格子表示禁区。1212344 p4 4p1 1p2 2p314143. .3.5 禁区排列定理8 83.5.2.5.2有禁区的排列有禁区的排列数为n! !-r1 1( (n-1)!+1)!+r2 2( (n-2)!+(2)!+(-1)1)nrn 。其中ri是有i个棋子布置到禁区部分的方案数。 证明：设S为n个棋子布入nn棋盘的所有排列的集合，Ai为第i个棋子布入禁区，其他棋子任意布的方案集，i=1

141、,2,=1,2,3,n。根据题意有|S|= =n! !。一个棋子落入禁区的方案数为r1 1，剩下的n-1 1棋子任意排列，故至少一个棋子落入禁区的方案数为r1 1( (n-1)!1)!。同理，两个棋子落入禁区的方案数为r2 2，剩下的n-2 2棋子任意排列，故至少两个棋子落入禁区的方案数为r2 2( (n-2)!2)!，以此类推。 根据容斥原理，无一棋子落入禁区的方案数为144144. .3.5 禁区排列例1 3.5.2.5.2有禁区的排列例1 1、有G, ,L, ,W, ,Y四位工作人员，A, ,B,C,C,D为四项任务，但G不能从事任务B，L不能从事B,C,C两项任务，W不能做C,C,D工

142、作，Y不能从事任务D。若要求每人从事各自力所能及的一项工作，试问有多少种不同方案？ A BCCDGLWY解：由题意，可得棋盘如右图，其中有阴影的格子表示禁区。由上述可知R( )=1+6=1+6x+10+10x2 2+4+4x3，即r1 1=6=6，r2 2=10=10，r3=4=4，故所求方案数为4!4!-6 63!+10!+102!2!-4=44=4*145145. .3.5 禁区排列例2 3.5.2.5.2有禁区的排列例2 2、设右图是nn棋盘，禁区都在对角线上，用n个棋子在上面布局。求如图所示的有禁区的棋盘的布局方案数。n格n格解：设棋盘中有阴影的格子为禁区C C。显然这是一个错排。由上

143、述可知R( (C C)=)=R( ( ) )n=(1+=(1+x) )n=1+=1+C C( (n,1),1)x+ +C C( (n,2),2)x2 2+C C( (n, ,n) )xn，即ri= =C C( (n, ,i) )，故所求方案数为Dn= =n! !-C C( (n,1)(,1)(n-1)!+1)!+C C( (n,2)(,2)(n-2)!+(2)!+(-1)1)nC C( (n, ,n) )注：这是错排公式的另一种推导方式。146146. .3.6 广义容斥原理概念若将3.1 .1中的例1 1所问改为“单修一门数学的学生有多少？” “只修一门课的学生有多少？”“只修两门课的学生有

144、多少？”则相应的答案表示如下：设有与性质r1 1, ,r2 2,rn相关的集合S的子集A1 1, ,A2 2,An，pk k表示至少具有k k种性质的元素的元次，qk k为恰有k k种性质的元素个数，有147147. .3.6 广义容斥原理定理9 9注：q0 0即通用的容斥原理 。证明：可以利用数学归纳法证明。或用组合分析方法如下：为证明等式成立，只需证明等式右端恰好具有k k个性质ri ( (i=1,2,=1,2,n) )的元素被计算的次数净值为1 1，而少于或多于k k个性质的元素被计算的次数净值为0 0即可。考虑S中一个恰好具有k k个性质的元素x，则其对pk k的某一项的贡献为1 1，

145、而对pk k+1+1, ,pk k+2+2,pn的贡献都是0 0。若某一元素具有的性质少于k k种，则其对pk k, ,pk k+1+1,pn的贡献都是0 0。若恰有k k+ +j j种性质，则其对pk k的贡献是C C( (k k+ +j j, ,j j) )，对pk k+ +i的贡献是C C( (k k+ +j j, ,k k+ +i) )，其中 ( (j j=1,=1,2,2,n-k k; i=1,2,=1,2,j j) )。而即恰有k k+ +j j种性质，对pk k, ,pk k+1+1,pn的贡献都是0 0。定理得证。148148. .3.6 广义容斥原理例1例1 1、某学校有12

146、12位教师，已知教数学课的教师有8 8位，教物理的教师有6 6位，教化学的教师有5 5位，其中有5 5位既教数学又教物理，有4 4位兼教数学和化学，兼教物理和化学的有3位；有3位教师教三门课，试问教数、理、化以外的课的教师有几位？只教一门课的教师有几位？正好教两门课的教师有几位？解：设全体教师集合为S，令教数学的教师属于A1 1，教物理的属于A2 2，教化学的属于A3。则p0 0=12=12，p1 1= =|A1 1|+ +|A2 2|+ +|A3|=8+6+5=19=8+6+5=19，p2 2= =|A1 1A2 2|+ +|A1 1A3|+ +|A2 2A3|=5+4+=5+4+3=12=

147、12，p3= =|A1 1A2 2A3|= =3。故教其他课的老师数为：q0 0= =p0 0-p1 1+ +p2 2-p3=12=12-19+1219+12-3=2=2恰好教一门的教师数为：q1 1= =p1 1-2 2p2 2+ +3p3=4=4恰好教两门的老师数为：q2 2= =p2 2-3p3= =3149149. .3.6 广义容斥原理例2例2 2、（n 对夫妻围坐问题二重错排）设 n 对夫妻围圈而坐，男女相间，每个男人都不和他的妻子相邻，有多少种可能的方案？解：不妨令n个女人先围成一圈，方案数为( (n-1)!1)!。对任一这种给定方案，顺时针给每个女人编号1,2,1,2,n。设第

148、i号女人顺时针与下一个女人之间的位置为第i号位置，第i号女人的丈夫的编号也为第i号，1 1in。让n个男人坐到上述编号的n个位置上。设ai是坐在第i号位置上的男人，则aii, ,i-1,21,2in，a1 1n,1 ,1。这样的限制也即要求在下面3行n列的排列中 a1 1a2 2a3an-1 1an12123n-11n n1212n-22n-1 1每列中都无相同元素。满足这样的限制的排列a1 1a2 2an称为二重错排。设二重错排的个数为Un，原问题所求的方案数就是Un( (n-1)!1)!。设Ai为ai= =i, ,i-1,21,2in，A1 1为a1 1= =n,1 ,1的排列a1 1a2

149、 2an的集合，则|Ai|=2(=2(n-1)!1)!，因为Ai表示两个位置集合，关键是计算k k个Ai的交集的排列数。考虑( (n,1)(1,2)(2,1)(1,2)(2,3)()(n-1, 1,n) )这n对数的k k 对中各取一数，且互不相同的取法的计数，这相当于从n,1,1,2,2,1,1,2,2,3, ,3,4,4,n-1, 1,n-1, 1,n中取k k个互不相邻数的组合的计数，但首尾的n不能同时取。根据前面的不相邻组合，其计数为C C(2(2n-k k+1,+1,k k) )-C C(2(2n-4 4-( (k k-2)+1,2)+1,k k-2)=2)=C C(2(2n-k k

150、, ,k k) )(2(2n)/(2)/(2n-k k) )，根据容斥原理，有150150. .第3章 小结 本章主要讨论了容斥原理及其推广定理的概念，及其在排列组合计数中的各种应用，包括：有限元重集的排列、组合、圆排列，错排、多种有限制排列等。 合理分类是计数的重要方法。在无法简单分类的情况下，要涉及有重复的分类，这就要用到容斥原理。容斥原理在某种意义上提供了计数问题的一种间接解法。不是直接计算精确的个数，而是根据容斥原理借助于交替加减一些适当的项来修正所计算的个数。正如本章的例子所表明的那样，这样一种方法常常很有效，需要重点掌握。 容斥原理解决的是有限集合的交集、并集的计数问题。重点是考察

151、对象的属性，建立相应的集合关系，并利用集合的基本运算来解决实际应用中的大量计算问题。151151. .第3章 习题P54541 1、3、7 7、1010、1212。152152. .回顾前一章容斥原理：本章重点介绍母函数（普通母函数、指数母函数）的基本概念及其在排列组合中的应用 ： 母函数的基本概念 母函数的基本运算 母函数在排列、组合中的应用 整数拆分 母函数在组合恒等式中的应用基本原理重集的r-组合错排、有限制排列15153. .4.1 普通母函数概念4.1.14.1.1普通母函数 注： f( (x) )是无穷级数，不管其收敛性；x为形式变元，f( (x) )为形式幂级数 ；序列与母函数一

152、一对应；母函数是序列的另一表达形式；有限序列也可用母函数表示；可与二项式定理结合应用 。给定一无穷序列( (a0 0, ,a1 1,an,)(,)(简记为an) )，称函数 为序列an的普通母函数（发生、生成函数） 。 154154. .4.1 普通母函数例14.1.14.1.1普通母函数 例 1 1、 求 序 列 ( (C C( (n,0),0),C C( (n,1),1),C C( (n,2),2),C C( (n, ,n) )的普通母函数。 解：由定义4.14.1及二项式定理的推论1.9.21.9.2有 155155. .4.1 普通母函数例24.1.14.1.1普通母函数 例2 2、求

153、序列( (C C( (n-1,0),1,0),-C C( (n,1),1),C C( (n+1,2),(+1,2),(-1)1)k kC C( (n+ +k k-1, 1,k k),),)的普通母函数。 解：由定义4.14.1及二项式定理的推论1.10.21.10.2有 156156. .4.1 普通母函数例34.1.14.1.1普通母函数 例3、证明(1(1-4 4x) )-1/21/2是序列( (C C(0,0),(0,0),C C(2,1),(2,1),C C(4,2),(4,2), , C C(2(2n, ,n),),)的普通母函数。 证明：由牛顿二项式定理有 由定义知，(1(1-4

154、4x) )-1/21/2是序列( (C C(0,0),(0,0),C C(2,1),(2,1),C C(4,2),(4,2), , C C(2(2n, ,n),),)的普通母函数。157157. .4.1 普通母函数例44.1.14.1.1普通母函数 例4 4、求序列(0,1(0,12 23,2,234,4,n( (n+1)(+1)(n+2),)+2),)的普通母函数。 158158. .4.1 指数母函数概念4.1.24.1.2指数母函数 注： fe( (x) )也是形式幂函数。经常可结合以下公式运算：给定一无穷序列( (a0 0, ,a1 1,an,),)（简记为an），称函数 为序列an

155、的指数母函数。 159159. .4.1 指数母函数例54.1.24.1.2指数母函数 例5 5、设n是整数，求序列( (p( (n,0),0),p( (n,1),1),p( (n, ,n) )的指数母函数fe( (x) )。 解：由定义4.24.2及公式P( (n, ,r)=)=r! !C C( (n, ,r), ),以及例1 1的结论，有 160160. .4.1 指数母函数例64.1.24.1.2指数母函数 例6 6、求序列( (p(0,0),(0,0),p(2,1),(2,1),p(4,2),(4,2),p(2(2n, ,n),),)的指数母函数fe( (x) )。 解：由定义4.24

156、.2及公式P( (n, ,r)=)=r! !C C( (n, ,r) )，以及例3的结论，有161161. .4.1 指数母函数例74.1.24.1.2指数母函数 例7 7、求序列1, 1, ,2 2,n,的指数母函数fe( (x) )。其中是实数。 解：由定义4.24.2，有 特别地：若 =1=1，则序列(1,1,1,)(1,1,1,)的指数母函数为ex 。162162. .4.1 指数母函数例84.1.24.1.2指数母函数 例8 8、求序列(1,1(1,14,14,14 47,7,1 14 47 7( (3n+1),)+1),)的指数母函数。 解：由定义4.24.2和二项式定理，有161

157、63. .4.1 母函数定理14.1.24.1.2指数母函数 设f( (x) )、fe( (x) )分别为序列an的普通、指数母函数，则 解：由指数母函数的定义4.24.2，有 将上式两边同乘以e-s并从0 0到 积分得由分部积分法有故164164. .设A( (x),),B( (x),),C C( (x) )分别是序列an, ,bn和cn的普通母函数，则C C( (x)=)=A( (x)+)+B( (x) )当且仅当ci= =ai+ +bi,(,(i=0,1,=0,1,r,),)C C( (x)=)=A( (x) )B( (x) )当且仅当 , ,( (i=0,1,=0,1,r,),)4.2

158、 母函数运算定理2165165. .4.2 母函数运算例1例1 1、设A( (x) )是序列an的普通母函数，则A( (x)/(1)/(1-x) )是序列a0 0, ,a0 0+ +a1 1,a0 0+ +a1 1+an,的普通母函数。166166. .4.2 母函数运算例2例2 2、求和的值。 167167. .4.2 母函数运算推论1推论4.2.14.2.1：168168. .4.2 母函数运算推论2推论4.2.14.2.1：推论4.2.24.2.2：169169. .4.2 母函数运算推论3推论4.2.14.2.1：推论4.2.24.2.2：推论4.2.4.2.3：见本节例1 1。170

159、170. .4.2 母函数运算推论4推论4.2.44.2.4：171171. .4.2 母函数运算推论5、6推论4.2.54.2.5：推论4.2.44.2.4：推论4.2.64.2.6：172172. .设A( (x),),B( (x),),C C( (x) )分别是序列an, ,bn和cn的指数母函数，则C C( (x)=)=A( (x)+)+B( (x) )当且仅当ci= =ai+ +bi,(,(i=0,1,=0,1,r,),)C C( (x)=)=A( (x) )B( (x) )当且仅当 , ,( (i=0,1,=0,1,r,),)4.2 母函数定理317173. .4.3 排列组合概述

160、母函数有着极其广泛的应用，从本节开始介绍母函数在某些组合数学的问题中的应用。本节介绍普通母函数在组合中的应用和指数母函数在排列中的应用，主要是计数问题，也有部分方案方法问题。考虑三个不同的物体a、b、c的选取方法。如果对选取方法的个数感兴趣，而不是对不同的选取方法感兴趣，则可令a= =b= =c=1=1，有 174174. .4.3 组合应用例14. 4.3.1.1在组合中的应用 例1 1、有红球两只，白球、黄球各一只，试求有多少种不同的组合方案。随机组合 解：设r, ,w, ,y分别代表红球，白球和黄球。由此可见，除一个球也不取的情况外，有：( (a) )取一个球的组合数为三，即分别取红，白

161、，黄，三种；( (b) )取两个球的组合数为四，即两个红的，一红一黄，一红一白，一白一黄；( (c) )取三个球的组合数为三，即两红一黄，两红一白，一红一黄一白；( (d) )取四个球的组合数为一，即两红一黄一白。令取i个球的组合数为ai，则序列a0 0, ,a1 1, ,a2 2, ,a3, ,a4 4的普通母函数为故共有1+1+3+4+4+3+1=12+1=12（或32 22 2=12=12）种组合方式。175175. .4.3 组合应用例24. 4.3.1.1在组合中的应用 例2 2、n个完全一样的球放到m个有标志的盒子中，不允许有空盒，问有多少种不同的方案？其中nm 重复组合 解：由于

162、不允许有空盒，令n个球放到m个有标志的盒子的方案数为an，序列an对应的普通母函数为f( (x) )。则176176. .4.3 组合应用例34. 4.3.1.1在组合中的应用 例3、某单位有8 8个男同志，5 5个女同志，现要组织一个由数目为偶数的男同志，和数目不少于2 2的女同志组成的小组，试求有多少种组成方式。随机组合 解：令an为从8 8位男同志中抽取出n个的允许组合数。由于要男同志的数目必须是偶数，故序列an对应的普通母函数为f( (x)=)=(1+(1+x) )8 8+(1+(1-x) )8 8/2 /2类似女同志的允许组合数对应的普通母函数为g( (x)=)=(1+(1+x) )

163、5 5-(1+5(1+5x) )令cn为为符合要求的n个人组成的小组的数目，由乘法法则，序列cn对应的普通母函数为h( (x)=)=f( (x) )g( (x)=)=(1+(1+x) )8 8+(1+(1-x) )8 8(1+(1+x) )5 5-(1+5(1+5x) )/2 /2故总的组成方式数目为12812826=26=332828。177177. .4.3 组合应用例44. 4.3.1.1在组合中的应用 例4 4、证明从n个不同的物体中允许重复 地 选 取 r个 物 体 的 方 式 数 为F( (n, ,r)=)=C C( (n+ +r-1, 1,r) )。 证明：设ar表示从n个不同的

164、物体中允许重复的选取r个物体的方式数。序列ar的普通母函数为178178. .4.3 组合应用例54. 4.3.1.1在组合中的应用 例5 5、求从n个不同物体中允许重复地选取r个物体，但每个物体出现偶数次的方式数。 解：设ar为所求的方式数。由于每个物体出现偶数次，故可用因子(1+(1+x2 2+ +x4 4+)+)示某一物体可以不选，或选取2 2次，或选取4 4次，。因此序列ar的普通母函数为179179. .4.3 组合应用例64. 4.3.1.1在组合中的应用 例6 6、在一个书架上共有1616本书，其中4 4本是高等数学，3本是普通物理，4 4本是数据结构，5 5本是离散数学。求从中

165、选取r本数的方式数，其中r=12=12。解：这实际上是求重集4 4*M, ,3*P,4 ,4*S,5 ,5*D的1212组合数。设ar是选取r本书的方式数。由于高等数学最多只能选取4 4本，普通物理最多只能选取3本，数据结构最多只能选取4 4本，离散数学最多只能选取5 5本，故序列ar的普通母函数为取f( (x) )展开式中xr的系数即为所求的方式数。当r=12=12时，x1212的系数为34 4，即 a1212= =34 4。180180. .4.3 组合应用例74. 4.3.1.1在组合中的应用 例7 7、现有2 2n个A，2 2n个B，2 2n个C C，求从它们之中选出3n个字母的不同的

166、方式数。解：这个问题实际上是求重集2 2n*A,2 ,2n*B,2 ,2n*C C的3n 组合数。设ar为所求的方式数。则序列ar的普通母函数为181181. .4.3 排列应用例84. 4.3.2.2在排列中的应用 例8 8、由1,2,1,2,3,4 ,4四个数字组成的五位数中，要求数1 1出现次数不超过2 2次，但不能不出现；2 2出现不超过1 1次；3出现次数可达3次，也可不出现；4 4出现次数为偶数。求满足上述条件的数的个数。容斥原理 解：设满足条件的r位数的个数为ar，序列ar的指数母函数为由此可见满足条件的5 5位数ar=215=215个。182182. .4.3 排列应用例94.

167、 4.3.2.2在排列中的应用 例9 9、求1, 1,3,5,7,9,5,7,9五个数字组成的n位数的个数，要求其中3,7 ,7出现的次数为偶数，其他1,5,91,5,9出现的次数不加限制。 解：设满足上述条件的r位数的个数为ar，序列ar的指数母函数为18183. .4.3 排列应用例104. 4.3.2.2在排列中的应用 例1010、证明从n个不同的物体中允许重复地选取r个物体的排列数为nr。 证明：这个问题实际上是证明重集B= =*b1 1, ,*b2 2,*bn的r 排列数为nr。设ar为所求的排列数。则序列ar的指数母函数为184184. .4.3 排列应用例114. 4.3.2.2

168、在排列中的应用 例1111、用红、白、绿三种颜色给1 1n棋盘中的正方形着色，要求偶数个正方形着红色，而着白色和绿色的正方形个数不加限制，求不同的着色方式数。 证明：若用R, ,W和G分别表示红、白和绿三种颜色，则该问题实际上是求重集B= =*R, ,*W, ,*G的n 排列数，其中要求R出现偶数次。设an为所求的排列数。则序列an的指数母函数为185185. .4.3 排列应用例124. 4.3.2.2在排列中的应用 例1212、在所有的n位数中，包含数字3,8,9,8,9，但不包含数字0,40,4的数有多少？ 解：这个问题实际上是求重集B= =*1, 1,*2, 2,*3, ,*5, 5,

169、*6, 6,*7, 7,*8,8,*9 9的n 排列数，其中要求3,8,9,8,9至少出现一次，而其他的数不加限制。设符合题意的数有an个。则序列an的指数母函数为186186. .4.3 排列应用例134. 4.3.2.2在排列中的应用 例1 13、求1,2,1,2,3,4,5,4,5五个数字组成的r位数的个数，要求其中1 1出现的次数与2 2出现的次数的和必须是偶数。 解：设an为符合题意的个数。由于1 1出现的次数与2 2出现的次数的和为偶数，可分为两种情况：1 1出现的次数与2 2出现的次数都为偶数；1 1出现的次数与2 2出现的次数都为奇数。由加法法则知，序列an的指数母函数为187

170、187. .这是母函数的应用实例之一。整数的拆分就是把整数分成若干个正整数部分，并且不考虑各部分的次序，不同的拆分方法的总数叫拆分数P( (n) )。相当于把n个无区别的球放到1 1mn个无标志的盒子中的方法数。 4.4 整数的拆分概念188188. .4.4 整数的拆分定理4设a, ,b, ,c. .为大于0 0的整数，则1/ 1/(1(1-xa)(1)(1-xb)(1)(1-xc)的级数展开式中xn的系数等于把正整数n拆分为a, ,b, ,c的和的方法数P( (n) )。证明：注意到如果项xn是由x3a, ,xb, ,x2 2c,的乘积所组成的 ，则于是，每当n可以拆分为a, ,b, ,c

171、的和时， xn就会出现，这就证明了定理的结论。189189. .4.4 整数的拆分例1例1 1、若有1 1克、2 2克、3克、4 4克的砝码各一枚，问能称出哪几种重量？有几种可能方案？ 证明：我们采用如下办法来产生拆分数的普通母函数：从右端的母函数知能称出从1 1克到1010克的重量，系数便是方案数。例如右端有2 2x5 5 项，即称出5 5克的方案有2 2种，5=2+5=2+3=1+4=1+4。同样6=1+2+6=1+2+3=2+4=2+4，10=1+2+10=1+2+3+4+4，即称出6 6克的方案有2 2种，称出1010克的方案有1 1种。190190. .4.4 整数的拆分例2例2 2

172、、求用1 1分、2 2分、3分的邮票贴出不同数值的方案数。 解：因邮票允许重复，故普通母函数为以其中x4 4为例，其系数为4 4，即4 4拆分成1 1、2 2、3之和的拆分数为4 4，即191191. .4.4 整数的拆分例3例3、若有1 1克的砝码3枚，2 2克的4 4枚，4 4克的2 2枚，问能称出哪些重量？各有几种方案？ 解：上面的1+1+x4 4+ +x8 8项表示4 4克砝码只有两枚，或不取，或取一枚，或取2 2枚。x8 8项的系数为5 5，说明称8 8克的方案有5 5种 ：192192. .4.4 整数的拆分例4例4 4、整数n拆分成1,2,1,2,3,m的和，并允许重复，求其母函

173、数。如若其中m至少出现一次，其母函数如何？ 解： 若整数n拆分成1,2,1,2,3,m的和，并允许重复，其普通母函数为：若拆分中m至少出现一次，其普通母函数为：上式的组合意义：整数n拆分成1 1到m的和的拆分数减去拆分成1 1到m-1 1的和的拆分数，即为至少出现一个m的拆分数。19193. .4.4 整数的拆分定义用Pk k( (n) )表示n拆分为1,2,1,2,k k允许重复的方法数。用Po( (n) )表示n拆分为奇整数的方法数。用Pd( (n) )表示n拆分为不同整数的方法数。用Pt( (n) )表示n拆分为2 2的不同幂（1,2,4,1,2,4,）的方法数。 194194. .4.

174、4 整数的拆分推论推论4.4.14.4.1：P3( (n) )的普通母函数是1/ 1/(1(1-x)(1)(1-x2 2)(1)(1-x3) ) 推论4.4.24.4.2：Pk k( (n) )的普通母函数是1/ 1/(1(1-x)(1)(1-x2 2)(1)(1-xk k) ) 推论4.4.4.4.3：P( (n) )的普通母函数是1/ 1/(1(1-x)(1)(1-x2 2)(1)(1-x3) 推论4.4.44.4.4：Po( (n) )的普通母函数是1/ 1/(1(1-x)(1)(1-x3) )(1(1-x5 5) 195195. .4.4 整数的拆分定理5设a, ,b, ,c为不同的正

175、整数，则(1+(1+xa)(1+)(1+xb)(1+)(1+xc) )的级数展开式中xn的系数就是把n拆分为a, ,b, ,c的和，且a, ,b, ,c最多只出现一次的方法数。 推论4.5.14.5.1：Pd( (n) ) 的普通母函数为(1+(1+x)(1+)(1+x2 2) )(1+(1+x3)(1+)(1+x4 4)推论4.5.24.5.2：Pt( (n) )的普通母函数是 (1+(1+x)(1+)(1+x2 2) )(1+(1+x4 4)(1+)(1+x8 8)196196. .4.4 整数的拆分定理6-1Euler定理：Po( (n) )= =Pd( (n)证明：根据推论4.5.14

176、.5.1，Pd( (n) )的普通母函数为等式右端正好是Po( (n) )的普通母函数（推论4.4.4)4.4.4)。所以Po( (n)=)=Pd( (n) )，即把n拆分成奇整数的和的方法数等于把n拆分成不同的整数和的方法数。197197. .4.4 整数的拆分定理6-2Euler定理：Po( (n) )= =Pd( (n)可以验证当n=7=7的情况：198198. .4.4 整数的拆分定理7Sylvester定理：对任意正整数n有Pt( (n)=1)=1证明I：因为任何一个正整数都可惟一地用一二进制数来表示，而一个二进制数又可惟一地表示成2 2的次幂的和，由此即得结论。证明II：因为序列1

177、,1,1,1,1,1,的普通母函数为上式的左端正好是Pt( (n) )的普通母函数（推论4.5.2),4.5.2),199199. .4.4 整数的拆分例5例5 5、设有1,2,4,8,16,1,2,4,8,16,32 2克砝码各一枚，试问能称出哪些重量？分别有几种方案？ 证明：从普通母函数f( (x) )可以得知，用这些砝码可以称出从0 0克到6 63克的重量，而且办法都是惟一的。实际是0 0到6 63的数的二进制表示是惟一的。200200. .4.4 整数的拆分例6例6 6、证明以下恒等式并说明其组合含义。 证明：因此这个恒等式表明，任何正整数都可以惟一地拆分成形式为的不同部分。换句话说，

178、任何正整数的十进制表示是惟一的。201201. .4.4 整数的拆分定理8-1拆分数的估计式 ：对任意正整数n，有证明：由推论4.4.4.4.3知，P( (n) )的普通母函数为： 对上式两端取对数得由对数的泰勒展开式知 （A）202202. .4.4 整数的拆分定理8-2 拆分数的估计式 ：对任意正整数n，有20203. .4.4 整数的拆分定理8-3 拆分数的估计式 ：对任意正整数n，有204204. .4.4 整数的拆分定理8-4 拆分数的估计式 ：对任意正整数n，有205205. .4.4 整数的拆分定理8-5 拆分数的估计式 ：对任意正整数n，有206206. .4.5 Ferrer

179、s图定义设n的一个拆分为n= =a1 1+ +a2 2+ak k，其中 a1 1a2 2ak k1 1，如从上到下依次画ai个格子（点）( (i=1,2,=1,2,k k) )，称此图称为Ferrers图。 Ferrers图像具有如下性质：1 1、每一层至少有一个格子。2 2、第一行与第一列互换，第二行于第二列互换，即下图绕虚线轴旋转所得的图仍然是Ferrers图像。两个Ferrers图像称为一对共轭的Ferrers图像。207207. .4.5 Ferrers图定理9正整数n拆分为k k项和的拆分数等于数n拆分为最大数为k k的拆分数。证明：考虑Ferrers图与其共轭图的关系，即可得证。因

180、整数n拆分成k k个数的和的拆分可用一k k行的Ferrers图表示，所得的Ferrers图的共轭图最上面一行有k k个格子。例如：24=6+6+5+4+24=6+6+5+4+35 5个数，最大数为6 624=5+5+5+4+24=5+5+5+4+3+2+26 6个数，最大数为5 5208208. .4.5 Ferrers图定理10、11正整数n拆分为最多不超过k k个数的和的拆分数等于数n拆分为最大数不超过k k的拆分数。 正整数n拆分为互不相同的若干奇数的和的拆分数等于数n拆分成有自共轭的Ferrers图的拆分数。 证明：设 构造一个Ferrers图像，其第一行，第一列都是n1 1+1+1

181、格，对应于2 2n1 1+1+1，第二行，第二列各n2 2+1+1格，对应于2 2n2 2+1+1。以此类推。由此得到的Ferrers图像是共轭的。反过来也一样。例如 17=9+5+17=9+5+3,对应为Ferrers图像为9+5+9+5+3=17=17209209. .4.6 组合恒等式应用母函数不仅在计数中有广泛应用，而且在证明（推导）组合恒等式中提供了一种重要方法。其中用二项式定理的，参见1.41.4 。210210. .4.6 组合恒等式应用例1-1例1 1、设p, ,q为任意正整数，证明： 证明：由于一个序列是与它的母函数一一对应的，而两个母函数间的乘积关系必然反映为两个母函数对应

182、的序列与其乘积对应的序列之间的关系。为了证明上面的恒等式，只需求出两个序列对应的母函数，使得其乘积对应的序列为先求形如序列 的母函数。在上式中分别令n= =p和n= =q得211211. .4.6 组合恒等式应用例1-2例1 1、设p, ,q为任意正整数，证明： 212212. .4.6 组合恒等式应用例2例2 2、设p为非负整数，且pn ，证明： 证明：由式将上式两边对x微分p次得将上式两边同乘以1/ 1/p! !得 在上式中，令x= = -1 1，有 故恒等式成立。注意，若令x= = 1, 1,又可得到如下的恒等式：本例中的恒等式还表明序列与序列是一对互相正交的序列（当pn时），故此恒等式

183、在组合分析中极为有用。21213. .4.6 组合恒等式应用例3-1例3、证明： 证明：由式于是我们分别得到下列各式将以上各式两端分别相加，则其右端和中xn的系数正好是要证的恒等式的左端，其左端的和为 如果我们能求出f( (x) )展开式中xn的系数是2 22 2n, ,则此例中恒等式得证。214214. .4.6 组合恒等式应用例3-2例3、证明： 215215. .4.6 组合恒等式应用例4例4 4、证明： 证明：由二项式定理分别有以下各式将以上各式两端分别相加，则其右端和中xk k的系数正好是要证的恒等式的左端，其左端的和为 216216. .4.6 组合恒等式应用例5例5 5、证明：证

184、明：由于左端出现形如的序列，故自然要考虑求序列 的母函数。由4.14.1节例3知序列的母函数为，即根据定理4.24.2，上式中xk k的系数是又由二项式定理有 也就是说，上式中xk k的系数是4 4n217217. .第4章 小结 本章主要研究了序列的母函数表示法，母函数表示法不仅可以使得对数列的代数处理更容易些，而且它对事件的符号描述也是很有用的。在以后的学习中，这是一个重要的概念。 本章重点需要掌握普通母函数、指数母函数的基本概念，及其在排列、组合中的应用，并了解母函数的一个应用实例整数拆分和Ferrers图。218218. .第4章 习题P81816 6、7 7、8 8、1010、111

185、1、1212、1 13。219219. .回顾前一章母函数：本章主要介绍递推关系的建立及几种常见的求解方法： 常系数齐次递推关系 常系数非齐次递推关系 迭代法 归纳法 母函数法形式函数排列、组合中应用整数拆分等220220. .5.1 递推关系定义设an为一序列，把该序列中an和它前面几个ai (0(0in) )关联起来的方程称做一个递推关系（递归关系）。如第3章的错排数Dn=(=(n-1)(1)(Dn-1 1+ +Dn-2 2) )，( (n3) ) 和关系式an= =3an-1 1，( (n1)1)都是递推关系。如a0 0= =d0 0 , ,a1 1= =d1 1,ak k= =dk k

186、，di为常数( (i=0,1,=0,1,k k) )，称为递推关系的初值。如D1 1=0,=0,D2 2=1=1作为初值即可惟一的确定序列( (D0 0, ,D1 1,Dn,),)，a0 0=1=1作为初值即可惟一的确定序列(1,(1,3, ,32 2,3n,),)。将递推关系和初值结合起来称为带初值的递推关系。如221221. .5.1 递推关系建立例1-1例1 1、在一个平面上有一个圆和n条直线，这些直线中的每一条在圆内都同其他的直线相交。如果没有多于三条的直线相交于一点，试问这些直线将圆分成多少个不同区域？ 222222. .5.1 递推关系建立例1-2解：要求解这个问题，首先必须建立递

187、推关系，然后求解递推关系即可。设这n条直线将圆分成的区域数为an，如果有n-1 1条直线将圆分成an-1 1个区域，那么再加入第n条直线与在圆内的其他n-1 1条直线相交。显然，这条直线在圆内被分成n条线段，而每条线段又将第n条直线在圆内经过的区域分成两个区域。这样，加入第n条直线后，圆内就增加了n个区域。而对于n=0=0，显然有a0 0=1=1，于是对于每个整数 n，可以建立如下带初值的递推关系 （求解方法以后几节再介绍）这就是问题的解答。22223. .5.1 递推关系建立例2-1例2 2、“Hanoi塔”问题：n个大小不一的圆盘依半径的大小，从下而上的套在柱子A上。如图所示。现要求将所有

188、的圆盘从柱子A上全部移到柱子C C上，每次只允许从一根柱子上转移一个圆盘到另一根柱子上，且在转移过程中不允许出现大圆盘放到小圆盘上。试问至少要转移多少次才能将柱子上的n个圆盘全部转移到柱子C C上去？ 224224. .5.1 递推关系建立例2-2解：用an表示从一根柱子上的n个圆盘全部转移到另一根柱子上的转移次数。显然，a1 1=1,=1,a2 2= =3。当n3时，要将柱子A上的n个圆盘转移到柱子C C上，可以这样设想。先把柱子A上的n-1 1个圆盘转移到柱子B上，这需要转移an-1 1次；然后把柱子A上最后一个圆盘转移到柱子C C上，显然这需要转移一次；最后再把柱子B上的n-1 1个圆盘

189、转移到柱子C C上，这也需要转移an-1 1次。经过这些步骤后，所有A上的n个圆盘就全部转移到柱子C C上。由加法法则，这一共转移了2 2an-1 1+1+1次。于是可以建立如下带初值的递推关系 这就是我们需要的结果。225225. .5.1 递推关系建立例3-1例3、“Fibonacci兔子问题”也是组合数学中的著名问题之一。这个问题是指：从某一年某一月开始，把雌雄各一的一对兔子放入养殖场中，从第二个月雌兔每月产雌雄各一的一对新兔。每对新兔也是从第二个月起每月产一对兔子。试问第n个月后养殖场中共有多少对兔子？ 226226. .5.1 递推关系建立例3-2解：设第n个月时养殖场中兔子的对数为

190、Fn。并定义F0 0=1=1，显然有，F1 1=1=1。由于在第n个月时，除了有第n-1 1个月时养殖场中的全部兔子Fn-1 1外，还应该有Fn-2 2对新兔子，这是因为在第n-2 2个月就已经有的每对兔子，在第n个月里都应生一对新的兔子。因此可以建立如下带初值的递推关系 求解上式可以得到我们所需的答案。注：利用该式我们可以推得( (F0 0, ,F1 1,Fn,)=(1,1,2,)=(1,1,2,3,5,8,1,5,8,13,21,21,34,55,)4,55,)常称Fn为Fibonacci数， ( (F0 0, ,F1 1,Fn,),)为Fibonacci数列。Fibonacci数列在数学

191、中是一个奇特而又常见的序列，它在算法分析中起着重要的作用。具体性质以后讨论。227227. .5.1 递推关系建立例4例4 4、在一个平面中，有n个圆两两相交，但任二个圆不相切，任三个圆无公共点，求这n个圆把平面分成多个区域？ 解：设这n个圆将平面分成an个区域。如图。易见 ，a1 1=2,=2,a2 2=4=4。现在假设前n-1 1个圆将平面分成了an-1 1个区域，当加入第n个圆时，由题设这个圆与前面的n-1 1个圆一定交于2(2(n-1)1)个点，这2(2(n-1)1)个点把第n个圆分成2(2(n-1)1)条弧，而每条弧正好将前面的 n-1 1个圆分成的区域中的其经过的每个区域分成2 2

192、个区域，故新加入的第n个圆使所成的区域数增加了2(2(n-1)1)。因此可以建立如下带初值的递推关系： 求解这个递推关系可以得到问题的解答。228228. .5.1 递推关系建立例5例5 5、设有n个数b1 1, ,b2 2,.,.,bn的连乘积为b1 1b2 2. .bn。试求不同的结合方式数（加括号的方式）。 解：设不同的结合方式数为an。定义a1 1=1=1，显然有a2 2=1=1。由于对乘积b1 1b2 2bn的任一结合方式，必有某一个k k使得最后的运算为积b1 1b2 2bk k与积bk k+1+1bk k+2+2bn相乘。当k k 固定时，对乘积b1 1b2 2bk k有ak k

193、 种不同的结合方式，而对乘积bk k+1+1bk k+2+2bn有an-k k 种不同的结合方式。由乘法法则知，对某一个k k 共有ak k an-k k 种不同的结合方式。再由加法法则即得如下带初值的递推关系： 求解这个递推关系即得到问题的解答。229229. .5.1 递推关系建立例5 5、设有n个数b1 1, ,b2 2,.,.,bn的连乘积为b1 1b2 2. .bn。试求不同的结合方式数（加括号的方式）。 注：以上各例均为经典组合数学问题，在算法分析中常用；对普通的递推关系无一般规则可解。 2 230 0. .5.2 常系数线性齐次定义若an中相邻k k+1+1项满足an= =b1

194、1an-1 1+ +b2 2an-2 2+bk kan-k k，( (nk k) )称之为an的k k阶常系数线性齐次递推关系。其中bi( (i=1,2,=1,2,k k) )是常数，且bk k0 0。a0 0= =d0 0, , a1 1= =d1 1, , , ak k-1 1= =dk k-1 1称为初始条件，其中di( (i=0,2,=0,2,k k-1)1)是常数；C C( (x)=)=xk k-b1 1xk k-1 1-b2 2xk k-2 2-bk k称为上述递推关系的特征多项式；C C( (x)=0)=0称为上述递推关系的特征方程；该方程的方程根称为上述递推关系的特征根。2 2

195、31 1. .5.2 常系数线性齐次相异特征根定理15.2.15.2.1相异特征根的解法 若q0,0,an= =qn是上述递推关系的解，当且仅当q是上述特征方程的解。 证明：若q 0,0,an= =qn是递推关系an= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k的解 qn = =b1 1qn-1 1 + +b2 2qn-2 2 +bk kqn-k k(nk k) ) qk k = =b1 1qk k-1 1 + +b2 2qk k-2 2 +bk k q是特征方程xk k-b1 1xk k-1 1-b2 2xk k-2 2-bk k=0=0的根。证毕。2 232 2

196、. .5.2 常系数线性齐次相异特征根定理25.2.15.2.1相异特征根的解法 若q1 1, ,q2 2,qk k, ,为上述递推关系的特征根（相异），c1 1, , c2 2,ck k为任意常数，则an= =c1 1q1 1n+ +c2 2q2 2n+ck kqk kn为上述递推关系的解。 证明：由于qi( (i=1,2,=1,2,k k) )是特征方程xk k-b1 1xk k-1 1-b2 2xk k-2 2-bk k=0=0的根，由定理5.15.1有qin = =b1 1qin-1 1 + +b2 2qin-2 2 +bk k qin-k k，i=1,2,=1,2,k k将上式两边同

197、乘以ci ，然后从1 1到k k求和有因此an= =c1 1q1 1n+ +c2 2q2 2n+ck kqk kn是递推关系an= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k的解。2 233. .5.2 常系数线性齐次相异特征根定理3-1若an为上述递推关系的任一解，且存在一组适当常数c1 1, ,c2 2,ck k使得an具有表达式an= =c1 1q1 1n+ +c2 2q2 2n +ck kqk kn ，称该表达式为上述递推关系的通解。5.2.15.2.1相异特征根的解法 若q1 1, ,q2 2,qn为上述递推关系的特征根（相异），则an= =c1 1q1

198、1n+ +c2 2q2 2n+ck kqk kn为上述递推关系的通解，其中ci由初始条件确定。2 234 4. .5.2 常系数线性齐次相异特征根定理3-25.2.15.2.1相异特征根的解法 证明：由定理5.25.2知， an= =c1 1q1 1n+ +c2 2q2 2n+ck kqk kn是递推关系an=b1 1an-1 1+ +b2 2an-2 2+bk kan-k k的解。只需证明，若该式满足递推关系式an= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k的任意初值条件式a0 0= =d0 0, ,a1 1= =d1 1, , , ak k-1 1= =dk

199、k-1 1所得到的关于c1 1, ,c2 2,ck k的线性方程组有惟一解即可。由初值条件式a0 0= =d0 0, ,a1 1= =d1 1,ak k-1 1= =dk k-1 1，我们得到因此，上述线性方程组关于c1 1, ,c2 2,ck k有惟一的解。从而证明了an= =c1 1q1 1n+ +c2 2q2 2n+ck kqk kn 是递推关系的 an= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k 的通解。2 235 5. .例1 1、求递归关系5.2 常系数线性齐次例15.2.15.2.1相异特征根的解法 2 236 6. .5.2 常系数线性齐次例25.

200、2.15.2.1相异特征根的解法 例2 2、求递归关系2 237 7. .5.2 常系数线性齐次相同特征根定理45.2.25.2.2相同特征根的解法 若q为上述递推关系的特征方程C C( (x)=0)=0的一个m重特征根，则qn, ,nqn,nm-1 1qn为该递推关系的解。 证明：令P( (x)=)=xk k-b1 1xk k-1 1-b2 2xk k-2 2-bk k， Pn( (x)=)=xn-k k P( (x) ) = =xn-b1 1xn-1 1-b2 2xn-2 2-bk kxn-k k 。由于q是P( (x)=0)=0的m重根，故q也是Pn( (x)=0)=0的m重根，由高等代

201、数的知识知，q也是Pn( (x)=0)=0的( (m-1)1)重根，那么q也是xPn( (x)=0)=0的( (m-1)1)重根，即q是方程nxn-b1 1( (n-1)1)xn-1 1-b2 2( (n-2)2) xn-2 2-bk k( (n-k k) )xn-k k =0=0的( (m-1)1)重根。类似地，q是方程n2 2xn-b1 1( (n-1)1)2 2xn-1 1-b2 2( (n-2)2)2 2xn-2 2-bk k( (n-k k) )2 2xn-k k=0=0的( (m-2)2)重根。一般地，对任意的i, ,im, ,q是方程nixn-b1 1( (n-1)1)ixn-1

202、 1-b2 2( (n-2)2)ixn-2 2-bk k( (n-k k) )i xn-k k=0=0的( (m-i) )重根。即有niqn-b1 1( (n-1)1)iqn-1 1-b2 2( (n-2)2)iqn-2 2-bk k ( (n-k)k)iqn-k k=0=0。分别令i=1,2,=1,2,m-1 1，知nqn, ,n2 2qn, ,nm-1 1qn都是递推关系an= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k的解，而qn是递推关系an= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k的解在定理5.15.1中已经证明。故定理得证

203、。2 238 8. .5.2 常系数线性齐次相同特征根定理5-15.2.25.2.2相同特征根的解法 若q1 1, ,q2 2,qt分别为上述递推关系的特征方程C C( (x)=0)=0相异的m1 1, ,m2 2,mt重特征根， 为该递推关系的通解，其中cij j由初始条件确定。2 239 9. .5.2 常系数线性齐次相同特征根定理5-25.2.25.2.2相同特征根的解法 证明：由定理5.45.4知， 表达式的右端每一项都是递推关系an= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k的解。故an也是该递推关系的解。现只需证明该式满足递推关系式an= =b1 1a

204、n-1 1+ +b2 2an-2 2+bk kan-k k的任意初值条件式a0 0= =d0 0, ,a1 1= =d1 1, ak k-1 1= =dk k-1 1所得的线性方程组有惟一解即可。 将初值条件式a0 0= =d0 0, ,a1 1= =d1 1,ak k-1 1= =dk k-1 1代入式( (A) )得到下列方程组：这个方程组的系数行列式是Vandermonde行列式的一个推广。其行列式之值为故方程组有惟一解。即cij j( (i=1,2,=1,2, ,t; j j=1,2,=1,2, ,mi) )是由初值惟一确定，定理得证。240240. .例3、求递归关系5.2 常系数线

205、性齐次例35.2.25.2.2相同特征根的解法 241241. .例4 4、求递归关系5.2 常系数线性齐次例45.2.25.2.2相同特征根的解法 242242. .5.2 常系数线性齐次例55.2.25.2.2相同特征根的解法 例5 5、求递归关系24243. .5.2 常系数线性齐次例65.2.25.2.2相同特征根的解法 例6 6、计算n阶行列式的值：解：设具有以上形式的n阶行列式的值为an，按第一列展开有 显然a1 1=2=2， a2 2= =3，于是可建立递推关系如下这个递推关系就是例3所求解的递推关系，故由例3的结果可知244244. .5.2 常系数线性齐次注意事项5.2.25

206、.2.2相同特征根的解法 注：建立递推关系关系时可考虑某个特定 数值，如第一个、最后一个等；k k次递推关系需要k k个初值，一般从a0 0开始（不妨假设）；结果需要验证（n= =k k+1,+1,k k+2,+2,） 。 245245. .5.3 常系数线性非齐次定义若an中相邻k k+1+1项满足an= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k+ +f( (n) )，( (nk k) )称之为an的k k阶常系数线性非齐次递推关系。其中bi( (i=1,2,=1,2,k k) )是常数，且bk k0 0，f( (n) )0 0 。若f( (n) )= =0 0

207、，称 = =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k 为上述递推关系导出的常系数线性齐次递推关系。246246. .5.3 常系数线性非齐次定理6-1若 为an= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k+ +f( (n) ) 的一个特解， 为= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k 的一个通解，则an= = + + 为原非齐次递推关系的通解。 证明：由于 是非齐次递推关系式导出的齐次线性递推关系式即的通解，故有又由于是非齐次递推关系的一个特解，故有将以上两式的两边分别相加得由上式可见 是式的解。247

208、247. .5.3 常系数线性非齐次定理6-2若 为an= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k+ +f( (n) ) 的一个特解， 为= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k 的一个通解，则an= = + + 为原非齐次递推关系的通解。 现只需证明 能满足式的任意初值条件式所导出的关于c1 1, ,c2 2,ck k为未知数的线性方程组有惟一解即可。式中。而这是显然的。因为该方程组的系数矩阵是一个Verdermonde矩阵，其行列式的值不为0 0。故定理得证。248248. .5.3 常系数线性非齐次定理6-3若 为an=

209、=b1 1an-1 1+ +b2 2an-2 2+bk kan-k k+ +f( (n) ) 的一个特解， 为= =b1 1an-1 1+ +b2 2an-2 2+bk kan-k k 的一个通解，则an= = + + 为原非齐次递推关系的通解。 v 注：定理5.65.6指出，若要求一个常系数线性非齐次递推关系式的通解，必须先求出这个递推关系所导出的常系数线性齐次递推关系的通解，然后再求这个递推关系式的一个特解，将其相加即可。v 然而，求一个非齐次线性递推关系的特解，通常没有系统的方法，但当函数f( (n) )是某些特殊形式时，才有一些规范的求法。249249. .v 若f( (n) )为n的

210、k k次多项式，则 = =A0 0nk k+ +A1 1nk k-1 1+Ak k，其中A0 0, , A1 1,Ak k为待定系数；若导出的常系数线性齐次递推关系特征根为1 1的m重根，则 =(=(A0 0nk k+ +A1 1nk k-1 1+Ak k ) )nm 。5.3 常系数线性非齐次特殊形式v 可针对f( (n) )的某些特定形式，转化为齐次性。v 若f( (n) )为 n的形式，如不是导出的常系数线性齐次递推关系特征根，则 = =A n，其中A为待定系数；若是导出的常系数线性齐次递推关系的k k重特征根根，则 =(=(A0 0nk k+ +A1 1nk k-1 1+Ak k) )

211、 n 。250250. .5.3 常系数线性非齐次例1例1 1、求递归关系（Hanoi塔）251251. .5.3 常系数线性非齐次例2例2 2、求递归关系252252. .5.3 常系数线性非齐次例3例3、求递归关系25253. .5.3 常系数线性非齐次例4例4 4、求递归关系an+2+2an-1 1+ +an-2 2=2=2n的通解。254254. .5.3 常系数线性非齐次例5例5 5、求递归关系an-4 4an-1 1+4+4an-2 2=2=2n的通解。255255. .5.3 常系数线性非齐次例6例6 6、求Sn=1+2+=1+2+3+n。256256. .5.3 常系数线性非齐

212、次例7例7 7、求Sn=1=12 2+2+22 2+ +32 2+n2 2。257257. .5.3 常系数线性非齐次例8例8 8、求Sn=1=13+2+23+ +33+n3。258258. .5.4 迭代法例1针对上述k k阶常系数线性（非）齐次递推关系求解方法，当k k较大时，面临着解高次方程和高阶线性方程组的困难；而且对一般的非齐次递推关系无系统的方法 。 例1 1、求递归关系解：这是常系数线性非齐次递推关系，可以用上节中的方法求解。这里用迭代法求解。反复应用递推关系式进行迭代有259259. .5.4 迭代法例2例2 2、求递归关系解：这是一个非常系数线性非齐次递推关系。下面用迭代法求

213、解。反复应用递推关系式进行迭代有 260260. .5.4 迭代法例3例3、求递归关系解：这是一个非线性递推关系。反复应用递推关系式进行迭代有注：此例中的递推关系式还可以作一个变换变成一个常系数线性非齐次递推关系然后利用上节的方法求解。261261. .5.4 归纳法例4例4 4、求递归关系解：这是5.15.1中例4 4所导出的递推关系。在5. 5.3中已经求出该递推关系的解。下面我们用归纳法求解。先用初值条件a1 1=2=2求出前几项，并观察其规律。由上面所得到的值，我们可以猜想解的一般的公式为为了证实上述猜想确实是递推关系的解，我们用归纳法证之。由上面计算前几项的值，显然，当n=1,2,=

214、1,2,3,4,5,4,5时，结论成立。设n= =k k时，结论成立，即有则当n= =k k+1+1时，有可见，当n= =k k+1+1时，结论也是成立的。262262. .5.4 归纳法例5例5 5、求递归关系解：与例4 4一样，先求前几项的值于是，我们可以猜想解的一般的公式为然后用归纳法证明以上猜想是正确的。 n=0,1,2,=0,1,2,3, ,结论显然成立。设n= =k k时，结论成立，即有则当n= =k k+1+1时，有可见，当n= =k k+1+1时，结论也是成立的。26263. .5.5 母函数在递推关系中的应用母函数法是求解递推关系的一种重要方法，不仅可以求解常系数线性（非）齐

215、次递推关系，也可以求解非线性、非常系数的递推关系 。求解的方法和步骤为：1. 1. 用f( (x) )表示序列an的普通母函数；2. 2.利用递推关系an的表达式代入母函数的右端，或采用多项式形式算法，转化为关于f( (x) )的方程g( (f( (x)=0)=0；3. .解出f( (x) )再展开成幂级数，即可求得an的初等表达式。264264. .5.5 母函数的应用例1-1例1 1、求递归关系265265. .5.5 母函数的应用例1-2例1 1、求递归关系266266. .5.5 母函数的应用例2例2 2、求递归关系267267. .5.5 母函数的应用例3-1例3、求递归关系2682

216、68. .5.5 母函数的应用例3-2例3、求递归关系注：通常，称满足上述递推关系的序列( (a1 1, ,a2 2,an,),)为C Catalan序列，称序列中的数为C Catalan数。这个数很重要，它在各种不同的范围里经常出现，许多有意义的计数问题都与这个数有关。269269. .5.5 母函数的应用例4-1例4 4、求递归关系270270. .5.5 母函数的应用例4-2例4 4、求递归关系271271. .5.5 母函数的应用例5-1例5 5、求n位十进制正整数中出现偶数个5 5的数的个数。解I：令an= =n位十进制数中出现偶数个5 5的数的个数 bn= =n位十进制数中出现奇数

217、个5 5的数的个数建立递推关系如下这是关于序列an和 bn的联立关系。设序列an, ,bn的普通母函数分别为A( (x), ),B( (x) )。其中272272. .5.5 母函数的应用例5-2例5 5、求n位十进制正整数中出现偶数个5 5的数的个数。27273. .5.5 母函数的应用例5-3例5 5、求n位十进制正整数中出现偶数个5 5的数的个数。解II： n-1 1位的十进制数的全体共 9 9 1010n-2 2, ,从中去掉含有偶数个5 5的数，余下的便是n-1 1位中含有奇数个5 5的数。故有： 274274. .5.5 母函数的应用例6例6 6、求递归关系（Hanoi塔）解：设序

218、列an的普通母函数为275275. .5.6 Fibonacci数列15.6.15.6.1Fibonacci数列性质5.6.15.6.1：F1 1+ +F2 2+Fn= =Fn+ +2 2-1 1276276. .5.6 Fibonacci数列25.6.15.6.1Fibonacci数列性质5.6.15.6.1：F1 1+ +F2 2+Fn= =Fn+ +2 2-1 1性质5.6.25.6.2：F1 1+ +F3+F2 2n-1 1= =F2 2n277277. .5.6 Fibonacci数列35.6.15.6.1Fibonacci数列性质5.6.15.6.1：F1 1+ +F2 2+Fn=

219、 =Fn+ +2 2-1 1性质5.6.25.6.2：F1 1+ +F3+F2 2n-1 1= =F2 2n性质5.6.5.6.3：F1 12 2+ +F2 22 2+Fn2 2= =Fn Fn+1+1278278. .5.6 Fibonacci数列45.6.15.6.1Fibonacci数列性质5.6.15.6.1：F1 1+ +F2 2+Fn= =Fn+ +2 2-1 1性质5.6.25.6.2：F1 1+ +F3+F2 2n-1 1= =F2 2n性质5.6.5.6.3：F1 12 2+ +F2 22 2+Fn2 2= =Fn Fn+1+1性质5.6.45.6.4：Fn-1 1 Fn+1

220、+1-Fn2 2=(=(-1)1)n279279. .5.6 第一类Stirling数定义5.6.25.6.2第一类Stirling数令xn= =x( (x-1)(1)(x-2)(2)(x-n+1)+1)，若 ，则称S1 1( (n, ,k k) )为第一类Stirling数。280280. .5.6 第一类Stirling数定理5.6.25.6.2第一类Stirling数第一类Stirling数满足以下递推关系：注：这是依赖于两个参数的递推关系。证明：由定义易见，S1 1(0,0)=1,(0,0)=1,S1 1( (n,0)=0(,0)=0(n0)0) 281281. .5.6 第二类Sti

221、rling数定义5.6.5.6.3 第二类Stirling数令xn= =x( (x-1)(1)(x-2)(2)(x-n+1)+1)，若 ，则称S2 2( (n, ,k k) )为第二类Stirling数。282282. .5.6 第二类Stirling数定理85.6.5.6.3 第二类Stirling数第二类Stirling数满足以下递推关系：证明：由定义易见，S2 2(0,0)=1,(0,0)=1,S2 2( (n,0)=0(,0)=0(n0)0)28283. .5.6 第二类Stirling数定理9-15.6.5.6.3 第二类Stirling数第二类Stirling数S2 2( (n,

222、,k k) )就是n个元素的集合划分为k k个不相交的非空子集的方式数目。证明：设A( (n, ,k k) )是n个元素的集合划分成k k个不相交的非空子集的方式数目。下面证明A( (n, ,k k) )满足定理5.85.8中的递推关系式。给定一个n元集合a1 1, ,a2 2,an，将这个n元集合划分成k k个不相交的非空子集可以分为互不相容的两种情况：设an是k k个子集合中的一个子集，于是把a1 1, ,a2 2,an-1 1划分为k k-1 1个子集有A( (n-1, 1,k k-1)1)种划分方式。如果an不是k k个子集合中的一个，即an必与其他的元素构成一个子集。首先把a1 1,

223、 ,a2 2,an-1 1划分为k k个子集，这共有A( (n-1, 1,k k) )种划分方式。然后把an加入到k k个子集合中的一个子集中去，这有k k种加入方式。对每一个加入方式都使集合划分成k k个子集，因此方式数共有k kA( (n-1, 1,k k) )种。 由由, ,并应用加法法则有：a1 1, ,a2 2,an划分成k k个子集的方式数一共有A( (n-1, 1,k k -1)+1)+k kA( (n-1, 1,k k) )种，即 A( (n, ,k k) )= =A( (n-1, 1,k k-1)+1)+k kA( (n-1, 1,k k) )。用n+1+1代替上式中的n，则

224、上式变为A( (n+1,+1,k k) )= =A( (n, ,k k-1)+1)+k kA( (n, ,k k) )。又因为将一个元素的集合划分成一个不相交的的非空子集的方式数显然是1 1，故A(1,1)=1(1,1)=1，代入递推关系有A(0,0)=1(0,0)=1。另外，我们不可能把n个元素的集合的n个元素不放进任何一个集合中去，故A( (n,0)=0,0)=0。因此A( (n, ,k k) )是满足定理5.85.8中的递推关系式的。故A( (n, ,k k)=)=S2 2( (n, ,k k) )284284. .5.6 第二类Stirling数定理9-25.6.5.6.3 第二类St

225、irling数第二类Stirling数S2 2( (n, ,k k) )就是n个元素的集合划分为k k个不相交的非空子集的方式数目。n个有区别的球放入m个相同的盒子中，要求无一空盒的方式数即第二类Stirling数S2 2( (n, ,m) )。285285. .5.6 第二类Stirling数定理10-15.6.5.6.3 第二类Stirling数第二类Stirling数S2 2( (n, ,k k) )具有如下性质： S2 2( (n,0)=0,0)=0S2 2( (n,1)=1,1)=1S2 2( (n, ,n)=1)=1S2 2( (n, ,k k)=0()=0(nk k或k k=0=

226、0n) )S2 2( (n,2)=2,2)=2n-1 1-1 1证明：S2 2( (n,2),2)表示n个有区别的球放入2 2个相同的盒子中，要求无一空盒的方式数。设有n个不相同的球b1 1, ,b2 2,bn, ,从中取出球b1 1，其余的n-1 1个球，每个都有两种选择：与b1 1同盒或不与b1 1同盒。但必须排除一种情况，即全体与b1 1同盒，因这时另一盒将是空盒。故实际上只有2 2n-1 1-1 1种方案，即S2 2( (n,2)=2,2)=2n-1 1-1 1。286286. .5.6 第二类Stirling数定理10-25.6.5.6.3 第二类Stirling数第二类Stirli

227、ng数S2 2( (n, ,k k) )具有如下性质： S2 2( (n,0)=0,0)=0S2 2( (n,1)=1,1)=1S2 2( (n, ,n)=1)=1S2 2( (n, ,k k)=0()=0(nk k或k k=0=0n) )S2 2( (n,2)=2,2)=2n-1 1-1 1S2 2( (n, ,n-1)=1)=C C( (n,2),2)证明： S2 2( (n, ,n-1)1)表示n个不相同的球放到n-1 1个相同的盒子里，不允许有空盒的方式数。故有且只有一个盒子有两个球，从n个有区别的球中取2 2个共有C C( (n,2),2)种组合方案，故S2 2( (n, ,n-1)

228、=1)=C C( (n,2),2)。287287. .5.6 第二类Stirling数定理10-35.6.5.6.3 第二类Stirling数第二类Stirling数S2 2( (n, ,k k) )具有如下性质： S2 2( (n,0)=0,0)=0S2 2( (n,1)=1,1)=1S2 2( (n, ,n)=1)=1S2 2( (n, ,k k)=0()=0(nk k或k k=0=0n) )S2 2( (n,2)=2,2)=2n-1 1-1 1S2 2( (n, ,n-1)=1)=C C( (n,2),2)证明： S2 2( (n, ,m) )表示把n个不同的球放入 m个相同的盒子，而且

229、无一盒为空的方式数。如果考虑盒子是编号的。因为m个盒子共有m! !种编号方式，于是由乘法法则知共有m! !S2 2( (n, ,m) )种方式把n个不同的球放入m个不同编号的盒子中去，而且没有一个空盒。注：这种方式实际上是第二章3.1 .1中的例1010。设S表示n个不同的球任意放入m个有编号的盒子里的所有方法的集合，显然|S|= =mn 。令pi( (i=1,2,=1,2,m) )表示盒子i为空这一性质，Ai( (i=1,2,=1,2,m) )表示S中具有性质pi的元素组成的集合。则 表示没有一个箱子为空的元素集合。由容斥原理即可得因此可得288288. .5.6 第二类Stirling数定

230、理例15.6.5.6.3 第二类Stirling数例1 1、把n本不同的书放入m个有编号的箱子中去（nm) )，使得没有一个箱子为空。共有多少种方法？解：这个例子实际上是第三章3.1 .1中的例1010。 通过以上分析可知所求的方式数为289289. .5.6 第二类Stirling数定理例25.6.5.6.3 第二类Stirling数例2 2、设n, ,m为正整数，nm，证明证明：我们用组合分析法证明。设有n个不同的球，有 m个盒子，它们的编号为1,2,1,2,m 。把这n个球放入盒子中去，允许有空盒且不限制放入盒子内的球数，总共有mn种方式。这是由于每个球放到m个盒子中去一共有m种方式。于

231、是n只不同的球放到m个盒子中去，由乘法法则知共有mn种方式。另一方面，由例1 1知n个不同的球放入k k个不同编号的盒子中去，并且没有一个空盒的方式数为k k! !S2 2( (n, ,k k) )。而从m个盒子中选取k k个盒子的方式数为C C( (m, ,k k) )（显然有m-k k个盒子是空的），于是由乘法法则知， n只不同的球放入k k个不同盒子中的的方式数为C C( (m, ,k k) )S2 2( (n, ,k k) )k k! !（允许有m-k k个空盒）。当k k取1 1到m ，并把这些数相加所得的和，就是n只不同的球放入 m个不同盒子中去且允许有空盒的方式数。于是有2902

232、90. .5.6 Bell数定义5.6.45.6.4Bell数若 ，则称Bn为Bell数。其组合含义为n个元素的集合划分为不相交的非空子集的方式数目。显然有B0 0=1=1。291291. .5.6 Bell数定理5.6.45.6.4Bell数Bell数Bn满足以下递推关系：证明：我们用组合分析法证明。Bn+1+1为n+1+1个元素的集合的划分数。在n+1+1个元素的集合中任意固定一个元素，然后用剩下的n个元素的各种划分来构造n+1+1个元素的划分。方法如下：先在n个元素中选取k k个元素，这里1 1k kn，组成一个集合，对它进行划分，其划分数为Bi，而将剩下的n-k k个元素和那个固定的元

233、素组成一个子集，形成n+1+1个元素的一种划分。这样得到的n+1+1个元素的划分数为，又因为n+1+1个元素的集合本身也是一个划分，它对应着。所以n+1+1个元素的集合的划分数应该是292292. .5.6 Catalan数定义5.6.4C5.6.4Catalan数一个凸n边形，通过不相交于n边形内部的对角线，把n边形拆分成若干个三角形，不同的拆分方式数目hn，称为C Catalan数。29293. .5.6 Catalan数定理12-15.6.4C5.6.4Catalan数C Catalan数满足以下递推关系：( (a)hn+1+1= =h2 2hn+ +h3hn-1 1+hnh2 2证明

234、：( (a) )的证明：如图所示的n+ +1 1边形，以v1 1vn+1+1 作为一条边的三角形的另一个顶点为vk k，k=k=2, 2,3, ,n 。三角形v1 1vk kvn+1+1 将凸n+1+1边形分割成两部分， 一部分是k k边形，另一部分是n-k+k+2 2边形。根据乘法法则，以v1 1vk kvn+1+1为一拆分三角形的拆分数应为hk khn-k k+2+2, ,k=k=2, 2,3, ,n。所得的拆分各不相同。根据加法法则有294294. .5.6 Catalan数定理12-25.6.4C5.6.4Catalan数C Catalan数满足以下递推关系：( (a)hn+1+1=

235、=h2 2hn+ +h3hn-1 1+hnh2 2( (b)()(n-3) )hn= =n( (h3hn-1 1+ +h4 4hn-2 2+hn-1 1h3)/2)/2证明：( (b) )的证明：如图所示的n边形，从v1 1点分别到n-3个顶点v3, ,v4 4,vn-1 1引出n-3条对角线。对角线v1 1vk k 把 n边形分割成两个部分，一部分是k k边形，另一部分是n-k+k+2 2边形。因此，以v1 1vk k 对角线作为拆分线的方案数为hk khn-k k+2+2, ,vk k可以是v3, ,v4 4,vn-1 1任一点，对所有这些点求和得以v2 2, ,v3,vn取代v1 1点也

236、有类似的结果。但考虑到对角线有两个顶点，同一对角线在两个顶点分别计算了一次。但该式并不给出拆分数，无疑其中是有重复的。其重复度是由于一个凸n边形的拆分有n-3 条对角线，而对其每一条边计数时该拆分都计数了一次，故重复了n-3次即上式给出的结果是hn的n-3倍。295295. .注：C Catalan数很重要，它在各种不同的范围里经常出现，许多有意义的计数问题都与这个数有关。如5.15.1例5 5中n个数的连乘积加括号的方式数，第1 1章课后习题从(0,0)(0,0)到( (n, ,n) )的格路问题中恒满足xy ，等等。5.6 Catalan数定理135.6.4C5.6.4Catalan数hn

237、+1+1=C=C(2(2n-2 2, ,n-1)/1)/n此定理的证明参照5.55.5 例3（用普通母函数法），或参考5.45.4 例3 （用迭代法）。296296. .第5章 小结 本章讨论了如何使用递推关系的方法解决组合问题， 这种方法适合利用计算机进行一步一步的计算。主要介绍了常系数齐次递推关系、常系数非齐次递推关系、迭代法、归纳法、母函数法等常用的方法，最后介绍了几种经典的递推关系。 通过学习，应该了解到一个序列既可以用它的母函数来表示，也可以用对应的递推关系来表示，只是各自的侧重点不同，利用上述方法解决组合问题是具有一定的技巧性的。 同时希望能培养了解各种解法之间的相互关系的能力。

238、重点需要掌握根据实际问题列出递推关系的技巧，列出递推关系的关键，常常是如何对所要计数的对象进行合理的分类，也就是要确定一个合理的分类标准。同时需要掌握解某几种线性、非线性常系数递推关系的方法，掌握利用差分方法解递推关系的技巧，掌握几个经典的递推关系及其组合含义。297297. .第5章 习题P111131 1、3、5 5、1010、1111、1212。298298. .本章主要介绍Plya计数定理。 群的基本概念 置换的概念及表示方法 Burnside引理 Plya定理 Plya定理的应用及推广299299. .6.1 群的概念（1）给定集合G和G上的二元运算“ ”，如满足下列条件，称集合G（

239、在运算“ ” 之下）为一个群。( (a) )封闭性：若a, ,bG，则存在cG, ,使得ab= =c；( (b) )结合律：任意a, ,b, ,cG，有( (ab) )c= =a( (bc) )；( (c) )有单位元：存在eG，任意aG，有ae= =ea= =a；( (d) )有逆元：任意aG，存在bG, ,ab= =ba= =e，b= =a-1 1。注：由于结合律成立，( (ab) )c= =a( (bc) )可记做abc。可推广对于a1 1, ,a2 2,an的乘积，结合律同样成立。 aaa= =an （共n个a相乘）。30000. .6.1 群的概念（2）例1 1、G= =1, 1,-

240、1 1在普通乘法下是群。解：验证如下 ( (a) )封闭性：(1)(1)(-1)=1)=-1,(1)(1)=1,1,(1)(1)=1,(-1)(1)1)(1)-1,(1,(-1)(1)(-1)=11)=1。( (b) )结合性：显然。( (c) )单位元素：e=1=1。( (d) )逆元素：由于(1)(1)=1,(1)(1)=1,(-1)(1)(-1)=1,1)=1,故(1)(1)-1 1=1,(=1,(-1)1)-1 1= =-1 1。30101. .6.1 群的概念（3）例2 2、G= =0,1,2,0,1,2,n-1 1在mod n的加法下是群。解：对于任意两整数，除以n的余数相等时，称

241、它们是mod n 相等的。验证如下( (a) )封闭性：任意整数除以n的余数只能是0,1,2,0,1,2,n-1 1，故封闭性成立。( (b) )结合性：显然。( (c) )单位元素：e=0=0是单位元。( (d) )逆元素：对于任意元素a G，有n-a G，且a+(+(n-a)=)=n 00mod n 故a-1 1= =n-a mod n。30202. .6.1 群的概念（4）例3、二维欧氏空间所有刚体旋转T= =T构成群。其中 证明：下面证明 T T= =T+ + 其中T T表示先对( (x, ,y) )点作T变换，再对它的结果作T 变换。( (a) )封闭性：由T T= =T+ + 可得

242、封闭性成立。( (b) )结合性：( (TT) )T= =T( (TT)=)=T+ + + 。( (c) )单位元素：e= =T0 0，即=0=0的旋转为单位元。( (d) )逆元素：T 的逆元素为T- 。30 03. .6.1 群的概念（5）若群元素的个数是有限的，称之为有限群；若群元素的个数是无限的，称之为无限群。有限群G的元素个数叫做群的阶，记做|G|。若群G的任意二元素a, ,b恒满足ab= =ba，则称G为交换群，或Abel群。设G是群，H是G的子集，若H在G原有的运算之下也是一个群，则称H为G的一个子群。30404. .6.1 群的概念（6）( (a)单位元唯一：e1 1e2 2=

243、 =e2 2= =e1 1 ( (b)消去律成立：ab= =acb= =c，ba= =cab= =c( (c)每个元的逆元唯一。( (d)()(abc) )-1 1= =c-1 1b-1 1a-1 1。( (e)G有限群，aG，则存在最小正整数r，使得ar= =e，且a-1 1= =ar-1 1。证明：( (a) ) 设有两个单位元e1 1和e2 2。根据单位元的定义，e1 1作为单位元有e1 1e2 2= =e2 2。同理，e2 2作为单位元有e1 1e2 2= =e1 1，故e1 1= =e2 2。( (b) ) 证其一。因ab= =ac，用元素a的逆元素a-1 1左乘等号两端得a-1 1

244、( (ab)=)=a-1 1( (ac) )，根据结合律有b= =c 。( (c) ) 设元素a的逆元素不惟一，有a-1 1和b，根据定义aa-1 1= =a-1 1a= =e, ,ab= =ba=e，即aa-1 1= =ab，用a-1 1左乘等号两端得b= =a-1 1 。( (d) )根据结合律得：( (abc)( )(c-1 1b-1 1a-1 1)=()=(ab)( )(cc-1 1)()(b-1 1a-1 1)=)=( (ab)()(b-1 1a-1 1)=()=(ab) )（b-1 1a-1 1)=()=(a)( )(bb-1 1)( )(a-1 1)=()=(a)( )(a-1

245、1)=)=e 。( (e) ) 设g是群G的阶|G|，aG。构造a, ,a2 2,ag, ,ag+1+1( (共g+1+1项) )，这g+1+1项同属于G，然而G只有g个不同元素，故根据鸽笼原理，其中至少有两项相等。设al= =am, ,l m。不妨设lm, ,则得al-m= =e。令l-m= =r, ,则有 aar-1 1= =e。即a-1 1= =ar-1 1。这就证明了对于任意元素aG ，存在一最小的正整数r，使得ar=e，便称r为元素a的阶。即：r= =minj j|aj j= =e, ,j jN。不难证明，对于元素a，集合H= =a, ,a2 2,ar-1 1, ,ar= =e在原来

246、群的运算下也是一个群。30505. .6.2 置换群（1）注：a1 1a2 2an是1, 1,n中元的一个排列。 n阶置换共有n! !个，同一置换用这种表示可有n! !个表示法。n阶置换又可看作1, 1,n上的一元运算，一元函数。1, 1,n到自身的1 1-1 1变换，称为置换。1, 1,n为目标集，称为n阶置换。 30606. .6.2 置换群（2）注：应该先做P1 1的置换，再做P2 2的置换；规定了若作为运算符或函数符应是后置的；n个元素的置换也有类似的结果。30707. .6.2 置换群（3）1, 1,n上的所有n阶置换在上面的乘法定义下是一个群，称之为对称群，记做Sn 。30808.

247、 .6.2 置换群（4）1, 1,n上的所有n阶置换在上面的乘法定义下是一个群，称之为对称群，记做Sn 。任一n阶群同构于一个n个文字的置换群。注：一般说1, 1,n上的一个置换群，不一定是指Sn，但一定是Sn的某一个子群。分析：建立有限群G= =a1 1, ,a2 2,an的元素ai 和某一置换群的某一置换一一对应，并且同构。例如：对于G的某一元素ai，对应有序列a1 1ai, ,a2 2ai,anai，其中所有元素都不相同，如若不然，alai= =amai，则用ai-1 1右乘上式两端，可得al= =am。矛盾。令alai= =ail, ,l=1,2,=1,2,n，故元素ai G对应于a1

248、 1, ,a2 2,an的某一排列ai1 1, ,ai2 2,ain，令ai和置换 对应，即ai pi , ,进而只需证明ai pi, ,aj j pj jaiaj j pipj j 即可。证明：据上有 30909. .6.2 置换群（5）例1 1、求等边三角形的运动群。ABC CFEDO解：对等边三角形ABC C可进行如下运动：( (a) ) 不动置换；( (b) ) 分别绕过中心的轴xx沿逆时针方向旋转120120，240240 ； 沿三角形ABC C的中线AD, ,BE, ,C CF翻转180180。( (a) )经( (a),(),(b),(),(c) )的变换, ,ABC C重合于本

249、身，但顶点换了位置。设A, ,B, ,C C分别代以1,2,1,2,3，可得顶点间的置换如下:( (b) )可以证明这6 6个置换是一个群。可以看出封闭性、结合性、单位元素、逆元素四条件均满足，故构成一个群。x 120120xABC COAC CBDABC CD180180 31010. .6.2 置换群（6）例1 1、求等边三角形的运动群。ABC CFEDO注：群的封闭性说明了多个置换的复合置换仍是上面6 6个置换之一。如根据置换 可知该置换表示三角形ABC C绕中心轴xx逆时针旋转240240，接着绕中线BE翻转180180的结果相当于绕C CF中线翻转180180。直接置换如下x 240

250、240xABC COBAC CEBC CAE180180 BAC CFABC CF180180 31111. .6.3 循环、奇循环与偶循环（1）6.3 循环、奇循环与偶循环（1）( (a1 1a2 2am)=)= 称为置换的循环表示。( (a1 1a2 2am)=()=(a2 2a3ama1 1)=()=(ama1 1am-1 1) )有m种表示方法。 若两个循环无共同文字，称为不相交的，不相交的循环相乘可交换。举例：例如5 5个文字1,2,1,2,3,4,5,4,5的置换循环(154)(154)中2, 2,3不出现，表示2 2和3保持不变, ,即(154)=(154)(2)(154)=(1

251、54)(2)(3) )注：(1)(1)置换( (a1 1a2 2ak k) )实际上只与元素的相邻状况有关，而与哪个元素为首无关。比如 (12(123)=(2)=(231)1)。(2)(2)不相交两循环的乘积可交换，例如(12(123)(45)=(45)(12)(45)=(45)(123) )。( (3) )若p=(=(a1 1a2 2an) )，则pn=(1)(2)(=(1)(2)(n)=)=e。例如31212. .6.3 循环、奇循环与偶循环（2）6.3 循环、奇循环与偶循环（1）任一置换可表成若干不相交循环的乘积。 证明：对于已知置换从1 1开始搜索，如 则得一循环如若包含了(1,2,(

252、1,2,n) )的所有文字，则搜索停止。否则，从余下的文字中的任一文字开始，如法进行，再得一循环。如此反复直到所有文字都取完为止。这样便得到一组互不相交的循环之积。循环的顺序是可以交换的，但是，用p表示若干循环之积是惟一的。31 13. .6.3 循环、奇循环与偶循环（3）6.3 循环、奇循环与偶循环（2）例1 1、一副扑克牌，编号从1 1到5252，分成1 126,26,27275252两部分，互相交错插入（洗牌），即第2727张插入第2 2张，第1 1张不动，第2 2张退为第3张，这样操作一次相当于一个置换p。 解：可见p分解成1 1阶循环2 2个，2 2阶循环1 1个，8 8阶循环6 6

253、个。由此可见这样的操作重复8 8次又恢复到原来的模样。故31414. .6.3 循环、奇循环与偶循环（4）6.3 循环、奇循环与偶循环（2）2 2阶循环( (i j j) )叫做i和j j的对换（换位）。任一循环都可以表示为对换的积 。 证明：这只要给出一个分解的方法就可以了。例如31515. .6.3 循环、奇循环与偶循环（5）6.3 循环、奇循环与偶循环（2）注：任一循环分解成若干个换位之积不是惟一的，甚至于连换位的数目都不相同，例如 (12(123)=(12)(1)=(12)(13)=(12)(1)=(12)(13)( )(31)(11)(13) )但有一个性质却是不变的，即换位数目的奇

254、偶性不变。即一个置换分解成若干个数目的换位之积，可分解成奇数个换位之积，不可能表示为偶数个换位之积。同样，分解成偶数个换位之积的置换不可能表示为另一个奇数个换位之积。其理由如下：设表达式设k kl,1 ,1l, ,k kn, ,其中f是由不含xk k和xl的项组成的部分。若xk k和xl互换，我们来看看对F的各项的影响，( (xi-xl)( )(xi-xk k) )实际上不变，f 由于不含xk k和xl，故不受影响。xk k和xl互换的结果使F变号，或用( (xk k, ,xl) )F = =-F 或( (k k, ,l) )F = =-F来表示。p是某一置换，p 分解成换位之积，若分解成奇数

255、个换位之积，则p作用于f 的结果使f 变号；若p分解成偶数个换位之积，则p作用于f 的结果不变。p作用于f 的结果是固有的，它取决于本身，故p分解成奇数个或偶数个换位之积也取决于p 本身，而不是依赖于分解过程。31616. .6.3 循环、奇循环与偶循环（6）若一个置换可分解为奇数个对换的积，叫做奇置换；若分解为偶数个对换的积，叫做偶置换。例2 2、 0 08 87 76 65 54 432 21 11 12 26 630 04 48 85 57 731717. .6.3 循环、奇循环与偶循环（7）Sn中所有偶置换构成一阶为( (n!)/2!)/2的子群称为交代群，记做An。 证明：先证An是

256、Sn的子群。单位元是偶置换，故An非空。(1)(1)封闭性：若p1 1, ,p2 2是偶置换，则p3= =p1 1p2 2也是偶置换，故封闭性成立。(2)(2)结合律：显然成立。( (3) )单位元素：置换群的单位元素本身就是偶置换。(4)(4)逆元素：( (i k k) )的逆元素为( (i k k) )，p=(=(i1 1 j j1 1)( )(i2 2 j j2 2)()(ik k j jk k) )的逆元素为p-1 1=(=(ik k j jk k)( )(ik k-1 1 j jk k-1 1)()(i2 2 j j2 2)( )(i1 1 j j1 1) )，有pp-1 1=(=(

257、i1 1 j j1 1)( )(i2 2 j j2 2)()(ik k j jk k)( )(ik k j jk k)()(i2 2 j j2 2)( )(i1 1 j j1 1) )=(=(i1 1 j j1 1)( )(i2 2 j j2 2)()(ik k-1 1 j jk k-1 1)( )(ik k-1 1 j jk k-1 1)()(i2 2 j j2 2)( )(i1 1 j j1 1)=)=(=(i1 1 j j1 1)( )(i1 1 j j1 1)=(1)(2)()=(1)(2)(n)=)=e同理有p-1 1p=(1)(2)(=(1)(2)(n)=)=e令 Bn = =Sn

258、An即Bn 为Sn中奇置换的全体。任取一个换位( (i j j) )，对于An的任一置换p，则( (i j j) )p是奇置换，即( (i j j) )p Bn。故|An|Bn| 。同理，对于集合Bn的任一置换q，显然有( (i j j) )q An，即( (i j j) )q是偶置换。故 |Bn|An| 。由和可得|An|=|Bn|，但|An|+|Bn|= =n! ! |An|=(=(n!)/2!)/231818. .6.4 Burnside引理（1）先观察群S3，A3， S4 4，A4 4，以增加感性认识。 S3=(1)(2)(1)(2)(3),(12),(2),(12),(23),(1)

259、,(13),(12),(123),(1),(132)2) A3=(1)(2)(1)(2)(3),(12),(123),(1),(132)2) S4 4=(1)(2)(1)(2)(3)(4),(12),(1)(4),(12),(13),(14),(2),(14),(23),(24),(),(24),(34),(124),(123), ),(124),(1(124),(132),(12),(134),(142),(144),(142),(143),(2),(234),(244),(243),),(12(1234),(1244),(1243),(1),(1324),(124),(1342),(142

260、42),(1423),(14),(1432),2),(12)(12)(34),(14),(13)(24),(14)(2)(24),(14)(23) ) A4 4=(1)(2)(1)(2)(3)(4),(12)(4),(123),(124),(1),(124),(132),(12),(134),(142),4),(142),(14(143),(2),(234),(244),(243),(12)(),(12)(34),(14),(13)(24),(14)(2)(24),(14)(23) )一般地，可把Sn中的任一置换p分解成若干互不相交的循环乘积。设其中k k阶循环出现的次数为ck k，k k=1

261、,2,=1,2,n，k k阶循环出现ck k次，用( (k k) )ck k表示。31919. .6.4 Burnside引理（2）Sn中P的循环格式均可表示为(1)(1)c1 1(2)(2)c2 2(n) )cn, ,Sn中有相同格式的置换全体构成一个共轭类。 Sn中属(1)(1)c1 1(2)(2)c2 2(n) )cn共轭类的元素的个数为n!/(!/(c1 1! ! c2 2!.!.cn!1!1c1 12 2c2 2ncn) )证明：(1)(1)c1 1(2)(2)c2 2(n) )cn格式为：一个长度为k k的循环有k k种表示，ck k个长度为k k的循环有 ck k! !k kck

262、 k种表示。1,2,1,2,n 的全排列共有n! !个，给定一个排列，装入格式得一置换，除以前面的重复度得n!/(!/(c1 1! ! c2 2!.!.cn!1!1c1 12 2c2 2ncn) )个不同的置换。32020. .6.4 Burnside引理（3）例1 1、求S4 4中不同循环格式的共轭类个数。 解：根据上述定理，可得出S4 4中(1)(1)4 4共轭类有4!/(4!14!/(4!14 4)=1)=1个置换，即(1)(2)(1)(2)(3)(4)(4)S4 4中(2)(2)1 1共轭类（ 即(1)(1)2 2(2)(2)1 1）有4!/(2!1!14!/(2!1!12 22 21

263、 1)=6)=6个置换，即(12),(1(12),(13),(14),(2),(14),(23),(24),(),(24),(34)4)S4 4中( (3) )1 1共轭类（ 即(1)(1)1 1( (3) )1 1）有4!/(1!1!14!/(1!1!11 131 1)=8)=8个置换，即(12(123),(124),(1),(124),(132),(12),(134),(142),(144),(142),(143),(2),(234),(244),(243) )S4 4中(4)(4)1 1共轭类有4!/(1!4!/(1!1 14 41 1)=6)=6个置换，即(12(1234),(1244

264、),(1243),),(1(1324),(124),(1342),(14242),(1423),(14),(1432),2),S4 4中(2)(2)2 2共轭类有4!/(2!4!/(2!1 12 22 2)=)=3个置换，即(12)(12)(34),(14),(13)(24),)(24),(14)(2(14)(23) )32121. .6.4 Burnside引理（4）设G是1, 1,n上的一个置换群。GSn, ,k k1, 1,n，G中使k k保持不变的置换全体，称为k k不动置换类，记做Zk k 。置换群G的k k不动置换类Zk k是G的一个子群。 如：G= =e,(12),(,(12),

265、(34),(12)(4),(12)(34)4) Z1 1=e,(,(34)4), ,Z2 2=e,(,(34)4), ,Z3=e,(12),(12), ,Z4 4=e,(12),(12)可见， Zk k是G中有“因子” k k的置换全体。又如A4 4=e,(12,(123),(124),(1),(124),(132),(12),(134),(142),4),(142),(14(143),(2),(234),(244),(243),(12)(),(12)(34),(14),(13)(24),(14)(2)(24),(14)(23) ) Z1 1=e,(2,(234),(244),(243) ),

266、 ,Z2 2=e,(1,(134),(144),(143) ) Z3=e,(124),(142),(124),(142), ,Z4 4=e ,(12,(123),(1),(132)2) 证明：封闭性：结合性：显然成立。有单位元：G的单位元属于Zk k 。有逆元：32222. .6.4 Burnside引理（5）注：满足等价类的3个条件：( (a) )自反性；( (b) )对称性；( (c) )传递性。设G= =e,(12),(,(12),(34),(12)(4),(12)(34)4)，在群G作用下，1 1变2 2，2 2变1 1，3变4 4，4 4变3，但1 1或2 2不能在G作用下变3或4

267、4，同样3或4 4不能变为1 1或2 2，有E1 1= =E2 2= =1,21,2, ,E3= =E4 4=3,4,4。由G定义的关系R：若存在pG，使得 ，则称k kRj j。如果满足k kRk k；k kRj j 则j jRk k；k kRj j，j jRl 则k kRj j ，称R是1, 1,n上的一个等价关系。一般1, 1,n上的G将1, 1,n划分成若干等价类，元素k k所属的等价类记为Ek k 。含目标集元素k k的在G作用下的等价类也称为含k k的轨道（踪迹）。32 23. .6.4 Burnside引理（6）设G是1, 1,n上的一个置换群，Ek k是1, 1,n在G的作用下

268、包含k k的等价类，Zk k是k k不动置换类，有|Ek k|Zk k|= =|G| 。证明：若|Ek k|= =l，不失一般性，设Ek k= =a1 1(=(=k k),),a2,2,al，a1,1,a2 2,al是l个不超过n的正整数，而且各不相等。既然a1,1,a2 2,al属于同一个等价类，故存在属于G的置换pi使得即置换pi 使数k k变为等价类中的ai 。P=p1 1, ,p2 2,pl 是属于群G的置换的集合，但不是一个群。作 Gj j = =Zk k pj j，j j=1,2,=1,2,l。由于即数k k在 pj j Zk k pj j 的作用下变为 aj j。Gj j= =Z

269、k k pj j 的元素属于G，而且当ij j时，GiGj j= = 。另一方面，凡属于G的任一置换p，有，即k k在p作用下变为某一元素aj j，依据元素k k的等价类，故存在pj j G，使得 依据Zk k的定义，则有p是G的任意元素，故有 32424. .6.4 Burnside引理（7）定理6.86.8举例如下设G= =A4 4= =e,(12,(123),(124),(1),(124),(132),(12),(134),(142),4),(142),(14(143),(2),(234),(244),(243),(12)(),(12)(34),(14),(13)(24),(14)(2)

270、(24),(14)(23) ) E1 1= =1,2,1,2,3,4,4, ,Z1 1= =e,(2,(234),(244),(243) )则A4 4中存在单位元素p1 1= =e 使存在置换p2 2=(12)(=(12)(34)4)使存在置换p3 =(1=(13)(24)(24)使存在置换p4 4=(14)(2=(14)(23) )使 Z1 1p1 1=e,(2,(234),(244),(243) )Z2 2p22=(12)(12)(34),(124),(124),(124),(123) )Z3 p3 =(1(13)(24),(1)(24),(132),(12),(134)4)+)+)Z4

271、4p4 4=(14)(2(14)(23),(14),(143),(142),(142)32525. .6.4 Burnside引理（8）Burnside引理：设G= =a1 1, ,a2 2,ag是目标集1, 1,n上的置换群，每个置换都写成不相交循环的乘积。G将1, 1,n换分成l个等价类。c1 1( (ak k) )是在置换ak k的作用下不动点的个数，也就是长度为1 1的循环的个数。则不同等价类的个数l= =c1 1( (a1 1)+)+c1 1( (a2 2)+)+c1 1( (ag) )/ /|G|。定理6.96.9举例如下令G= = e,(12),(,(12),(34),(12)(

272、4),(12)(34)4)，设 222222221111111100110011110011000000000012123448 8| Zk k |(1)(1)4 4(2)(2)0 0( (3) )0 0(4)(4)0 0(1)(1)2 2(2)(2)1 1( (3) )0 0(4)(4)0 0(1)(1)2 2(2)(2)1 1( (3) )0 0(4)(4)0 0(1)(1)0 0(2)(2)2 2( (3) )0 0(4)(4)0 04 42 22 20 0(1)(2)(1)(2)(3)(4)(4)(12)(12)(3)(4)(4)(1)(2)(1)(2)(34)4)(12)(12)(3

273、4)4)格式c1 1( (aj j) )k ksjk jkaj j32626. .6.4 Burnside引理（9）证明：作表如下|Z1 1| |Z2 2|Zn|Zk k|c1 1( (a1 1) )c1 1( (a2 2) )c1 1( (ag) )s1111s1212 s1 1ns2121s2222 s2 2n sg11sg22 sgna1 1a2 2agc1 1( (aj j) )1212 nk ksjk jkaj j32727. .6.4 Burnside引理（10）例2 2、一正方形分成4 4格，2 2种颜色着色，有多少种方案使之图像不同？其中：图象是看上去不同的图形；方案：经过转动

274、相同的图象算同一方案；图象数总是大于方案数。 解：每格有两种颜色可供选择，故有如图所示的1616种可能方案。C C11C C2 2 C C3C C4 4 C C5 5 C C6 6 C C7 7 C C8 8 C C9 9 C C1010 C C1111 C C1212 C C1 13 C C1414 C C1515 C C1616当每个图都绕过中心点的轴按逆时针方向旋转9090，180180，270270时，得到1616种图象的又一种排列，可以看作是1616种图像的一种置换。分别讨论如下：( (a) )旋转0 0为不动置换，有p1 1=(1)(2)(16)=(1)(2)(16)( (b) )

275、旋转9090，这时，C C3被C C4 4取代，C C4 4被C C5 5取代，C C1616被C C1 13取代，有p2 2=(1)(2)(=(1)(2)(3456)(78910)(1112)(1456)(78910)(1112)(13141516)141516) ( (c) )旋转180180，这时，C C3和C C5 5互换， C C4 4和C C6 6互换，故有p3=(1)(2)(=(1)(2)(35)(46)(79)(810)(11)(12)(15)(46)(79)(810)(11)(12)(1315)(1416)15)(1416)( (d) )旋转270270，有p4 4=(1)(

276、2)(654=(1)(2)(6543)(10987)(1112)(1615141)(10987)(1112)(16151413) )不同等价类的个数： 32828. .6.4 Burnside引理（11）例3、一个圆环上装着4 4个珠子，每个珠子或者为蓝色，或者为红色，问有多少种不同的方案？其中：经过刚体运动使之吻合的算同一种方案。 解：这个问题可看作前例正方形的四格着色情况，但考虑到空间刚体运动，除了和前例一样的p1 1, ,p2 2, , p3, , p4 4外，其置换群还包含如下置换：C C11C C2 2 C C3C C4 4 C C5 5 C C6 6 C C7 7 C C8 8 C

277、 C9 9 C C1010 C C1111 C C1212 C C1 13 C C1414 C C1515 C C1616(e) )沿l1 1轴翻转180180，有p5 5=(1)(2)(=(1)(2)(36)(45)(710)6)(45)(710)(89)(1112)(1(89)(1112)(13)(15)(1416)(15)(1416)(f) )沿l2 2轴翻转180180，有p6 6=(1)(2)(=(1)(2)(34)(56)(78)4)(56)(78)(910)(1112)(1(910)(1112)(1315)(14)(16)15)(14)(16)( (g) )沿l3轴翻转18018

278、0，有p7 7=(1)(2)(=(1)(2)(3)(46)(5)(7)(810)(9)(11)(12)(46)(5)(7)(810)(9)(11)(12)(1(1314)(15)(16)14)(15)(16)( (h) )沿l4 4轴翻转180180，有p8 8=(1)(2)(4)(=(1)(2)(4)(35)(6)(8)(79)(10)(11)(12)5)(6)(8)(79)(10)(11)(12)(1(1316)(1415)16)(1415)不同等价类的个数： l1 1l2 2l3l4 432929. .6.5 Plya定理（1）Plya定理 ：设是目标集1, 1,n上的置换群，每个置换都

279、写成不相交循环的乘积， 是置换 的循环的节数，用m种颜色对1, 1,n中的元素着色，则不同着色方案数为分析： Plya定理中的群是作用在n个对象上的置换群，相应地，Burnside定理中的G 群是在这n个对象上用m种颜色进行染色后的方案集合上的置换群。G 群与群之间的联系是这样的：对应于群的元素，相应地在染色方案集合上也诱导一个属于G 的置换p 。只要证明 即可。330 0. .6.5 Plya定理（2）举例分析如下：在证明以前，先就前面的例子进行分析，然后推广到一般。右图的染色方案见上节例2 2题中的图。其置换群为分别对应于上节例题中方案集的置换。p1 1=(1)(2)(16)=(1)(2)

280、(16)p2 2=(1)(2)(=(1)(2)(3456)(78910)(1112)(1456)(78910)(1112)(13141516)141516)p3=(1)(2)(=(1)(2)(35)(46)(79)(810)(11)(12)(15)(46)(79)(810)(11)(12)(1315)(1416)15)(1416)p4 4=(1)(2)(654=(1)(2)(6543)(10987)(1112)(1615141)(10987)(1112)(16151413) )仔细观察其中的关系，首先，不难发现2 21 1 3 4 4331 1. .6.5 Plya定理（3）其次，还可以发现，

281、在pi作用下不变的图像正好是对应的的循环节中的对象染以相同的颜色所得到的图像。例如， 对应的p2 2中一阶循环节为(1)(2)(1)(2)。见图，图像C C1 1, ,C C2 2正好是1,2,1,2,3,4 ,4着以同一种颜色所得的结果。又如 对应的p3中的一阶循环节为(1)(2)(11)(12)(1)(2)(11)(12)，正好是1 1和3, ,2 2和4 4分别着以相同的颜色的结果。2 21 1 3 4 4C C1 1C C2 2C C1111C C1212332 2. .6.5 Plya定理（4）Plya定理 ：设是目标集1, 1,n上的置换群，每个置换都写成不相交循环的乘积， 是置换

282、 的循环的节数，用m种颜色对1, 1,n中的元素着色，则不同着色方案数为证明： 假定n个对象用m种颜色进行染色后的方案集合为S，显然。 的每一元素对应于n个对象的一个排列，也对应了S中的mn个染色方案的一个排列，记作aj j 。这样n个对象上的群 ，对应于作用在S上的群G。故。而且有。和前面讨论一样，可得S 按G分成不同等价类的个数为 333. .6.5 Plya定理（5）凸多面体与一个顶点相关的面角之和与36060的差称为该顶点的欠角。凸多面体各顶点欠角的和为720720 。注：欠角定理主要是为了解决正多面体及一些对称多面体的计算问题。 例如：用正5 5边形搭成的正多面体的面数：正5 5边形

283、的顶角=(5=(5-2)2)180180/5=108/5=108欠角=36060-3108108= =36 6 顶点数=720=720/ /36 6=20(=20(个) )一个顶点3条边，重复度为2,2,边数=20=203/2=/2=30 0条一个顶点相关3个面，重复度为5 5，面数=20=203/5=12/5=12个 334 4. .6.6 Plya定理的应用（1）例1 1、等边三角形的3个顶点用红，兰，绿3着色，有多少种方案？ 解： 等边三角形v1 1v2 2v3的刚体运动包括：分别绕三角形的中心旋转0 0,120,120,240,240，以及过三顶点的中线翻转。如图所示，得群：十种染色方

284、案如图v1 1v2 2v3v3v1 1v2 2v2 2v3v1 1335 5. .6.6 Plya定理的应用（2）例2 2、甲烷C CH4 4的4 4个键任意用H, , C C1 1, ,C CH3,C,C2 2H5 5 连接，有多少种方案？ 解： 问题相当于对正四面体的四个顶点用四种颜色着色，求不同的方案数。使正四面体v1 1v2 2v3v4 4重合的刚体运动有三类，一是不动置换；一是绕过顶点的中心线xx旋转120120,240,240，置换格式为(1)(1)1 1( (3) )1 1，分别有4 4个 ；一是绕如v1 1v2 2, ,v3v4 4中点取线yy 旋转180180，置换格式为(2

285、)(2)2 2，分别有3个 ；如图，旋转群G的元素为：v1 1v2 2v3v4 4xxyy336 6. .6.6 Plya定理的应用（3）例3、正6 6面体的6 6个面分别用红，蓝两种颜色着色，有多少方案？ 解： 使正六面体各面重合的刚体运动群，有如下几种情况。不动置换，即单位元素(1)(2)(1)(2)(3)(4)(5)(6)(4)(5)(6)，格式为(1)(1)6 6。绕过(1)(1)面(6)(6)面中心的AB轴旋转9090。对应置换有(1)(2(1)(2345)(6)45)(6)，(1)(54(1)(5432)(6)2)(6)，格式为(1)(1)2 2(4)(4)1 1。正六面体有三个对

286、面，故同类的置换有6 6个。绕AB轴旋转180180的置换有(1)(24)(1)(24)(35)(6)5)(6)，格式为(1)(1)2 2(2)(2)2 2，同类的置换有3个。(1)(1)(2)(2)(6)(6)(4)(4)（3）(5)(5)9090,180,180 AB337 7. .6.6 Plya定理的应用（4）例3、正6 6面体的6 6个面分别用红，蓝两种颜色着色，有多少方案？ 绕C CD轴旋转180180的置换为(16)(25)(16)(25)( (34)4)，格式为(2)(2)3，正六面体中对角线位置的平行的棱有6 6对，故同类的置换有6 6个。绕正六面体的对角线EF旋转12012

287、0，绕EF旋转120120的置换为( (326)(154)26)(154)。绕EF旋转-120120的置换为(62(623)(451)(451)，格式为( (3) )2 2。正六面体的对角线有4 4，故同类的置换8 8个。于是不同的染色方案数为(1)(1)(2)(2)(6)(6)(4)(4)（3）(5)(5)180180 C CD(1)(1)(2)(2)(6)(6)(4)(4)（3）(5)(5)EF120120 338 8. .6.6 Plya定理的应用（5）例4 4、用2 2种颜色给正6 6面体的8 8个顶点着色，有多少方案？ 解：和例3相似，不过把六个面的着色改为8 8个点的着色后，使正六

288、面体重合的关于顶点的运动群有所改变，包括：单位元素(1)(2)(1)(2)(3)(4)(5)(6)(7)(8)(4)(5)(6)(7)(8)，格式为(1)(1)8 8。绕过xx轴旋转9090 的置换分别为(12(1234)(5678),(44)(5678),(4321)(8765),21)(8765),格式为(4)(4)2 2，同类的置换有6 6个。绕xx轴旋转180180的置换为(1(13)(24)(57)(68)(24)(57)(68)，格式(2)(2)4 4，同类的置换有3个。yyzzxx1 12 24 435 56 68 87 7339 9. .6.6 Plya定理的应用（6）例4 4

289、、用2 2种颜色给正6 6面体的8 8个顶点着色，有多少方案？ 绕yy轴旋转180180的置换为(17)(26)(17)(26)(35)(48)5)(48)格式为(2)(2)4 4，同类的置换有6 6个。绕zz轴旋转120120的置换分别为(8(836)(425)(1)(7)6)(425)(1)(7)(6(638)(524)(1)(7)8)(524)(1)(7)格式为( (3) )2 2(1)(1)2 2，同类的置换有8 8个。依据Plya定理，不同的方案数为yyzzxx1 12 24 435 56 68 87 734040. .6.6 Plya定理的应用（7）例5 5、在正6 6面体的每个面

290、上任意做一条对角线，有多少方案？ 解：因为在每个面上作一条对角线的方式有2 2种，所以可参照面2 2着色的思路。但顶面和底面上的对角线无论怎么作，绕xx 转动9090，都不会有不变的图象。绕另两个同类型轴转动也有同样的问题。而绕其他类型的轴转动及绕xx转动180180都可等同于面的2 2着色。于是不同的方案数其中0 0 6 6 2 23这一项正是体现了上面所作的与面2 2着色不同之处的分析。yyzzxx(1)(1)(2)(2)(6)(6)(4)(4)（3）(5)(5)34141. .6.6 Plya定理的应用（8）例6 6、骰子的6 6个面分别有1,61,6点，有多少种不同的方案？ 解I：问题

291、相当于对正六面体的六个面，用六种颜色对之染色，要求各面的颜色都不一样，求不同的方案数。6 6个面用六种颜色涂染，各个面颜色不同，应有6!6!种方案。但其中有的经旋转使之重合的算同一种。依据例3，可知旋转运动群共有2424个置换，观察这6!6!种方案在这群的作用下的置换关系。设6!6!种方案为s1 1, ,s2 2,s6!6!，单位元素对应的置换为( (s1 1)( )(s2 2)()(s6!6!) )。由于6 6个面颜色均不相同，故对其它2 23个置换没有一种方案都保持不变的。设2424个置换中p0 0为单位元素，即不动置换。其余为p1 1, ,p2 2,p2 23 。因此有c1 1( (p0

292、 0)=6!,)=6!,c1 1( (p1 1)=)=c1 1( (p2 2)=)=c1 1( (p3)=)=c1 1( (p2 23)=0)=0。根据Burnside引理，不同的方案数应为34242. .6.6 Plya定理的应用（9）例6 6、骰子的6 6个面分别有1,61,6点，有多少种不同的方案？ 解II：下面用的Plya定理和容斥原理。使正六面体重合的置换群见例3。用m种颜色对正六面体的六个面进行涂染可得不同方案数为nm ，有34 43. .6.6 Plya定理的应用（10）令li = =用i种颜色对正六面体的六个面进行涂染所得不少于i种颜色的方案数。34444. .6.7 母函数形

293、式的Plya定理（1）将Plya定理推广到母函数型，不仅可以计数，还可以对状态进行列举。设G= =a1 1, ,a2 2,ag是目标集1, 1,n上的置换群，每个置换都写成不相交循环的乘积，c( (ak k) )是置换ak k的循环的节数，ci( (ak k) )是置换ak k中i阶的循环因子的节数，用m种颜色b1 1, ,b2 2,bm对1, 1,n中的元素着色，则不同着色方案数为l= =mc( (a1 1) )+ +mc( (a2 2) )+mc( (ag) )/ /|G|。其中mc( (aj j) )用( (b1 1+ +b2 2+bm) )c1 1( (aj j) )( (b1 12

294、2+ +b2 22 2+bm2 2) )c2 2( (aj j) ) ( (b1 1n+b2 2n+bmn) )cn( (aj j) ) 代替，形成以b1 1, ,b2 2,bm为变元的n次对称多项式P( (b1 1, ,b2 2,bm) )。 34545. .6.7 母函数形式的Plya定理（2）例1 1、有3种不同颜色的珠子，串成4 4颗珠子的项链，有哪些方案？ 解：如图所示，使之重合的运动包括：关于圆环中心旋转9090和180180；关于xx和yy轴翻转180180。故有置换群G为其中格式为(1)(1)4 4的一个，(4)(4)1 1的两个，(2)(2)2 2的3个， (1)(1)2 2

295、(2)(2) 的两个。根据Plya定理不同方案数为v1 1v2 2v4 4v3yyxx34646. .6.7 母函数形式的Plya定理（3）例1 1、有3种不同颜色的珠子，串成4 4颗珠子的项链，有哪些方案？ 具体方案是其中b2 2rg的系数为2 2，即由两颗蓝色珠子，一红一绿组成的方案有2 2种。即brgbbbgr34747. .6.7 母函数形式的Plya定理（4）例2 2、4 4颗红色珠子嵌在正6 6面体的4 4个顶点上，有多少方案？ 解：问题相当于用两种颜色对正六面体的顶点着色，求两种颜色相等的方案数。从上节例4 4知，置换群的节数为2424，其中格式为(1)(1)8 8的一个， (4

296、)(4)2 2的6 6个，(2)(2)4 4的9 9个，(1)(1)2 2( (3) )2 2的8 8个，故 相应的方案如下34848. .6.7 母函数形式的Plya定理（5）解III：从上节例3知，置换群的节数为2424，其中格式为(1)(1)6 6的一个，(1)(1)2 2(4)(4)1 1的6 6个，(1)(1)2 2(2)(2)2 2的3个，(2)(2)3的6 6个，( (3) )2 2的8 8个，故 例3、骰子的6 6个面分别有1,61,6点，有多少种不同的方案？ 34949. .6.7 母函数形式的Plya定理（6）例4 4、（分配问题）将四个球a, ,a, ,b, ,b放到两个

297、不同的盒子A、B中，问有多少种不同的放法？ 解：设D= =a1 1, ,a2 2, ,a3, ,a4 4，其中a1 1= =a2 2= =a, ,a3= =a4 4= =b。对任何一种方法，对调a1 1与a2 2，或a3与a4 4仍属同一种方法，故相应的置换群G为(1)(2)(1)(2)(3)(4),(12)()(4),(12)(3)(4),(1)(2)()(4),(1)(2)(34),(12)(4),(12)(34)4)将不同的两个盒子看作是两种颜色，根据Plya定理m=(2=(24 4+2+23+2+23+2+22 2)/4=9)/4=9故可分配的方法为 ( ( )( )(a a b b)

298、,(),(a)( )(a b b),(),(b)( )(a a b),(),(a a)( )(b b),(),(a b)( )(a b) )( (b b)( )(a a),(),(a b b)( )(a),(),(a a b)( )(b),(),(a a b b)( )( ) )35050. .6.8 图的计数（1）例1 1、3个顶点的无向简单图有多少个不同形的图形 ？ 解：简单图问题相当于对n个无标志顶点的完全图用两种颜色进行着色，求不同方案数的问题。如用两种颜色x, ,y，消去着y颜色的边，即得一个n个顶点的简单图。三个顶点的无向图，从6.66.6例1 1知从P可知对3个顶点的无向简单图的

299、边着色，其中三条边都着以色x的有1 1种，两条边，或一条边，或无一条边着色x的方案各1 1种，把着以色y的边消除得:( (a)()(b)()(c)()(d) )35151. .6.8 图的计数（2）例2 2、4 4个顶点的无向图有多少个不同的图形 ？ 解：右图的关于顶点的置换群为对称群S4 4。因为下面观察在S4 4作用下，e1 1, ,e2 2, ,e3, ,e4 4, ,e5 5, ,e6 6的变换。例如对应于置换p1 1=(=(v1 1, ,v2 2) )，即对应于置换( (v1 1v2 2)( )(v3)( )(v4 4) )，e1 1=(=(v1 1, ,v2 2) )不变，e2 2

300、=(=(v3, ,v4 4) )不变。但e3=(=(v2 2, ,v3) )变为e5 5=(=(v1 1, ,v3) )，e4 4=(=(v1 1, ,v4 4) )被e6 6=(=(v2 2, ,v4 4) )所取代。故有( (v1 1v2 2) )对应于边的置换v1 1v2 2v3v4 4e1 1e2 2e3e4 4e5 5e6 6p1 1=(=(v1 1, ,v2 2) )v2 2v1 1v3v4 4e1 1e2 2e5 5e6 6e3e4 435252. .6.8 图的计数（3）下面把群S4 4与G6 6所对应的置换列于表中（见P34545表4.44.4），从表中可知G6 6群的格式为

301、(1)(1)6 6的一个，(1)(1)2 2(2)(2)2 2的9 9个，(2)(4)(2)(4)的6 6个，( (3) )2 2的8 8个。故依据母函数型式的Plya定理得对应的图像为：( (a) )( (b) )( (c) )( (d) )( (e) )( (f) )( (g) )35 53. .6.8 图的计数（4）例3、求4 4个顶点的不同构的有向图的个数。 解：和上例不同的是四个顶点的有向图的边不是6 6条，而是1212条。与上例相似，可以从S4 4导出关于e1 1, ,e2 2,e1212的阶置换群，其格式为(1)(1)1212的一个，(1)(1)2 2(2)(2)5 5的6 6个

302、，( (3) )4 4的8 8个，(2)(2)6 6的3个，(4)(4)3的6 6个。依据Plya定理可得其中x2 2 y1010的系数为5 5，即有两条边的四个顶点的有5 5种。如图e1 1e2 2e5 5e6 6e3e4 4e7 7e8 8e1010e9 9e1111e1212( (b) )( (a) )( (c) )( (d) )( (e) )35454. .6.9 Plya定理的若干推广（1）不相交集合上的置换笛卡儿积上的置换复合置换染色格式等价的置换（De Bruij jn定理）35555. .第6章 小结本章重点研究了Plya计数定理。在按照一个置换群所导出的等价关系把一个集合分成

303、的等价类的计数中，该定理是最有用的。本章从群的基本概念着手，熟悉一些基本的有限群，特别是正多面体的转动群（分别以顶点，棱，面为目标集的置换群），及其置换格式。熟悉一种正多面体的转动群的置换表示关键在于熟悉对应的转动轴。本章的另一个重点是Burnside引理，明白了Burnside引理再理解Plya定理就不难了。只是Burnside引理实际使用起来不太方便，而Plya定理用起来是比较方便的。Plya定理还可以结合母函数进行计数或列举，其他重要应用包括图、树、布尔函数的计数等。了解了这些问题就可以对Plya定理有更深入也更直观的理解。35656. .第6章 习题P354541111、1414、1515、1616。35757. .组合数学主要研究满足一定条件的组态（一种安排）的存在性、计数及构造等方面的问题。组合数学大体上可分为组合计数、组合设计、组合矩阵、组合优化等方面。本课程主要讨论了基本的组合计数问题。在本课程中我们将组态称为组合模型，我们将从中学数学中已出现的排列、组合的计数着手，一直讨论到用火柴能搭出多少个不同的足球这样的有趣的问题。要求是熟练掌握基本的计数方法，能够灵活运用，解决问题。无论问题以计算题还是证明题的形式出现，对于中等难度以下的问题，都应能够解答。 35858. .结束谢 谢35959. .期末考试注：36060. .