组合数学课件

1、课程简介课程简介相关课程相关课程使用教材使用教材数学分数学分析析高高等等代代数数离散离散数学数学书名书名：组合数学：组合数学（第（第三三版）版）作作者：者：孙淑玲孙淑玲 出出版社版社：中国科中国科学学技术大技术大学出学出版社版社 本课程针本课程针对计算对计算机科机科学学中中的一个的一个重重要学要学科科组合数学，组合数学，组合数学是数学的一个分组合数学是数学的一个分支支，它，它研究事物研究事物在在结结定定模模式下的式下的配配置置，研究研究这种这种配置配置的存在性，所有可能的存在性，所有可能配置配置的计数的计数和和分类分类以以及配置及配置的的各各种性种性质质。组合数学在计算。组合数学在计算机科机科

2、学学中中有有着极着极其其广泛广泛的应的应用用。 组合学问题求解方法组合学问题求解方法层层出不出不穷、干变万穷、干变万化，应化，应以以理解理解为为基础基础，善善于总于总结各结各种种技巧技巧，掌握科掌握科学的组学的组织和推织和推理方法。理方法。目录（目录（1）引言引言第第1章章 排排列与列与组合组合 1.1 加法法则和乘法法则 1.2 排列 1.3 组合 1.4 二项式定理 1.5 组合恒等式及其含义 1.6 模型转换 本章小结 习题第第2章章 鸽笼原鸽笼原理理 2.1 鸽笼原理 2.2 鸽笼原理的推广 2.3 Ramsey定理 本章小结 习题第第3章章 容斥原容斥原理理 3.1 容斥原理 3.2

3、 重集r-组合 3.3 错排问题 3.4 有限制排列 3.5* 一般有限制排列 3.6* 广义容斥原理 本章小结 习题第第4章章 母函母函数数 4.1 母函数的基本概念 4.2 母函数的基本运算 4.3 在排列组合中的应用 4.4 整数的拆分 4.5 Ferrers图目目 录录目录（目录（2） 4.6* 在组合恒等式中的应用 本章小结 习题第第5章章 递推关系递推关系 5.1 递推关系的建立 5.2 常系数线性齐次递推关系 5.3 常系数线性非齐次递推关系 5.4 迭代法与归纳法 5.5 母函数在递推关系中的应用 5.6* 典型的递推关系 本章小结 习题第第6章章 Plya定理定理 6.1 群

4、的概念 6.2 置换群 6.3 循环、奇循环与偶循环 6.4 Burnside引理 6.5 Plya定理 6.6 Plya定理的应用 6.7 母函数形式的Plya定理 6.8* 图的计数 6.9* Plya定理的若干推广 本章小结 习题*课程课程总总结结注：加*的章节一般性了解引引 言言发展历史发展历史涵盖内容涵盖内容学习目的学习目的学习方法学习方法 存在性问题存在性问题 计数计数和枚举和枚举 优化优化问题问题 构造性问题构造性问题 科科学的组学的组织织 科科学的学的推推理理 古老古老 年轻年轻 练习练习 思考思考总总结结 笔记笔记组合数学研究的中心问题是按照一定的规组合数学研究的中心问题是按

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

6、基本计数方法：计数方法： 加加法法则法法则和乘和乘法法则法法则 排排列列 组合组合 二项式定理的应二项式定理的应用用 组合恒等式组合恒等式 相互独相互独立立的的事事件件 A、B 分别有分别有 k 和和 l 种方法种方法产生产生，则，则产生产生 A 或或 B 的方的方法数法数为为 k+l 种。种。1.1 加法法则1.1 加法法则和乘法法则加法法则和乘法法则1.1.1 加法法则加法法则加法法则加法法则集合论定义集合论定义 若若|A|=k，|B|=l ，且且AB= ，则则|AB| = k+l 。 设设S是有限集合，若是有限集合，若 ，且且时，时， ，则有，则有 。ij ijSS 1,miiiSSSS

7、 11mmiiiiSSS 1.1 加法法则例11.1 加法法则和乘法法则加法法则和乘法法则1.1.1 加法法则加法法则例例 题题例例1、有一所学有一所学校校给一给一名物名物理理竞赛竞赛优优胜胜者者发奖发奖，奖品奖品有三类，有三类，第第一类是三种一类是三种不同不同版本版本的法的法汉词典汉词典；第第二类是二类是四四种种不同类不同类型型的的物物理理参考书参考书；第第三类是二三类是二种不同的种不同的奖杯奖杯。这位优。这位优胜胜者者只只能能挑选挑选一样一样奖品奖品。那么那么，这位优，这位优胜胜者者挑选奖挑选奖品品的方法有多少种？的方法有多少种？解：解：设设S是所有这是所有这些奖品些奖品的集合，的集合，S

