组合数学PPT课件.ppt

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

1、组合数学课件课程简介课程简介相关课程相关课程使用教材使用教材数学分数学分析析高高等等代代数数离散离散数学数学书名名组合数学组合数学（第（第三三版）版）作作孙淑玲淑玲 版版社社中中国国科科学学技技术大大学学版版社社 本本课课程程针对对计计算算机机科科学学中中的的一一个个重重学学科科组组合合数数学学，组组合合数数学学数数学学的的一一个个分分支支，研研究究事事物物在在结结定定模模式式的的配配置置，研研究究配配置置的的在在性性，有有配配置置的的计计数数和和分分类类以以及及配配置置的的各各性性质。组组合合数数学学在在计计算算机机科科学学中中有有着着极极其其广广泛泛的应的应用用。组合学问题解方法组合学问题

2、解方法层不不穷、干、干变万万，应，应以以理解理解为基基础，善善结结各各技巧技巧，掌握掌握科科学的组学的组织和推和推理方法。理方法。目目录（1 1）引引言言第第1 1章章 排排列与列与组合组合 1.1 加法法则和乘法法则 1.2 排列 1.3 组合 1.4 二项式定理 1.5 组合恒等式及其含义 1.6 模型转换 本章小结 习题第第2 2章章 鸽笼原鸽笼原理理 2.1 鸽笼原理 2.2 鸽笼原理的推广 2.3 Ramsey定理 本章小结 习题第第3 3章章 容斥原容斥原理理 3.1 容斥原理 3.2 重集r-组合 3.3 错排问题 3.4 有限制排列 3.5*一般有限制排列 3.6*广义容斥原理

3、 本章小结 习题第第4 4章章 母函母函数数 4.1 母函数的基本概念 4.2 母函数的基本运算 4.3 在排列组合中的应用 4.4 整数的拆分 4.5 Ferrers图目目录录目目录（2 2）4.6*在组合恒等式中的应用 本章小结 习题第第5 5章章 递推关系递推关系 5.1 递推关系的建立 5.2 常系数线性齐次递推关系 5.3 常系数线性非齐次递推关系 5.4 迭代法与归纳法 5.5 母函数在递推关系中的应用 5.6*典型的递推关系 本章小结 习题第第6 6章章 P P lyalya定理定理 6.1 群的概念 6.2 置换群 6.3 循环、奇循环与偶循环 6.4 Burnside引理 6

4、5 Plya定理 6.6 Plya定理的应用 6.7 母函数形式的Plya定理 6.8*图的计数 6.9*Plya定理的若干推广 本章小结 习题*课程课程结结注加*的章节一般性了解 在性问题在性问题 计数计数和和枚枚举 问题问题 性问题性问题 科科学的组学的组织 科科学的学的推推理理 古老古老 年年轻 练习习 思考思考结结 笔笔记组合数学组合数学研究研究的中的中心心问题问题是按照是按照一定的一定的规则则来安来安排有限多个对排有限多个对象象 有限多个对应的排，合的排非在不在时，的问题证明定的在。在性问题。的排在，则有多不同的排，经常样的问题有多的排方？对排的方分类？计数问题。一个组合问题有解，

5、则其一特定解的算法，的性问题。算法多，在一定的一个个的排方，问题。本章重点本章重点介介绍以以的的基本基本计数方法计数方法 加加法法则法法则和乘和乘法法则法法则 排排列列 组合组合 二项式定理的应二项式定理的应用用 组合恒等式组合恒等式 相相互互独独立立的的事事 A A、B B 分分有有 k k 和和 l l 方方法法产生生，则则产生生 A A B B 的的方方法数法数为 k k+l l 。1.1 加法法则1.1.11.1.1加法法则加法法则若若|A A|=k k，|B B|=l l，且且A AB B=，则则|A AB B|=k k+l l。S S有限集合，若有限集合，若，且且时，时，则有，则有

6、1.1 加法法则例11.1.11.1.1加法法则加法法则例例1 1、有有一一学学校校一一名名物物理理竞赛胜发发奖，奖品品有有三三类类，第第一一类类三三不不同同版版本本的的法法汉词典典第第二二类类四四不不同同类类型型的的物物理理参参考考书第第三三类类二二不不同同的的奖杯杯。胜只只挑挑选一一样样奖品品。那那么么，胜挑挑选奖品品的方法有多？的方法有多？解解S S有有些些奖品品的的集集合合，S Si i第第i i类类奖品品的的集集合合(i i=1,2,=1,2,3 3)，S Si iS Sj j=(i ij j)，根根据据加加法法法则法则有有1.1 加法法则例2、31.1.11.1.1加法法则加法法

