组合数学课件-教案

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 重集r-组合 3.3 错排问题 3.4 有限制排列 3.5* 一般有限制排

3、列 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 群的概念 6.2 置换群 6.3 循环、奇循环与偶循环 6.4 Burnsid

4、e引理 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 11mmiiiiSSS 1.1 加法法则例11.1 加法法则和乘法法则

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

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

9、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 乘法法则例41.1 加法法则和乘法法则加法法则和乘法法则1.1.2

10、 乘法法则乘法法则例例 题题例例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 加法法则和乘法法则加法法则和乘法法则1.1.2 乘法法则乘法法则例例 题题

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

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

13、421.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.2 线排列1.2 排列排列定义定义 1.1

14、1.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个元素中，任一个元素都可以排在个元素中，任一个元素都可以排在它的它的r排列首位，故首

16、位有排列首位，故首位有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) 。证明：证明：当当r2时，把集合

17、时，把集合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 、 将 具 有将 具 有 9

19、 个 字 母 的 单 词个 字 母 的 单 词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,S,

20、 的全的全排列，在每一个排列中再进行排列，在每一个排列中再进行 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个五位数；个五位数； 万位是

28、万位是3，千位，千位4中的一个，百位选中的一个，百位选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个元素，赋予上标个元素，赋予上

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

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

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

32、为个数。根据加法法则，此类符号个数为5!5!5!601! 1! 3!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)元素组合元

33、素组合起来，起来，A的的r无序子集，无序子集，A的的r组合。组合。如如rn，有，有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)个

34、个r排列，这是排列，这是从从n个不同元素中取个不同元素中取r个元素的个元素的r排列数排列数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-

35、r)。得证。得证。另外，也可通过计算得出证明如下另外，也可通过计算得出证明如下 !( ,)( , )()!()! !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个元素的个元素的组合由下面两

36、种情况组成：组合由下面两种情况组成： r个元素中包含个元素中包含a1。相当于从除去。相当于从除去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)!( , )!

37、()!(1)!(1)!(1)!(1)!(1)!(1)!(1(1)!(1, )(1,1)nn 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公式，即可证明。公式，即可证明。或利用组合

38、分析法，在集合或利用组合分析法，在集合A=an的的n个不同元素选出个不同元素选出r个元素的个元素的组合可分为以下多种情况：组合可分为以下多种情况： 如如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

39、个元素中不包含个元素中不包含a1,a2,an-r，但包含，但包含an-r+1，相当于从剩下的，相当于从剩下的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取两本相同文字的，有两本中文、两本英文或两本日文三种方取两本相同文字的，有两本中文、两本英文或两本日文三种方式，由加法法则得式，由加

41、法法则得C(5,2)+C(7,2)+C(10,2)=76任取两本书，相当于从任取两本书，相当于从5+7+10=22本书中取两本的组合，即本书中取两本的组合，即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,

42、298，B=2,5,299，C=3,6,300。任取。任取3个数其和正好被个数其和正好被3整除的整除的情况如下：情况如下：三个数同属于集合三个数同属于集合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 （无重）组

43、合（无重）组合例例 题题例例3、某车站有某车站有1到到6个入口处，每个个入口处，每个入口处每次只能进一个人，问一小组入口处每次只能进一个人，问一小组9个人进站的方案数有多少？个人进站的方案数有多少？解解I ：把两个入口间设上一个标志，加上这把两个入口间设上一个标志，加上这5个标志相当于每一个标志相当于每一个排列有个排列有14个元素，问题转化为重集个元素，问题转化为重集1*p1,1*p2,1*p9,5*标志标志的全排列（的全排列（pi代表代表9个人，个人，i=1,9），故进站方案数为），故进站方案数为14!/5!=726485760解解II ：考虑考虑9个人选择方案，第个人选择方案，第1个人有个

44、人有6种选择，第种选择，第2个人除了个人除了选择入口，还要考虑在第选择入口，还要考虑在第1个人的前面或后面，故有个人的前面或后面，故有7种选择种选择同理，第同理，第9个人有个人有14种选择，根据乘法法则，故进站方案数为种选择，根据乘法法则，故进站方案数为6 7 14=7264857601.3 无重组合例61.3 组合组合1.3.1 （无重）组合（无重）组合例例 题题例例6、求能除尽求能除尽1400的正整数数目（的正整数数目（1除外），其中包含多少个奇数？除外），其中包含多少个奇数？ 解：解：1400=23527，故除尽，故除尽1400的正整数分解为素数的乘积的正整数分解为素数的乘积的形式应该为

45、的形式应该为2l5m7n，其中，其中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个元素不考虑顺序的组合。个元素不考虑顺序

46、的组合。重集重集B=*b1, *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，得

47、到一个集合，得到一个集合1,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.7

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

49、素中可以重复的选择不同元素中可以重复的选择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)而无一空盒而无一空盒的方案数。的方案数。解 ：解 ： 这 个