8、i是是第第i类类奖品奖品的集合的集合(i=1,2,3)，显然，显然，SiSj= (ij) ，根据加根据加法法法则法则有有iiSSSSS31231| | | |3429 1.1 加法法则例2、31.1 加法法则和乘法法则加法法则和乘法法则1.1.1 加法法则加法法则例例 题题例例2、大大于于0小小于于10的的奇偶奇偶数数有多少个？有多少个？例例3、小小于于20可可被被2或或3整除整除的的自自然然数有多少个？数有多少个？解：解：设设S是符合条件数的集合，是符合条件数的集合，S1、S2分别是符合条件的分别是符合条件的奇奇数数、偶、偶数集合，显然，数集合，显然，S1S2= ，根据加根据加法法法则法则有

9、有SSS12| | |549 若若|A|=k，|B|=l ，A B=(a,b)|aA，bB，则，则|A B| = k l 。1.1 乘法法则1.1 加法法则和乘法法则加法法则和乘法法则1.1.2 乘法法则乘法法则乘法法则乘法法则 相互独相互独立立的的事事件件 A、B 分别有分别有 k 和和 l 种方法种方法产生产生，则，则选取选取A以后以后再选取再选取B 的方法数的方法数为为 kl 种。种。集合论定义集合论定义 设设 是有限集合，是有限集合，且且 ，则有，则有 。11mmiiiiSSS1miiSS (1,2,.,)iS im 12(,.,)|,1,2,.,miia aaaS im1.1 乘法法

10、则例41.1 加法法则和乘法法则加法法则和乘法法则1.1.2 乘法法则乘法法则例例 题题例例4、从从A 地到地到B地地有二条不同的有二条不同的道道路路，从从B地到地到C地地有有四四条不同的条不同的道路道路，而从而从C地到地到D地地有三条不同的有三条不同的道路道路。求求从从A地地经经B、C两地到达两地到达D地地的的道路道路数。数。解：解：设设S是所求的是所求的道路道路数集合，数集合，S1、S2、S3分别是分别是从从A到到B、从、从B到到C、从、从C到到D的的道路道路集合，集合，根据乘根据乘法法法则法则有有SSSS123| | | |2 4 324 1.1 乘法法则例51.1 加法法则和乘法法则加

11、法法则和乘法法则1.1.2 乘法法则乘法法则例例 题题例例5、由数由数字字1,2,3,4,5可可以以构成多少个构成多少个所有数所有数字互字互不不相相同的同的四四位位偶偶数？数？解：解：所求的是所求的是四四位位偶偶数，故个位数，故个位只只能能选选2或或4，有，有两两种种选选择择方法；又由于要求方法；又由于要求四四位数位数字互字互不不相相同，故个位同，故个位选中后选中后，十十位位只只有有四四种种选择选择方法；同理，方法；同理，百百位位、千、千位分别有三种位分别有三种、两两种种选择选择方法，方法，根据乘根据乘法法法则，法则，四四位数位数互互不不相相同的同的偶偶数数个数个数为为2 4 3 2=481.

12、1 乘法法则例61.1 加法法则和乘法法则加法法则和乘法法则1.1.2 乘法法则乘法法则例例 题题例例6、求出求出从从8个计算个计算机系机系的学的学生、生、 9个数学个数学系系的学的学生和生和10个经个经济系济系的学的学生生中选中选出出两两个不同个不同专业专业的学的学生生的方法数。的方法数。解：解：由由乘乘法法法则法则有有选选一个计算一个计算机系和机系和一个数学一个数学系系的方法数的方法数为为89=72选选一个数学一个数学系和系和一个经一个经济系济系的方法数的方法数为为910=90选选一个经一个经济系和济系和一个计算一个计算机系机系的方法数的方法数为为108=80由由加加法法法则法则，符合要求

13、的方法数，符合要求的方法数为为72+90+80=2421.1 重集的概念1.1 加法法则和乘法法则加法法则和乘法法则1.1.3 计数问题的分类计数问题的分类 有有序序安排或有安排或有序选择序选择 允许重复允许重复/不不允许重复允许重复 无序无序安排或安排或无序选择无序选择 允许重复允许重复/不不允许重复允许重复 标准标准集的特性：集的特性：确确定定、无序、无序、相异相异等。等。 重重集：集：B=k1*b1, k2*b2, kn*bn，其，其中中：bi为为n个个互互不不相相同的同的元素元素，称称 ki为为bi的的重重数数， i=1,2,n，n=1,2, ，ki=1,2, 。重集的概念重集的概念1

14、.2 线排列1.2 排列排列定义定义 1.11.2.1 线排列线排列集合论定义集合论定义定理定理 1.1从从n个不同个不同元素中元素中，取取r个个(0rn)按一按一定定顺序顺序排排列起列起来，其排来，其排列列数数P(n,r)。设设A=an ，从从A中选择中选择r个个(0rn)元素元素排排列起列起来，来，A的的r有有序子序子集，集，A的的r排排列列。如如n, rZ且且nr0, P(n,r)=n!/(n-r)!。如如n=r，称全称全排排列列P(n,n)= n!；如如nr, P(n,r)=0；如；如r=0, P(n,r)=1。证明：证明：构造集合构造集合A的的r排排列列时，可时，可以从以从A的的n各