7、则例例2 2、大大0 0小小1010的的奇奇偶偶数数有多个？有多个？例例3 3、小小2020被被2 23 3整整除除的的自自数有多个？数有多个？解解S S合合数数的的集集合合，S S1 1、S S2 2分分合合的的奇奇数数、偶、偶数集合，数集合，S S1 1S S2 2=，根根据据加加法法法则法则有有若若|A A|=k k，|B B|=l l，A AB B=(a a,b b)|a aA A，b bB B，则，则|A AB B|=k kl l。1.1 乘法法则1.1.21.1.2乘法法则乘法法则 相相互互独独立立的的事事 A A、B B 分分有有 k k 和和 l l 方方法法产生生，则则选取取

8、A A以以后后再再选取取B B 的方法数的方法数为 k kl l 。有限集合，有限集合，且且，则有，则有。1.1 乘法法则例41.1.21.1.2乘法法则乘法法则例例4 4、从从A A 地地到到B B地地有有二二不不同同的的道道路路，从从B B地地到到C C地地有有四四不不同同的的道道路路，而而从从C C地地到到D D地地有有三三不不同同的的道道路路。从从A A地地经经B B、C C两地两地到达到达D D地地的的道道路路数。数。解解S S的的道道路路数数集集合合，S S1 1、S S2 2、S S3 3分分从从A A到到B B、从从B B到到C C、从从C C到到D D的的道道路路集合，集合，

9、根根据据乘乘法法法则法则有有1.1 乘法法则例51.1.21.1.2乘法法则乘法法则例例5 5、数数字字1,2,1,2,3 3,4,5,4,5以以多多个个有数有数字互字互不不相相同的同的四四偶偶数？数？解解的的四四偶偶数数，个个只只选2 24 4，有有两两选择方方法法四四数数字字互互不不相相同同，个个选中中后后，十十只只有有四四选择方方法法同同理理，百百、千千分分有有三三、两两选择方方法法，根根据据乘乘法法法法则则，四四数数互互不不相相同同的的偶偶数数个数个数为2 2 4 4 3 3 2=482=481.1 乘法法则例61.1.21.1.2乘法法则乘法法则例例6 6、从从8 8个个计计算算机机

10、系系的的学学生生、9 9个个数数学学系系的的学学生生和和1010个个经经济系系的的学学生生中中选两两个不同个不同专业的学的学生生的方法数。的方法数。解解乘乘法法法则法则有有选一个计算一个计算机机系和系和一个数学一个数学系系的方法数的方法数为8 89=729=72选一个数学一个数学系和系和一个经一个经济系系的方法数的方法数为9 91010=90=90选一个经一个经济系和系和一个计算一个计算机机系系的方法数的方法数为10108=808=80加加法法法则法则，合的方法数，合的方法数为72+90+80=24272+90+80=2421.1 重集的概念1.1.1.1.3 3 计数问题的分类计数问题的分类

11、 有有序序排有排有序序选择允允许重复重复/不不允允许重复重复 无无序序排排无无序序选择允允许重复重复/不不允允许重复重复 标标准准集的特性集的特性确确定定、无、无序序、相异相异等。等。重重集集B B=k k1 1*b*b1 1,k,k2 2*b*b2 2,k kn n*b*bn n，其，其中中b bi i为n n个个互互不不相相同的同的元素元素，称称 k ki i为b bi i的的重重数数，i i=1,2,=1,2,n n，n n=1,2,=1,2,，k ki i=1,2,=1,2,。1.2 线排列1.2.11.2.1线排列线排列从从n n个不同个不同元素元素中中，取取r r个个(0(0r r

12、n n)一定一定顺序序排排列列起起，其排，其排列列数数P P(n n,r r)。A A=a an n ，从从A A中中选择r r个个(0(0r rn n)元素元素排排列列起起，A A的的r r 有有序序子子集，集，A A的的r r 排排列列。n n,r rZ且且n nr r0,0,P P(n n,r r)=)=n n!/(!/(n-rn-r)!)!。n n=r r，称全称全排排列列P P(n n,n n)=)=n n!n nr r,P P(n n,r r)=0)=0r r=0,=0,P P(n n,r r)=1)=1。证证明明集集合合A A的的r r 排排列列时时，以以从从A A的的n n各各