50、问 题 相 当 于 重 集这 个 问 题 相 当 于 重 集*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-

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

52、题。又每一整数的每一位可从序无关，因而是个组合问题。又每一整数的每一位可从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，组合，

53、组合数为数为F(8,r-1)=C(r+6,r-1)，同理，同理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 不相邻组合1.3 组合（3）1.3 组合组合定义定义 1.71.3.3 不相邻组合不相邻组合定理定理 1.8从序列从序列A=1,2,n个中选取个中选取r个，其个，其中不存在中不存在i,i+1两个相邻

54、的数同时出现两个相邻的数同时出现于一个组合的组合。于一个组合的组合。从序列从序列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,cr的取法。的取法。反之亦

55、然，集合反之亦然，集合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个的不相邻组合数，和从个的

56、不相邻组合数，和从n-r+1个不同元素中个不同元素中选取选取r个的组合数是相同的，即个的组合数是相同的，即C(n-r+1, r)。1.4 二项式定理1.4 二项式定理二项式定理定理定理 1.9 0,()nnkn kknnNx yRxyx yk如如有有证明：证明：因为因为(x+y)n=(x+y)(x+y)(x+y)，等式右端有，等式右端有n个因子，项个因子，项xkyn-k是从这是从这n个因子中选取个因子中选取k个因子，个因子，k=0,1,n。在这。在这k个个(x+y)里都取里都取x，而从剩下的，而从剩下的n-k个因子个因子(x+y)中选取中选取y作乘积得到，因此作乘积得到，因此xkyn-k的系数

57、为上述选法的个数的系数为上述选法的个数C(n,r)。故有。故有证毕。证毕。注：可用数学归纳法证明，证明略；注：可用数学归纳法证明，证明略； C(n, k)又称又称二项式系数二项式系数。 0()nnkn kknxyx yk1.4 二项式定理推论11.4 二项式定理二项式定理四个推论四个推论推论推论1.9.1：推论推论1.9.2：推论推论1.9.3： 000,()nnkn kknnn kkn kkkknnNx yRxyx ynknnxyxyknk如如有有 00,(1)nnnkkkknnnNxRxxxknk 如如有有 0,2nnknnNk如如有有证明：证明：在推论在推论1.9.2中令中令x=1，即可

58、得证。，即可得证。利用组合分析，等式左端相当于从利用组合分析，等式左端相当于从A=an中任意选择中任意选择k(0kn)个个元素的所有可能数目，即对元素的所有可能数目，即对n个元素，每一个都有被选择和不被个元素，每一个都有被选择和不被选择的可能，总的可能数为选择的可能，总的可能数为2n。另外，该等式还表明另外，该等式还表明A的所有子集个数为的所有子集个数为2n。1.4 二项式定理推论21.4 二项式定理二项式定理四个推论四个推论推论推论1.9.1：推论推论1.9.2：推论推论1.9.3：推论推论1.9.4： 000,()nnkn kknnn kkn kkkknnNx yRxyx ynknnxyx

59、yknk如如有有 00,(1)nnnkkkknnnNxRxxxknk 如如有有 0,2nnknnNk如如有有 0,( 1)0nkknnNk如如有有证明：证明：在推论在推论1.9.2中令中令x=-1，即可得证。，即可得证。另外，该等式还表明另外，该等式还表明A=an的偶数子集个数和奇数子集个数相等。的偶数子集个数和奇数子集个数相等。1.4 广义二项式定理1.4 二项式定理二项式定理定理定理 1.10定义定义 1.8 ( , ),(1).(1)/!01000CkRkZkkkkkk 广义广义二项式系数二项式系数 为：为： kkkR x yxyx yk0,|1,() 如如有有牛顿二项式定理：牛顿二项式

60、定理：1.4 广义二项式定理推论11.4 二项式定理二项式定理六个推论六个推论推论推论1.10.1：推论推论1.10.2： kkzzzk0| |1,(1) 有有nkkknkzzzk01| |1,(1)( 1)有有证明：证明：0000(1).(1)(1)!( 1)(1).(1)!1( 1)nkkkkkkkkkknnnknzzzkkn nnkzknkzk 1.4 广义二项式定理推论21.4 二项式定理二项式定理六个推论六个推论推论推论1.10.1：推论推论1.10.2：推论推论1.10.3：推论推论1.10.4：推论推论1.10.5： kkzzzk0| |1,(1) 有有nkkknkzzzk01|