15、元素中任各元素中任选选一个一个作为作为排排列列的的第第一项，有一项，有n种种选选法；法；第第一项一项选选定定后后从剩从剩下的下的n-1个个元素中选元素中选排排列列的的第第二项有二项有n-1种种选选法；法；由由此此类类推推，第第r项有项有n-r+1种种选选法。法。根据乘根据乘法法法则法则有有!( , )(1).(1)()!nP n rn nnrnr 1.2 线排列推论11.2 排列排列1.2.1 线排列线排列两个推论两个推论推论推论1.1.1：如如n, rN且且nr2，则，则P(n,r)=nP(n-1,r-1) 。证明：证明：在集合在集合A的的n个个元素中元素中，任任一个一个元素都元素都可可以以

16、排在排在它的它的r排排列列首位，故首位有首位，故首位有n种种取取法；首位法；首位取取定定后后，其，其他他位位置置的的元素正好元素正好是是从从A的的另另n-1个个元素中取元素中取r-1个的排个的排列列，因此因此有有P(n-1,r-1)种种取取法。由法。由乘乘法法则有法法则有P(n,r)=nP(n-1,r-1)证证毕毕。1.2 线排列推论21.2 排列排列1.2.1 线排列线排列两个推论两个推论推论推论1.1.1：如如n, rN且且nr2，则，则P(n,r)=nP(n-1,r-1) 。推论推论1.1.2：如如n, rN且且nr2，则，则P(n,r)= rP(n-1,r-1)+P(n-1,r) 。证

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

18、。再再由由加加法法则有法法则有P(n,r)= rP(n-1,r-1)+P(n-1,r)证证毕毕。1.2 线排列例11.2 排列排列1.2.1 线排列线排列例例 题题例例1、由数由数字字1,2,3,4,5可可以以构成多构成多少个所有数少个所有数字互字互不不相相同的同的四四位数？位数？解：解：由于所有的由于所有的四四位数位数字互字互不不相相同，故同，故每每一个一个四四位数就位数就是集合是集合1,2,3,4,5的一个的一个4排排列列，因而因而所求的所求的四四位数个位数个数数为为5!(5,4)120(54)!P 1.2 线排列例21.2 排列排列1.2.1 线排列线排列例例 题题例例 2 、 将 具将

19、 具 有有 9 个个 字 母字 母 的的 单 词单 词FRAGMENTS进行排进行排列列，要求，要求字母字母A总是总是紧跟紧跟在在字母字母R的的右边右边，问有，问有多少种这样的排法？如果多少种这样的排法？如果再再要求要求字字母母M和和N必须相邻呢必须相邻呢？解：解：由于由于A总是总是R的的右边右边，故这样的排，故这样的排列列相相当于当于是是8个个元元素素的集合的集合F,RA,G,M,E,N,T,S的一个的一个全全排排列列，个数，个数为为如果如果再再要求要求M和和N必须相邻必须相邻，可，可先先把把M和和N看看成一个成一个整整体体 =M,N，进行，进行7个个元素元素的集合的集合F,RA,G,E,T

20、,S, 的的全全排排列列，在，在每每一个排一个排列中再列中再进行进行 M,N的的全全排排列列，由，由乘乘法法法则，排法则，排列列个数个数为为(8,8)8!40320P(7,7)(2,2)7! 2!10080PP1.2 线排列例31.2 排列排列1.2.1 线排列线排列例例 题题例例3、有多少个有多少个5位数，位数，每每位数位数字都字都不不相相同，不能同，不能取取0，且且数数字字7和和9不能不能相邻相邻？解：解：由于所有的由于所有的5位数位数字互字互不不相相同，同，且且不能不能取取0，故，故每每一一个个5位数就是集合位数就是集合1,2,9的一个的一个5-排排列列，其排，其排列列数数为为P(9,5

21、)，其，其中中7和和9相邻相邻的排的排列列数数为为c(7,3)4!242P(7,3)，满足题目要求的满足题目要求的5位数个数位数个数为为(9,5)4 2(7,3)15120168013440PP 1.2 圆排列1.2 排列排列定义定义 1.21.2.2 圆排列圆排列定理定理 1.2设设A=an ，从从A中取中取r个个(0rn)元素元素按按某种某种顺序（顺序（如如逆逆时时针）针）排成一个排成一个圆圈圆圈，称为圆称为圆排排列（循环列（循环排排列）列）。设设A=an，A的的r圆圆排排列列个数个数为为P(n,r)/r。证明：证明：由于把一个由于把一个圆圆排排列旋转列旋转所所得到另得到另一个一个圆圆排排

22、列视为列视为相相同的同的圆圆排排列列，因此线因此线排排列列a1a2ar，a2a3ara1， ara1a2ar-1在在圆圆排排列中列中是一个，是一个，即即一个一个圆圆排排列列可可产生产生r个个不同的不同的线线排排列列；同理，；同理， r个不同的个不同的线线排排列列对应一个对应一个圆圆排排列列。而而总总共共有有P(n,r)个个线线排排列列，故，故圆圆排排列列的个数的个数为为 P(n,r)/r= n!/(r(n-r)!)证证毕毕。1.2 圆排列例41.2 排列排列例例 题题1.2.2 圆排列圆排列例例4、有有8人人围圆桌围圆桌就就餐餐，问有多少种，问有多少种就就座座方式？如果有方式？如果有两两人不人