13、元元素素中中任任选一一个个作作为排排列列的的第第一一项项，有有n n选法法第第一一项项选定定后后从从剩剩的的n n-1 1个个元元素素中中选排排列列的的第第二二项项有有n n-1 1选法法此此类类推推，第第r r项有项有n n-r r+1+1选法。法。根根据据乘乘法法法则法则有有1.2 线排列推论11.2.11.2.1线排列线排列推论推论1.1.11.1.1n n,r rN且且n nr r2 2，则则P P(n n,r r)=)=n nP P(n-n-1 1,r-r-1)1)。证证明明在在集集合合A A的的n n个个元元素素中中，任任一一个个元元素素都都以以排排在在的的r r 排排列列，有有n

14、 n取取法法取取定定后后，其其他他置置的的元元素素正正好好从从A A的的另另n n-1 1个个元元素素中中取取r r-1 1个个的的排排列列，因因此此有有P P(n n-1,1,r r-1)1)取取法。法。乘乘法法则有法法则有P P(n n,r r)=)=n nP P(n-n-1 1,r-r-1)1)证证毕。1.2 线排列推论21.2.11.2.1线排列线排列推论推论1.1.11.1.1n n,r rN且且n nr r2 2，则则P P(n n,r r)=)=n nP P(n-n-1 1,r-r-1)1)。推论推论1.1.21.1.2n n,r rN且且n nr r2 2，则则P P(n n,

15、r r)=)=r rP P(n-n-1 1,r-r-1)+1)+P P(n-n-1 1,r r)。证证明明r r2 2时时，集集合合A A的的r r 排排列列分分为两两大大类类一一类类包包含含A A中中的的个个固固定定元元素素，不不妨妨为a a1 1，另另一一类类不不包包含含a a1 1。第第一一类类排排列列相相先先从从A A-a a1 1 中中取取r r-1 1个个元元素素排排列列，有有P P(n n-1,1,r r-1)1)取取法法，再再将将a a1 1放放入入每每一一个个上上述述排排列列中中，对对任任一一排排列列，a a1 1都都有有r r放放法法。乘乘法法法法则则，第第一一类类排排列列

16、共共有有r rP P(n-n-1 1,r-r-1)1)个个。第第二二类类排排列列实质上上A A-a a1 1 的的r r 排排列列，共共有有P P(n-n-1 1,r r)个。个。再再加加法法则有法法则有P P(n n,r r)=)=r rP P(n-n-1 1,r-r-1)+1)+P P(n-n-1 1,r r)证证毕。1.2 线排列例11.2.11.2.1线排列线排列例例1 1、数数字字1,2,1,2,3 3,4,5,4,5以以多多个个有有数数字字互互不不相相同同的的四四数数？解解有有的的四四数数字字互互不不相相同同，每每一一个个四四数数集集合合 1,2,1,2,3 3,4,5,4,5 的

17、的一一个个4 4 排排列列，因因而而的的四四数数个个数数为1.2 线排列例21.2.11.2.1线排列线排列例例 2 2、将将 具具 有有 9 9个个 字字 母母 的的 单单 词FRAGFRAGMENTS S排排列列，字字母母A A紧跟跟在在字字母母R R的的右右边，问问有有多多样样的的排排法法？再再字字母母M和和N必必须相邻相邻呢呢？解解A AR R的的右右边，样样的的排排列列相相8 8个个元元素素的集合的集合FF,RARA,G G,M,E,N,T,SS的一个的一个全全排排列列，个数，个数为再再M和和N必必须相相邻邻，先先M和和N看看一一个个整整体体=M,N，7 7个个元元素素的的集集合合F