23、不愿坐愿坐在一在一起起，又有多少种就又有多少种就座座方式？方式？解：解：由由上述上述定理定理知知8人人围圆桌围圆桌就就餐餐，有，有8!/8=7!=5040种就种就座座方式。方式。又有又有两两人不人不愿坐愿坐在一在一起起，不，不妨妨设设此此二人二人为为A、B，当，当A、B坐坐在一在一起起时，时，相相当于当于7人人围圆桌围圆桌就就餐餐，有，有7!/7=6!种就种就座座方式。方式。 而而A、B坐坐在一在一起起时，又有时，又有两两种种情况情况，或者，或者A在在B的的左面左面，或者，或者A在在B的的右面右面，因此因此A、B坐坐在一在一起起时，时，共共有有26!种就种就座座方式，方式，因此因此如果有如果有

24、两两人不人不愿坐愿坐在一在一起起，就就座座方式方式为为7!-26!= 56!=36001.2 圆排列例51.2 排列排列例例 题题1.2.2 圆排列圆排列例例5、4男男4女围圆桌交替女围圆桌交替就就座座有多有多少种就少种就座座方式？方式？解：解：显然，这是一个显然，这是一个圆圆排排列列问题。首问题。首先让先让4个个男男的的围圆围圆桌桌就就座座，有，有4!/4=3!种就种就座座方式。方式。 因为因为要求要求男女围圆桌男女围圆桌交替交替就就座座，在，在男男的的坐坐定定后后，两两之间均两两之间均需需留留有一个有一个空空位，位，女女的就的就座相座相当于一个当于一个4元素元素集合的集合的全全排排列列，就

25、，就座座方式数方式数为为4!。由。由乘乘法法则法法则知知，就，就座座方式数方式数为为3!4!=1441.2 重排列1.2 排列排列定义定义 1.31.2.3 重排列重排列集合论定义集合论定义定理定理 1.3从从n个不同个不同元素中元素中，可，可重复选取重复选取r个按个按一定一定顺序顺序排排列起列起来，来，称为重称为重排排列列。从重从重集集B=k1*b1, k2*b2, , kn*bn中选中选取取r个按一定个按一定顺序顺序排排列起列起来。来。重重集集B=*b1, *b2, , *bn 的的r排排列列的个数的个数为为nr。证明：证明：构造构造B的的r排排列列如下：如下：选择第选择第一项时可一项时可

26、从从n个个元素元素中任选中任选一个，有一个，有n种种选选法，法，选择第选择第二项时由于可二项时由于可以重复以重复选取选取，仍仍有有n种种选选法，法，同理，同理，选择第选择第r项时项时仍仍有有n种种选选法，法，根据乘根据乘法法则，可法法则，可得得出出r排排列列的个数的个数为为nr。证证毕毕。1.2 重排列例61.2 排列排列例例 题题1.2.3 重排列重排列例例6、由数由数字字1,2,3,4,5,6这这六六个数个数字字能能组成多少个五位数？又可组成多少组成多少个五位数？又可组成多少大大于于34500的五位数？的五位数？解：解：一个五位数的一个五位数的各各位数位数字字可可重复重复出出现现，是一个，

27、是一个典型典型的的重重排排列列问题，问题，相相当于当于重重集集B=*1,*2,*6的的5排排列列，所求的五位数个数，所求的五位数个数为为65=7776。 大大于于34500的五位数可由下的五位数可由下面面三种三种情况情况组成：组成： 万万位位选选4,5,6中中的一个，其的一个，其余余4位位相相当于当于重重集集B的的4排排列列，由由乘乘法法则法法则知知，共共有有3 64个五位数；个五位数；万万位是位是3，千千位位5,6中中的一个，其的一个，其余余3位位相相当于当于重重集集B的的3排排列列，由，由乘乘法法则法法则知知，共共有有2 63个五位数；个五位数；万万位是位是3，千千位位4中中的一个，的一个

28、，百百位位选选5,6中中的一个，其的一个，其余余2位位相相当于当于重重集集B的的2排排列列，由，由乘乘法法则法法则知知，共共有有2 62个五位数；个五位数； 由由加加法法则法法则知知，大大于于34500的五位数个数的五位数个数为为364 + 263 + 262=43921.2 重排列计数1.2 排列排列1.2.3 重排列重排列定理定理 1.4重重集集B=n1*b1,n2*b2,nk*bk的的全全排排列列个数个数为为112!,! .!kiiknnnnnn其其中证明：证明：将将B中中的的ni个个bi看作看作不同的不同的ni个个元素元素，赋予上标赋予上标1,2, ni，即即 ，如，如此此，重重集集B