18、F,RARA,G G,E,T,S S,的的全全排排列列，在在每每一一个个排排列列中中再再 M,N 的的全全排排列列，乘乘法法法法则，排则，排列列个数个数为1.2 线排列例31.2.11.2.1线排列线排列例例3 3、有有多多个个5 5数数，每每数数字字都都不不相相同同，不不取取0 0，且且数数字字7 7和和9 9不不相邻相邻？解解有有的的5 5数数字字互互不不相相同同，且且不不取取0 0，每每一一个个5 5数数集集合合 1,2,91,2,9 的的一一个个5 5-排排列列，其其排排列列数数为P P(9,5)(9,5)，其其中中7 7和和9 9相相邻邻的的排排列列数数为cc(7,(7,3 3)4!

19、2)4!2 4 42 2P P(7,(7,3 3)，题目的，题目的5 5数个数数个数为1.2 圆排列1.2.21.2.2圆排列圆排列A A=a an n ，从从A A中中取取r r个个(0(0r rn n)元元素素顺序序（逆逆时时针）排排一一个个圆圆圈圈，称称为圆圆排排列（循环列（循环排排列）列）。A A=a an n，A A的的r r圆圆排排列列个数个数为P P(n n,r r)/r r。证证明明一一个个圆圆排排列列旋旋转转得得到到另另一一个个圆圆排排列列视为相相同同的的圆圆排排列列，因因此此线线排排列列a a1 1a a2 2a ar r，a a2 2a a3 3a ar ra a1 1，

20、a ar ra a1 1a a2 2a ar r-1 1在在圆圆排排列列中中一一个个，即即一一个个圆圆排排列列产生生r r个个不不同同的的线线排排列列同同理理，r r个个不不同同的的线线排排列列对对应应一一个个圆圆排排列列。而而共共有有P P(n n,r r)个个线线排排列列，圆圆排排列列的个数的个数为P P(n n,r r)/)/r r=n n!/(!/(r r(n-rn-r)!)!)证证毕。1.2 圆排列例41.2.21.2.2圆排列圆排列例例4 4、有有8 8围围圆圆桌桌餐餐，问问有有多多座座方方式式？有有两两不不愿愿坐坐在在一一起起，有多有多座座方式？方式？解解上上述述定定理理知知8

21、8围围圆圆桌桌餐餐，有有8!/8=7!=50408!/8=7!=5040座座方式。方式。有有两两不不愿愿坐坐在在一一起起，不不妨妨此此二二为A A、B B，A A、B B坐坐在在一一起起时时，相相7 7围围圆圆桌桌餐餐，有有7!/7=6!7!/7=6!座座方方式式。而而A A、B B坐坐在在一一起起时时，有有两两情情况况，A A在在B B的的左左面面，A A在在B B的的右右面面，因因此此A A、B B坐坐在在一一起起时时，共共有有2 26!6!座座方方式式，因因此此有有两两不不愿愿坐坐在在一一起起，座座方式方式为7!7!-2 26!=6!=5 56!=6!=3 36006001.2 圆排列例

22、51.2.21.2.2圆排列圆排列例例5 5、4 4男男4 4女女围围圆圆桌桌交交替替座座有有多多座座方式？方式？解解，一一个个圆圆排排列列问问题题。先先让4 4个个男男的的围围圆圆桌桌座座，有有4!/4=4!/4=3 3!座座方方式式。因因为男男女女围围圆圆桌桌交交替替座座，在在男男的的坐坐定定后后，两两两两之之间间均均留留有有一一个个空空，女女的的座座相相一一个个4 4元元素素集集合合的的全全排排列列，座座方方式式数数为4!4!。乘乘法法则法法则知知，座座方式数方式数为3 3!4!=1444!=1441.2 重排列1.2.1.2.3 3 重排列重排列从从n n个不同个不同元素元素中中，重复

23、重复选取取r r个个一定一定顺序序排排列列起起，称称为重重排排列列。从从重重集集B B=k k1 1*b*b1 1,k,k2 2*b*b2 2,k,kn n*b*bn n 中中选取取r r个一定个一定顺序序排排列列起起。重重集集B B=*b b1 1,*b b2 2,*b bn n 的的r r 排排列列的个数的个数为n nr r。证证明明B B的的r r 排排列列选择第第一一项项时时从从n n个个元元素素中中任任选一一个个，有有n n选法法，选择第第二二项项时时以以重重复复选取取，仍仍有有n n选法法，同同理理，选择第第r r项项时时仍仍有有n n选法，法，根根据据乘乘法法则，法法则，得得r

24、r 排排列列的个数的个数为n nr r。证证毕。1.2 重排列例61.2.1.2.3 3 重排列重排列例例6 6、数数字字1,2,1,2,3 3,4,5,6,4,5,6六六个个数数字字组组多多个个五五数数？组组多多大大3 345004500的五数？的五数？解解一一个个五五数数的的各各数数字字重重复复现，一一个个典典型型的的重重排排列列问问题题，相相重重集集B B=*1,1,*2,2,*6 6 的的55排排列列，的五数个数，的五数个数为6 65 5=7776=7776。大大3 345004500的五数的五数面面三三情况情况组组万万选4,5,64,5,6中中的的一一个个，其其余余4 4相相重重集集

25、B B的的44排排列列，乘乘法法则法法则知知，共共有有3 3 6 64 4个五数个五数万万3 3，千千5,65,6中中的的一一个个，其其余余3 3相相重重集集B B的的3 3 排排列列，乘乘法法则法法则知知，共共有有2 2 6 63 3个五数个五数万万3 3，千千4 4中中的的一一个个，百百选5,65,6中中的的一一个个，其其余余2 2相相重重集集B B的的22排排列列，乘乘法法法法则则知知，共共有有2 2 6 62 2个五数个五数加加法法则法法则知知，大大3 345004500的五数个数的五数个数为3 36 64 4+2 26 63 3+2 26 62 2=4=43 392921.2 重排列

26、计数1.2.1.2.3 3 重排列重排列重重集集B B=n n1 1*b*b1 1,n n2 2*b*b2 2,n nk k*b*bk k 的的全全排排列列个数个数为证证明明将将B B中中的的n ni i个个b bi i看看作作不不同同的的n ni i个个元元素素，赋予予上上标标1,2,1,2,n ni i，即即 ，此此，重重集集B B变具具有有n n1 1+n n2 2+n nk k=n n个不同的个不同的元素元素集合集合，集合，集合A A的的全全排排列列个数个数为n n!。n ni i个个b bi i赋予予上上标标的的方方法法有有n ni i!，对对重重集集B B的的任任一一个个全全排排列

27、列，都都以以产生生集集合合A A的的n n1 1!n n2 2!n nk k!个个排排列列（乘乘法法则法法则），重重集集B B的的全全排排列列个数个数为证证毕。注注利利用用组合数的计数方法同样组合数的计数方法同样以得以得证明。证明。1.2 重排列例71.2.1.2.3 3 重排列重排列例例6 6、有有四四面面红旗旗，三三面面蓝旗旗，二二面面黄黄旗旗，五五面面绿旗旗以以组组多多1414面旗面旗子子组的一排组的一排彩旗彩旗？解解一个一个重重排排列列问题，问题，重重集集 4 4*红旗旗,3*3*蓝旗旗,2,2*黄黄旗旗,5,5*绿旗旗 的的全全排排列列个数，个数，根根据据定理，一排定理，一排彩旗彩旗

28、的数的数为1.2 重排列例81.2.1.2.3 3 重排列重排列例例8 8、用用字字母母A A、B B、C C组组五五个个字字母母的的号号，在在每每个个号号里里，A A至至多多现2 2次次，B B至至多多现1 1次次，C C至至多多现3 3次次，此此类类号号的个数。的个数。解解一个一个重重排排列列问题。问题。根根据据分分析析，合题意的，合题意的号号个数个数相相重重集集M=2 2*A*A,1,1*B*B,3*3*C C 的的5 5 排排列列个数，分个数，分为三三情况情况分分M-A-A、M-B-B和和M-C C 的的全全排排列列个数。个数。根根据据加加法法则，法法则，此此类类号号个数个数为1.2

29、项链排列1.2.41.2.4项链排列项链排列对对圆圆排排列列，通通过转转动、平移平移、翻翻转、转、重重合的，合的，即即看作看作项项链链排排列列。n n个不同个不同元素元素的的r r 项项链链排排列列个数个数为P P(n n,r r)/(2)/(2r r)，具体参具体参P P lyalya定理定理。1.3 无重组合1.1.3 3.1.1（无重）组合（无重）组合A A=a an n，从从A A中中选择r r个个(0(0r rn n)元素元素组组合合起起，A A的的r r 无无序序子子集，集，A A的的r r 组合。组合。r rn n，有，有C C(n n,r r)=)=P P(n n,r r)/)

30、/r r!=!=n n!/(!/(r r!(!(n-rn-r)!)!)。n nr r=0=0，C C(n n,r r)=1)=1n nr r，C C(n n,r r)=0)=0。从从n n个不同个不同元素元素中中，取取r r个个(0(0r rn n)不不考考虑顺序序组合组合起起，其组合数，其组合数C C(n n,r r)。证证明明从从n n个个不不同同元元素素中中取取r r个个元元素素的的组组合合数数为C C(n n,r r)，而而r r个个元元素素组组r r!个个r r 排排列列，即即一一个个r r 组组合合对对应应r r!个个r r 排排列列。C C(n n,r r)个个r r 组组合合对

31、对应应r r!C C(n n,r r)个个r r 排排列列，从从n n个个不不同同元元素素中中取取r r个个元元素素的的r r 排排列列数数P P(n n,r r)，因因此此有有1.3 无重组合推论11.1.3 3.1.1（无重）组合（无重）组合推论推论1.5.11.5.1C C(n n,r r)=)=C C(n n,n-rn-r)证证明明实际上上，从从n n个个不不同同元元素素中中选r r个个元元素素的的同同时时，有有n-rn-r个个元元素素没没有有被被选，因因此此选r r个个元元素素的的方方式式数数等等选n-rn-r个个元元素素的的方方式式数数，即即C C(n n,r r)=)=C C(n

32、 n,n-rn-r)。得得证。证。另外另外，通通过计算计算得得证明证明1.3 无重组合推论21.1.3 3.1.1（无重）组合（无重）组合推论推论1.5.11.5.1C C(n n,r r)=)=C C(n n,n-rn-r)推论推论1.5.2(1.5.2(PascalPascal公公式式)C C(n n,r r)=C C(n-n-1 1,r r)+)+C C(n-n-1 1,r-r-1)1)证证明明利利用用组组合合分分析析法法。在在集集合合A A的的n n个个不不同同元元素素中中固固定定一一个个元元素素，不不妨妨为a a1 1，从从n n个个元元素素中中选r r个个元元素素的的组组合合面面两