29、就就变变成成具具有有n1+n2+nk=n个不同的个不同的元素元素集合集合显然，集合显然，集合A的的全全排排列列个数个数为为n!。又由于又由于ni个个bi赋予上标赋予上标的方法有的方法有ni!种，于是对种，于是对重重集集B的的任任一一个个全全排排列列，都都可可以产生以产生集合集合A的的n1!n2!nk!个排个排列（列（由由乘乘法法则法法则），故，故重重集集B的的全全排排列列个数个数为为证证毕毕。注：注：利用利用组合数的计数方法同样可组合数的计数方法同样可以得以得出证明。出证明。12,.,(1,2,., )iniiib bbik 12121212111222,.,.,.,.,knnnkkkAb b

30、bb bbb bb 112! .!kiiknnnnnn其其中1.2 重排列例71.2 排列排列1.2.3 重排列重排列例例 题题例例6、有有四面红旗四面红旗，三，三面蓝旗面蓝旗，二，二面面黄旗黄旗，五，五面绿旗面绿旗可可以以组成多少种由组成多少种由14面旗子面旗子组成的一排组成的一排彩旗彩旗？解：解：这是一个这是一个重重排排列列问题，是求问题，是求重重集集4*红旗红旗,3*蓝旗蓝旗,2*黄黄旗旗,5*绿旗绿旗的的全全排排列列个数，个数，根据根据定理，一排定理，一排彩旗彩旗的种数的种数为为14!25225204! 3! 2! 5! 1.2 重排列例81.2 排列排列1.2.3 重排列重排列例例

31、题题例例8、用字母用字母A、B、C组成五个组成五个字母字母的符的符号号，要求在，要求在每每个符个符号里号里，A至至多多出出现现2次次，B至至多出多出现现1次次，C至至多出多出现现3次次，求，求此此类符类符号号的个数。的个数。解：解：这也是一个这也是一个重重排排列列问题。问题。根据根据分分析析，符合题意的符，符合题意的符号号个数个数相相当于求当于求重重集集M=2*A,1*B,3*C的的5排排列列个数，可分个数，可分为为三种三种情况情况：需要分别求：需要分别求M-A、M-B和和M-C的的全全排排列列个数。个数。根据加根据加法法则，法法则，此此类符类符号号个数个数为为5!5!5!601! 1! 3!

32、2! 0! 3!2! 1! 2! 1.2 项链排列1.2 排列排列定义定义 1.41.2.4 项链排列项链排列 对对圆圆排排列列，通过转动、平移、翻转、通过转动、平移、翻转、可可重重合的，合的，即即可可看作看作项项链链排排列列。 如如n个不同个不同元素元素的的r项项链链排排列列个数个数为为P(n,r)/(2r)，具体参具体参照照Plya定理定理。1.3 无重组合1.3 组合组合定义定义 1.51.3.1 （无重）组合（无重）组合集合论定义集合论定义定理定理 1.5设设A=an，从从A中选择中选择r个个(0rn)元素元素组合组合起起来，来，A的的r无序子无序子集，集，A的的r组合。组合。如如rn

33、，有，有C(n,r)=P(n,r)/r!=n!/(r!(n-r)!)。如如nr=0，C(n,r)=1；如如nr，C(n,r)=0。从从n个不同个不同元素中元素中，取取r个个(0rn)不不考考虑顺序虑顺序组合组合起起来，其组合数来，其组合数C(n,r) 或或 。 nr证明：证明：从从n个不同个不同元素中取元素中取r个个元素元素的组合数的组合数为为C(n,r)，而而r个个元素元素可组成可组成r!个个r排排列列，即即一个一个r组合对应组合对应r!个个r排排列列。于是。于是C(n,r)个个r组合对应组合对应r!C(n,r)个个r排排列列，这是，这是从从n个不同个不同元素中取元素中取r个个元素元素的的r

34、排排列列数数P(n,r)，因此因此有有 ( , )!( , )!()!P n rnnC n rrrrnr1.3 无重组合推论11.3 组合组合1.3.1 （无重）组合（无重）组合三个推论三个推论推论推论1.5.1：C(n,r)=C(n,n-r)证明：证明：实际上实际上，从从n个不同个不同元素中选元素中选出出r个个元素元素的同时，的同时，就有就有n-r个个元素没元素没有有被选被选出，出，因此选因此选出出r个个元素元素的方式数的方式数等于等于选选出出n-r个个元素元素的方式数，的方式数，即即C(n,r)=C(n,n-r)。得得证。证。另外另外，也可，也可通过通过计算计算得得出证明如下出证明如下 !

35、( ,)( , )()!()! !nnC n nrC n rnrnnrnrr1.3 无重组合推论21.3 组合组合1.3.1 （无重）组合（无重）组合三个推论三个推论推论推论1.5.1：C(n,r)=C(n,n-r)推论推论1.5.2 (Pascal公公式式)：C(n,r)=C(n-1,r)+C(n-1,r-1) 证明：证明：利用利用组合分组合分析析法。在集合法。在集合A的的n个不同个不同元素中固元素中固定一个定一个元素元素，不，不妨妨设设为为a1 ，从从n个个元素中选元素中选出出r个个元素元素的的组合由下组合由下面两面两种种情况情况组成：组成： r个个元素中包含元素中包含a1。相相当于当于从