33、两情况情况组组 r r个个元元素素中中包包含含a a1 1。相相从从除除去去a a1 1的的n-n-1 1个个元元素素中中选r-r-1 1个个元元素素的的组组合合，再再加加上上a a1 1而而得得到到，组组合合数数为C C(n-n-1 1,r-r-1)1)r r个个元元素素中中不不包包含含a a1 1。相相从从除除去去a a1 1的的n-n-1 1个个元元素素中中选r r个个元素元素的组合的组合而得到而得到，组合数，组合数为C C(n-n-1 1,r r)。加加法法则法法则即得即得C C(n n,r r)=)=C C(n-n-1 1,r r)+)+C C(n-n-1 1,r-r-1)1)另外另

34、外，通通过计算计算得得证明证明1.3 无重组合推论31.1.3 3.1.1（无重）组合（无重）组合推论推论1.5.11.5.1C C(n n,r r)=)=C C(n n,n-rn-r)推论推论1.5.2(1.5.2(PascalPascal公公式式)C C(n n,r r)=)=C C(n-n-1 1,r r)+)+C C(n-n-1 1,r-r-1)1)推论推论1.5.1.5.3 3C C(n n,r r)=)=C C(n-n-1 1,r-r-1)+1)+C C(n-n-2 2,r-r-1)+1)+C C(r-r-1 1,r-r-1)1)证明证明反反复复利利用用PascalPascal公公

35、式，式，即即证明。证明。利利用用组合分组合分析析法，在集合法，在集合A A=a an n 的的n n个不同个不同元素元素选r r个个元素元素的的组合分组合分为以以多多情况情况 r r个个元素元素中中包包含含a a1 1，相相从除去从除去a a1 1的的n-n-1 1个个元素元素中中选r-r-1 1个个元素元素的组合，的组合，再再加加上上a a1 1而得到而得到，组合，组合数数为C C(n-n-1 1,r-r-1)1)r r个个元素元素中中不不包包含含a a1 1但包但包含含a a2 2，相相从除去从除去a a1 1,a a2 2的的n-n-2 2个个元素元素中中选r-r-1 1个个元素元素的组

36、合，的组合，再再加加上上a a2 2而得到而得到，组，组合数合数为C C(n-n-2 2,r-r-1),1),同理同理r r个个元素元素中中不不包包含含a a1 1,a a2 2,a an n-r r，但包但包含含a an n-r r+1+1，相相从剩从剩的的r-r-1 1个个元素元素中中选r-r-1 1个个元素元素的组合，的组合，再再加加上上a an n-r r+1+1而得到而得到，组合数，组合数为C C(r-r-1 1,r-r-1)1)。加加法法则法法则得得C C(n n,r r)=)=C C(n-n-1 1,r-r-1)+1)+C C(n-n-2 2,r-r-1)+1)+C C(r-r-

37、1 1,r-r-1)1)1.3 无重组合例11.1.3 3.1.1（无重）组合（无重）组合例例1 1、有有5 5本本日日文文书，7 7本本英英文文书，1010本本中中文文书，从从中中取取两两本本不不同同文文字字的的书，问问有有多多方方？若若取取两两本本相相同同文文字字的的书，问问有有多多方方？任任取取两两本本书，有多方？有多方？解解从从三三文文字字的的书中中取取两两共共有有C C(3 3,2)=,2)=3 3取取法法。根根据据乘乘法法法法则则有有日日英英各各一一本本的的方方法法数数为5 57=7=3 35 5，中中英英各各一一本本的的方方法法数数为10107=707=70，中中日各日各一一本本