36、除去从除去a1的的n-1个个元素中选元素中选出出r-1个个元素元素的组合，的组合，再加上再加上a1而得到而得到，组合数，组合数为为C(n-1,r-1)； r个个元素中元素中不不包含包含a1。相相当于当于从除去从除去a1的的n-1个个元素中元素中选选出出r个个元素元素的组合的组合而得到而得到，组合数，组合数为为C(n-1,r)。由由加加法法则法法则即得即得C(n,r)=C(n-1,r)+C(n-1,r-1)另外另外，也可，也可通过通过计算计算得得出证明如下出证明如下 !(1)!()(1)!(1)!( , )!()!(1)!(1)!(1)!(1)!(1)!(1)!(1(1)!(1, )(1,1)n

37、n nnrnr nC n rrnrrnrr rnrnrnnrnrrnrC nrC nr 1.3 无重组合推论31.3 组合组合1.3.1 （无重）组合（无重）组合三个推论三个推论推论推论1.5.1：C(n,r)=C(n,n-r)推论推论1.5.2 (Pascal公公式式)：C(n,r)=C(n-1,r)+C(n-1,r-1) 推论推论1.5.3：C(n,r)=C(n-1,r-1)+C(n-2,r-1)+ +C(r-1,r-1)证明：证明：反复利用反复利用Pascal公公式，式，即即可证明。可证明。或或利用利用组合分组合分析析法，在集合法，在集合A=an的的n个不同个不同元素选元素选出出r个个元

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

39、剩下的下的r-1个个元素中选元素中选出出r-1个个元素元素的组合，的组合，再加再加上上an-r+1而得到而得到，组合数，组合数为为C(r-1,r-1) 。由。由加加法法则法法则得得C(n,r)=C(n-1,r-1)+C(n-2,r-1)+ +C(r-1,r-1)1.3 无重组合例11.3 组合组合1.3.1 （无重）组合（无重）组合例例 题题例例1、有有5本日文书本日文书，7本英文书本英文书，10本中文书本中文书，从中取两本从中取两本不同不同文字文字的的书书，问有多少种方案？若问有多少种方案？若取两本相取两本相同同文字文字的的书书，问有多少种方案？，问有多少种方案？任取两本书任取两本书，有多少

40、种方案？有多少种方案？解：解：从从三种三种文字文字的的书中取两书中取两种种共共有有C(3,2)=3种种取取法。法。根据乘根据乘法法法法则有：则有：日英各日英各一一本本的方法数的方法数为为57=35，中英各中英各一一本本的方法数的方法数为为107=70，中日各中日各一一本本的方法数的方法数为为105=50，由，由加加法法则法法则得得35+70+50=155取两本相取两本相同同文字文字的，有的，有两本中文、两本英文两本中文、两本英文或或两本日文两本日文三种方三种方式，由式，由加加法法则法法则得得C(5,2)+C(7,2)+C(10,2)=76任取两本书任取两本书，相相当于当于从从5+7+10=22

41、本书中取两本本书中取两本的组合，的组合，即即C(22,2)=2311.3 无重组合例21.3 组合组合1.3.1 （无重）组合（无重）组合例例 题题例例2、从从1300之间任取之间任取3个不同的数，个不同的数，使得使得这这3个数的个数的和正好被和正好被3除尽除尽，问，问共共有几种方案？有几种方案？解：解：所有的所有的整整数可分数可分为以为以下下3个分类：个分类：模模3余余0、模、模3余余1和模和模3余余2，故故1300的的300个数可个数可以以分分为为3个集合：个集合：A=1,4,298，B=2,5,299，C=3,6,300。任取任取3个数其个数其和正好被和正好被3整除整除的的情况情况如下：

42、如下：三个数同属于集合三个数同属于集合A，有，有C(100,3)种方案；种方案；三个数同属于集合三个数同属于集合B，有，有C(100,3)种方案；种方案；三个数同属于集合三个数同属于集合C，有，有C(100,3)种方案；种方案；三个数分别属于集合三个数分别属于集合A,B,C，由，由乘乘法法则有法法则有1003种方案。种方案。由由加加法法则法法则得得，所求的方案数，所求的方案数为为3C(100,3)+1003=14851001.3 无重组合例31.3 组合组合1.3.1 （无重）组合（无重）组合例例 题题例例3、某某车站车站有有1到到6个个入口处入口处，每每个个入口处每次只入口处每次只能进一个人

43、，问一能进一个人，问一小小组组9个人进个人进站站的方案数有多少？的方案数有多少？解解I：按照按照从入口从入口1到入口到入口6的的顺序顺序可可得到得到9个人一个排个人一个排列列，再再把把两两个个入口间入口间设设上上一个一个标志标志，加上加上这这5个个标志相标志相当于当于每每一个排一个排列列有有14个个元素元素，其，其中中5个个标志没标志没有有区区别，别，但但其位其位置将区置将区分分各入口各入口的进的进站站人数，人数，相相当于当于14个个元素元素集合的集合的5组合，故进组合，故进站站方案数方案数为为9! C(14,5)=726485760解解II：同同上上分分析析，问题，问题转转化化为重为重集集1

44、*p1,1*p2,1*p9,5*标志标志的的全全排排列（列（pi代表代表9个人，个人，i=1,9），故进，故进站站方案数方案数为为14!/5!=726485760解解III：考虑考虑9个人个人选择选择方案，方案，第第1个人有个人有6种种选择选择，第第2个人个人除了除了选择入口选择入口，还还要要考虑考虑在在第第1个人的个人的前面前面或或后面后面，故有，故有7种种选择选择同理，同理，第第9个人有个人有14种种选择选择，根据乘根据乘法法则，故进法法则，故进站站方案数方案数为为6 7 14=7264857601.3 无重组合例41.3 组合组合1.3.1 （无重）组合（无重）组合例例 题题例例4、求求

45、5位数位数中至中至少出少出现现一个一个6，而被而被3整除整除的数的个数。的数的个数。解：解：10进进制制数数被被3整除整除的的充充要条件是要条件是各各位数的位数的和和能能被被3整除整除。据据此此可进行如下可进行如下讨论讨论：从左从左往往右右计，如最计，如最后后一个一个6出出现现在个位，则在个位，则十百千十百千位位各各有有10种种选择选择，万万位有位有3种可能，种可能，根据乘根据乘法法则，总个数法法则，总个数为为3103 ；如最如最后后一个一个6出出现现在在十十位，则个位有位，则个位有9种种选择选择，百千百千位位各各有有10种种选择选择，万万位有位有3种可能，种可能，根据乘根据乘法法则，总个数法

46、法则，总个数为为31029 ；如最如最后后一个一个6出出现现在在百百位，则个位，则个十十位位各各有有9种种选择选择，千千位有位有10种种选择选择，万万位有位有3种可能，种可能，根据乘根据乘法法则，总个数法法则，总个数为为31092；如最如最后后一个一个6出出现现在在千千位，则个位，则个十百十百位位各各有有9种种选择选择，万万位有位有3种可能，种可能，根据乘根据乘法法则，总个数法法则，总个数为为393；如最如最后后一个一个6出出现现在在万万位，则个位，则个十百十百位位各各有有9种种选择选择，千千位有位有3种可能，种可能，根据乘根据乘法法则，总个数法法则，总个数为为393 ；根据加根据加法法则，法

47、法则，符合条件的符合条件的整整数个数数个数为为3103 + 31029 + 31092 + 393 + 393 =125041.3 无重组合例51.3 组合组合1.3.1 （无重）组合（无重）组合例例 题题例例5、求求1000!的的末尾末尾有几个有几个零零。解：解：此此问题在于求问题在于求将将1000!分解分解为素为素数的数的乘积乘积时，时，2和和5的的幂幂是多少。是多少。末尾零末尾零的个数应的个数应该该等于等于2和和5的的幂中较小幂中较小的的那那个个数。数。11000中中5的的倍倍数的数数的数共共200个，其个，其中中有有40个个52的的倍倍数，这数，这40个数个数中中有有8个个53的的倍倍

48、数，数，而而这这8个数个数中中又有又有1个个54的的倍倍数，数，故故1000!分解分解为素为素数的数的乘积乘积时，时， 5的的幂幂应应该该是是200+40+8+1=249显然，显然，2的的幂必幂必然然大大于于249，因此因此1000!的的末尾末尾有有249个个零零。1.3 无重组合例61.3 组合组合1.3.1 （无重）组合（无重）组合例例 题题例例6、求能求能除尽除尽1400的的正整正整数数目数数目（1除外）除外），其，其中包含中包含多少个多少个奇奇数？数？ 解：解：1400=23527，故，故除尽除尽1400的的正整正整数分解数分解为素为素数的数的乘积乘积的的形形式应式应该为该为2l5m7

49、n，其，其中中0l3,0m2,0n1，但但应排应排除除l=m=n=0的的情况情况。故满足条件的数目。故满足条件的数目为为(3+1)(2+1)(1+1)-1=23其其中包含中包含的的奇奇数数为为(1)(2+1)(1+1)-1=51.3 重复组合1.3 组合组合定义定义 1.61.3.2 重复组合重复组合集合论定义集合论定义定理定理 1.6从从n个不同个不同元素中元素中，可，可重复选取重复选取r个不个不考虑顺序考虑顺序组合组合起起来，其组合数来，其组合数F(n,r)。从重从重集集B=k1*b1, k2*b2, , kn*bn中取中取r个个元素元素不不考虑顺序考虑顺序的组合。的组合。重重集集B=*b

50、1, *b2, , *bn 的的r组组合数合数F(n,r) = C(n+r-1, r)证明：证明：设设n个个元素元素b1,b2,bn和自和自然数然数1,2,n一一对应。于一一对应。于是是任任何组合何组合皆皆可可看作看作是一个是一个r个数的组合个数的组合c1,c2,cr。由于。由于是组合，不是组合，不妨认为各妨认为各ci是按照是按照大小顺序大小顺序排排列列的，的，相相同的同的ci连连续续排在一排在一起起，不，不妨妨设设c1c2cr 。又令又令di=ci+i-1(i=1,2,r)，即即d1=c1,d2=c2+1,dr=cr+r-1。因因1cin，故，故1din+r-1，得到得到一个集合一个集合1,

51、2,n+r-1的的r组合组合 d1,d2,dr (d1d2dr) 。显然有一种显然有一种c1,c2,cr的的取取法，就有一种法，就有一种d1,d2,dr的的取取法，法，反之亦反之亦然，这然，这两两种种取取法是法是一一对应的一一对应的，从而从而这这两两种种取取法是法是等等价价的的。如。如此此，从从n个不同个不同元素中元素中可可重复选取重复选取r个的组个的组合数，合数，和从和从n+r-1个不同个不同元素中元素中不不重复选取重复选取r个的组合数是个的组合数是相相同的，故同的，故F(n,r) = C(n+r-1, r)1.3 重复组合例71.3 组合组合定理定理 1.71.3.2 重复组合重复组合例例

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

53、择选择4个，或者个，或者相相当于当于将将4个个无无区区别的别的球放到球放到3个有个有标志标志的的盒子里盒子里。故。故展开展开项个数项个数为为 F(3,4)=C(3+4-1,4)=151.3 重复组合例8、91.3 组合组合例例 题题1.3.2 重复组合重复组合例例8、某某餐厅餐厅有有7种不同的种不同的菜菜，为了招为了招待朋友待朋友，一个，一个顾客顾客需要需要买买14个个菜菜，问，问有多少种有多少种买买法？法？例例9、求求n个个无区无区别的别的球放入球放入r个有个有标志标志的的盒盒子里子里(nr)而无而无一一空盒空盒的方案数。的方案数。解 ：解 ： 这 个 问 题这 个 问 题 相相 当 于当

54、于 重重 集集*1,*2,*7的的14组合。组合。根根据据定理定理1.6知买菜知买菜的方法数的方法数为为F(7,14)=C(7+14-1,14)=4845解：解：由于由于每每个个盒子盒子不能不能为空为空，故，故每每个个盒子里盒子里可可先放先放一个一个球球，这样这样还剩还剩n-r个个球球，再将再将这这n-r个个球防到球防到r个个盒子里盒子里，由于这时，由于这时每盒每盒的的球球数不数不受受限限制制，相相当于当于重重集集*a1,*a2,*ar的的n-r组合。组合。根据根据定理定理1.6知知，其组合数，其组合数为为 F(r,n-r)=C(r+n-r-1,n-r)=C(n-1,r-1)1.3 重复组合例

55、101.3 组合组合例例 题题1.3.2 重复组合重复组合例例10、在由数在由数0,1,9组成的组成的r位位整整数所组成的集合数所组成的集合中中，如果，如果将将一个一个整整数数重新重新排排列得到另列得到另一个一个整整数，则数，则称称这这两两个个整整数是数是等等价价的。的。那么那么，有多少不等有多少不等价价的的整整数？数？如果如果0和和9最多最多只只能出能出现现一一次次，又有多少不等，又有多少不等价价的的整整数？数？解：解：分分析析题意题意知知，一个，一个r位位整整数数只和只和所所取取的数的数字字有有关关，与与其其顺顺序无关序无关，因而因而是个组合问题。又是个组合问题。又每每一一整整数的数的每每

56、一位可一位可从从0,1,9中任取中任取，故不等，故不等价价的的r位位整整数数相相当于当于重重集集*0,*1,*9的的r组合。组合。根据根据定理定理1.6知知，其组合数，其组合数为为F(10,r)=C(10+r-1, r)=C(9+r,r) 0和和9最多最多只只出出现现一一次次，可分，可分为为三种三种情况情况：均均不出不出现现时时相相当于当于重重集集B=*1,*2,*8的的r组合，组合数组合，组合数为为F(8,r)=C(r+7,r)；只只出出现现其一，若其一，若0出出现现，相相当于当于B的的r-1组合，然组合，然后加入后加入0，组合，组合数数为为F(8,r-1)=C(r+6,r-1)，同理，同理

57、9出出现现的组合数的组合数为为C(r+6,r-1) ；均均出出现现一一次次，相相当于当于B的的r-2组合，然组合，然后加入后加入0,9，组合数，组合数为为F(8,r-2)=C(r+5,r-2)，由，由加加法法则法法则知知，符合题意的，符合题意的整整数个数数个数为为C(r+7,r)+2 C(r+6,r-1)+C(r+5,r-2)1.3 重复组合例111.3 组合组合例例 题题1.3.2 重复组合重复组合例例11、求方求方程程x1+x2+xn=r的非的非负整负整数解的个数解的个数，其数，其中中n,r为正整为正整数。数。解：解：设设重重集集B=*b1,*b2,*bn， B的的任任一个一个r组组合合都

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

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

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