38、的方法数的方法数为10105=50=50，加加法法则法法则得得3 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任取任取两本两本书，相相从从5+7+10=225+7+10=22本本书中中取取两本两本的组合，的组合，即即C C(22,2)=2(22,2)=23 31 11.3 无重组合例21.1.3 3.1.1（无重）组合（无重）组合例例2 2、从从1 13 30000

39、之之间间任任取取3 3个个不不同同的的数数，使使得得3 3个个数数的的和和正正好好被被3 3除除尽尽，问问共共有方？有方？解解有有的的整整数数分分为以以3 3个个分分类类模模3 3余余0 0、模模3 3余余1 1和和模模3 3余余2 2，1 13 30000的的 3 30000个个 数数 以以 分分 为 3 3个个 集集 合合 A A=1,4,2981,4,298，B B=2,5,2992,5,299，C C=33,6,6,3 30000。任任取取3 3个个数数其其和和正正好好被被3 3整整除除的的情况情况三个数同集合三个数同集合A A，有，有C C(100,(100,3 3)方方三个数同集合

40、三个数同集合B B，有，有C C(100,(100,3 3)方方三个数同集合三个数同集合C C，有，有C C(100,(100,3 3)方方三个数分集合三个数分集合A A,B B,C,C，乘乘法法则有法法则有1001003 3方。方。加加法法则法法则得得，的方数，的方数为3 3C C(100,(100,3 3)+100)+1003 3=1485100=14851001.3 无重组合例31.1.3 3.1.1（无重）组合（无重）组合例例3 3、车站站有有1 1到到6 6个个入入口口处处，每每个个入入口口处处每每次次只只一一个个，问问一一小小组组9 9个个站站的方数有多？的方数有多？解解I从从入入

41、口口1 1到到入入口口6 6的的顺序序得得到到9 9个个一一个个排排列列，再再两两个个入入口口间间上上一一个个标标志志，加加上上5 5个个标标志志相相每每一一个个排排列列有有1414个个元元素素，其其中中5 5个个标标志志没没有有区区，但但其其置置将将区区分分各各入入口口的的站站数，数，相相1414个个元素元素集合的集合的5 5 组合，组合，故故进站站方方案案数数为9!9!C C(14,5)=726485760(14,5)=726485760解解II同同上上分分析析，问问题题转转为重重集集 1 1*p p1 1,1,1*p p2 2,1,1*p p9 9,5,5*标标志志 的的全全排排列（列（

42、p pi i代代表表9 9个，个，i i=1,9=1,9），站站方数方数为14!/5!=72648576014!/5!=726485760解解III考考虑9 9个个选择方方，第第1 1个个有有6 6选择，第第2 2个个除除了了选择入入口口，还考考虑在在第第1 1个个的的前前面面后后面面，有有7 7选择同同理，理，第第9 9个有个有1414选择，根根据据乘乘法法则，法法则，站站方数方数为6 6 7 7 1414=726485760=7264857601.3 无重组合例41.1.3 3.1.1（无重）组合（无重）组合例例4 4、5 5数数中中至至现一一个个6 6，而而被被3 3整整除除的数的个数。

43、的数的个数。解解1010制制数数被被3 3整整除除的的充充各各数数的的和和被被3 3整整除除。据据此此讨论论从从左左右右计计，后后一一个个6 6现在在个个，则则十十百百千千各各有有1010选择，万万有有3 3，根根据据乘乘法法则，个数法法则，个数为3 310103 3 后后一一个个6 6现在在十十，则则个个有有9 9选择，百百千千各各有有1010选择，万万有有3 3，根根据据乘乘法法则，个数法法则，个数为3 310102 29 9 后后一一个个6 6现在在百百，则则个个十十各各有有9 9选择，千千有有1010选择，万万有有3 3，根根据据乘乘法法则，个数法法则，个数为3 310109 92 2

44、后后一一个个6 6现在在千千，则则个个十十百百各各有有9 9选择，万万有有3 3，根根据据乘乘法法则，个数法法则，个数为3 39 93 3后后一一个个6 6现在在万万，则则个个十十百百各各有有9 9选择，千千有有3 3，根根据据乘乘法法则，个数法法则，个数为3 39 93 3 根根据据加加法法则，法法则，符符合合条件条件的整数个数的整数个数为3 310103 3+3 310102 29+9+3 310109 92 2+3 39 93 3+3 39 93 3=12504=125041.3 无重组合例51.1.3 3.1.1（无重）组合（无重）组合例例5 5、1000!1000!的的末尾末尾有个有

45、个零零。解解此此问问题题在在将将1000!1000!分分解解为素素数数的的乘乘积时时，2 2和和5 5的的幂多多。末末尾尾零零的的个个数数应应该等等2 2和和5 5的的幂中中较小小的的那那个个数。数。1 110001000中中5 5的的倍倍数数的的数数共共200200个个，其其中中有有4040个个5 52 2的的倍倍数数，4040个个数数中中有有8 8个个5 53 3的的倍倍数数，而而8 8个个数数中中有有1 1个个5 54 4的的倍倍数数，1000!1000!分解分解为素素数的数的乘乘积时，时，5 5的的幂应应该200+40+8+1=249200+40+8+1=249，2 2的的幂必必大大2

46、49249，因因此此1000!1000!的的末尾末尾有有249249个个零零。1.3 无重组合例61.1.3 3.1.1（无重）组合（无重）组合例例6 6、除除尽尽14001400的的正正整整数数数数目目（1 1除外除外），其，其中中包包含含多个多个奇奇数？数？解解1400=21400=23 35 52 27 7，除除尽尽14001400的的正正整整数数分分解解为素素数数的的乘乘积的的形形式式应应该为2 2l l5 5m m7 7n n，其其中中0 0l l3 3,0,0m m2,02,0n n1 1，但但应应排排除除l l=m m=n n=0=0的的情况情况。的数目。的数目为(3 3+1)+

47、1)(2+1)(2+1)(1+1)(1+1)-1=21=23 3其其中中包包含含的的奇奇数数为(1)(1)(2+1)(2+1)(1+1)(1+1)-1=51=51.3 重复组合1.1.3 3.2.2重复组合重复组合从从n n个不同个不同元素元素中中，重复重复选取取r r个不个不考考虑顺序序组合组合起起，其组合数，其组合数F F(n n,r r)。从从重重集集B B=k k1 1*b*b1 1,k,k2 2*b*b2 2,k,kn n*b*bn n 中中取取r r个个元素元素不不考考虑顺序序的组合。的组合。重重集集B B=*b b1 1,*b b2 2,*b bn n 的的r r 组组合数合数F

48、 F(n n,r r)=)=C C(n n+r r-1,1,r r)证证明明n n个个元元素素b b1 1,b b2 2,b bn n和和自自数数1,2,1,2,n n一一一一对对应应。任任组组合合皆皆看看作作一一个个r r个个数数的的组组合合 c c1 1,c c2 2,c cr r。组组合合，不不妨妨认为各各c ci i大大小小顺序序排排列列的的，相相同同的的c ci i连续排在一排在一起起，不，不妨妨c c1 1c c2 2c cr r 。d di i=c ci i+i i-1(1(i i=1,2,=1,2,r r)，即即d d1 1=c c1 1,d d2 2=c c2 2+1,+1,

49、d dr r=c cr r+r r-1 1。因因1 1c ci in n，1 1d di in n+r r-1 1，得得到到一一个个集集合合 1,2,1,2,n n+r r-1 1 的的r r 组合组合 d d1 1,d d2 2,d dr r (d d1 1d d2 2d dr r)。有有一一 c c1 1,c c2 2,c cr r 的的取取法法，有有一一 d d1 1,d d2 2,d dr r 的的取取法法，反反之之亦亦，两两取取法法一一一一对对应应的的，从从而而两两取取法法等等价价的的。此此，从从n n个个不不同同元元素素中中重重复复选取取r r个个的的组组合合数数，和和从从n n+

50、r r-1 1个个不不同同元元素素中中不不重重复复选取取r r个个的的组组合合数数相相同的，同的，F F(n n,r r)=)=C C(n n+r r-1,1,r r)1.3 重复组合例71.1.3 3.2.2重复组合重复组合r r个个无区无区的的球放入球放入n n个有个有标标志志的的盒盒子子里里，每盒每盒的的球球数多数多1 1个，则个，则共共有有F F(n n,r r)方。方。例例7 7、试问问(x x+y y+z)4 4的的展展开开式式有有多多项？项？证证明明一一个个允允许重重复复组组合合的的典典型型问问题题，实质上上定定理理1.61.6的的另另一一法法。每每盒盒的的球球数数不不受受限限制