组合数学课件.ppt

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

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.1 容斥原理 3.2 重集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

3、迭代法与归纳法 5.5 母函数在递推关系中的应用 5.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、果人们想把有限多个对象按照它们所应满足的条件来进行安排，当符合要求的安排并非显然存在或显然不存在时，首要的问题就是要证明或者否定它的存在。这就是存在性问题。如果所要求的安排存在，则可能有多种不同的安排，这又经常给人们提出这样的问题：有多少种可能的安排方案？如何对安排的方案进行分类？这就是计数问题。如果一个组合问题有解，则往往需要给出求其某一特定解的算法，这就是所谓的构造性问题。如果算法很多，就需要在一定的条件下找出一个或者几个最优或近乎最优的安排方案，这就是优化问题。,第1章 排列与组合,本章重点介绍以下的基本计数方法：加法法则和乘法法则 排列 组合 二项式定理的应用 组合恒等式,相互独立的事

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

6、是第i类奖品的集合(i=1,2,3)，显然，SiSj=(ij)，根据加法法则有,1.1 加法法则例2、3,1.1 加法法则和乘法法则,1.1.1 加法法则,例 题,例2、大于0小于10的奇偶数有多少个？,例3、小于20可被2或3整除的自然数有多少个？,解：设S是符合条件数的集合，S1、S2分别是符合条件的奇数、偶数集合，显然，S1S2=，根据加法法则有,若|A|=k，|B|=l，AB=(a,b)|aA，bB，则|AB|=kl。,1.1 乘法法则,1.1 加法法则和乘法法则,1.1.2 乘法法则,乘法法则,相互独立的事件 A、B 分别有 k 和 l 种方法产生，则选取A以后再选取B 的方法数为

7、kl 种。,集合论定义,设 是有限集合，且，则有。,1.1 乘法法则例4,1.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的道路集合，根据乘法法则有,1.1 乘法法则例5,1.1 加法法则和乘法法则,1.1.2 乘法法则,例 题,例5、由数字1,2,3,4,5可以构成多少个所有数字互不相同的四位偶数？,解：所求的是四位偶数，故个位只能选2或4，有两种选择方法；又由于要求

8、四位数字互不相同，故个位选中后，十位只有四种选择方法；同理，百位、千位分别有三种、两种选择方法，根据乘法法则，四位数互不相同的偶数个数为2432=48,1.1 乘法法则例6,1.1 加法法则和乘法法则,1.1.2 乘法法则,例 题,例6、求出从8个计算机系的学生、9个数学系的学生和10个经济系的学生中选出两个不同专业的学生的方法数。,解：由乘法法则有选一个计算机系和一个数学系的方法数为89=72选一个数学系和一个经济系的方法数为910=90选一个经济系和一个计算机系的方法数为108=80由加法法则，符合要求的方法数为72+90+80=242,1.1 重集的概念,1.1 加法法则和乘法法则,1.

9、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,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)

10、!。如n=r，称全排列P(n,n)=n!；如nr,P(n,r)=0；如r=0,P(n,r)=1。,证明：构造集合A的r排列时，可以从A的n各元素中任选一个作为排列的第一项，有n种选法；第一项选定后从剩下的n-1个元素中选排列的第二项有n-1种选法；由此类推，第r项有n-r+1种选法。根据乘法法则有,1.2 线排列推论1,1.2 排列,1.2.1 线排列,两个推论,推论1.1.1：如n,rN且nr2，则P(n,r)=nP(n-1,r-1)。,证明：在集合A的n个元素中，任一个元素都可以排在它的r排列首位，故首位有n种取法；首位取定后，其他位置的元素正好是从A的另n-1个元素中取r-1个的排列，因

11、此有P(n-1,r-1)种取法。由乘法法则有P(n,r)=nP(n-1,r-1)证毕。,1.2 线排列推论2,1.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时，把集合A的r排列分为两大类：一类包含A中的某个固定元素，不妨设为a1，另一类不包含a1。第一类排列相当于先从A-a1中取r-1个元素进行排列，有P(n-1,r-1)种取法，再将a1放入每一个上述排列中，对任一排列，a1都有r种放法。由乘法法则，第一类排列共

12、有rP(n-1,r-1)个。第二类排列实质上是A-a1的r排列，共有P(n-1,r)个。再由加法法则有P(n,r)=rP(n-1,r-1)+P(n-1,r)证毕。,1.2 线排列例1,1.2 排列,1.2.1 线排列,例 题,例1、由数字1,2,3,4,5可以构成多少个所有数字互不相同的四位数？,解：由于所有的四位数字互不相同，故每一个四位数就是集合1,2,3,4,5的一个4排列，因而所求的四位数个数为,1.2 线排列例2,1.2 排列,1.2.1 线排列,例 题,例2、将具有9个字母的单词FRAGMENTS进行排列，要求字母A总是紧跟在字母R的右边，问有多少种这样的排法？如果再要求字母M和N

13、必须相邻呢？,解：由于A总是R的右边，故这样的排列相当于是8个元素的集合F,RA,G,M,E,N,T,S的一个全排列，个数为如果再要求M和N必须相邻，可先把M和N看成一个整体=M,N，进行7个元素的集合F,RA,G,E,T,S,的全排列，在每一个排列中再进行 M,N的全排列，由乘法法则，排列个数为,1.2 线排列例3,1.2 排列,1.2.1 线排列,例 题,例3、有多少个5位数，每位数字都不相同，不能取0，且数字7和9不能相邻？,解：由于所有的5位数字互不相同，且不能取0，故每一个5位数就是集合1,2,9的一个5-排列，其排列数为P(9,5)，其中7和9相邻的排列数为c(7,3)4!242P

14、(7,3)，满足题目要求的5位数个数为,1.2 圆排列,1.2 排列,定义 1.2,1.2.2 圆排列,定理 1.2,设A=an，从A中取r个(0rn)元素按某种顺序（如逆时针）排成一个圆圈，称为圆排列（循环排列）。,设A=an，A的r圆排列个数为P(n,r)/r。,证明：由于把一个圆排列旋转所得到另一个圆排列视为相同的圆排列，因此线排列a1a2ar，a2a3ara1，ara1a2ar-1在圆排列中是一个，即一个圆排列可产生r个不同的线排列；同理，r个不同的线排列对应一个圆排列。而总共有P(n,r)个线排列，故圆排列的个数为 P(n,r)/r=n!/(r(n-r)!)证毕。,1.2 圆排列例4

15、,1.2 排列,例 题,1.2.2 圆排列,例4、有8人围圆桌就餐，问有多少种就座方式？如果有两人不愿坐在一起，又有多少种就座方式？,解：由上述定理知8人围圆桌就餐，有8!/8=7!=5040种就座方式。又有两人不愿坐在一起，不妨设此二人为A、B，当A、B坐在一起时，相当于7人围圆桌就餐，有7!/7=6!种就座方式。而A、B坐在一起时，又有两种情况，或者A在B的左面，或者A在B的右面，因此A、B坐在一起时，共有26!种就座方式，因此如果有两人不愿坐在一起，就座方式为7!-26!=56!=3600,1.2 圆排列例5,1.2 排列,例 题,1.2.2 圆排列,例5、4男4女围圆桌交替就座有多少种

16、就座方式？,解：显然，这是一个圆排列问题。首先让4个男的围圆桌就座，有4!/4=3!种就座方式。因为要求男女围圆桌交替就座，在男的坐定后，两两之间均需留有一个空位，女的就座相当于一个4元素集合的全排列，就座方式数为4!。由乘法法则知，就座方式数为3!4!=144,1.2 重排列,1.2 排列,定义 1.3,1.2.3 重排列,集合论定义,定理 1.3,从n个不同元素中，可重复选取r个按一定顺序排列起来，称为重排列。,从重集B=k1*b1,k2*b2,kn*bn中选取r个按一定顺序排列起来。,重集B=*b1,*b2,*bn 的r排列的个数为nr。,证明：构造B的r排列如下：选择第一项时可从n个元

17、素中任选一个，有n种选法，选择第二项时由于可以重复选取，仍有n种选法，同理，选择第r项时仍有n种选法，根据乘法法则，可得出r排列的个数为nr。证毕。,1.2 重排列例6,1.2 排列,例 题,1.2.3 重排列,例6、由数字1,2,3,4,5,6这六个数字能组成多少个五位数？又可组成多少大于34500的五位数？,解：一个五位数的各位数字可重复出现，是一个典型的重排列问题，相当于重集B=*1,*2,*6的5排列，所求的五位数个数为65=7776。大于34500的五位数可由下面三种情况组成：万位选4,5,6中的一个，其余4位相当于重集B的4排列，由乘法法则知，共有364个五位数；万位是3，千位5,

18、6中的一个，其余3位相当于重集B的3排列，由乘法法则知，共有263个五位数；万位是3，千位4中的一个，百位选5,6中的一个，其余2位相当于重集B的2排列，由乘法法则知，共有262个五位数；由加法法则知，大于34500的五位数个数为364+263+262=4392,1.2 重排列计数,1.2 排列,1.2.3 重排列,定理 1.4,重集B=n1*b1,n2*b2,nk*bk的全排列个数为,证明：将B中的ni个bi看作不同的ni个元素，赋予上标1,2,ni，即，如此，重集B就变成具有n1+n2+nk=n个不同的元素集合显然，集合A的全排列个数为n!。又由于ni个bi赋予上标的方法有ni!种，于是对

19、重集B的任一个全排列，都可以产生集合A的n1!n2!nk!个排列（由乘法法则），故重集B的全排列个数为证毕。注：利用组合数的计数方法同样可以得出证明。,1.2 重排列例7,1.2 排列,1.2.3 重排列,例 题,例6、有四面红旗，三面蓝旗，二面黄旗，五面绿旗可以组成多少种由14面旗子组成的一排彩旗？,解：这是一个重排列问题，是求重集4*红旗,3*蓝旗,2*黄旗,5*绿旗的全排列个数，根据定理，一排彩旗的种数为,1.2 重排列例8,1.2 排列,1.2.3 重排列,例 题,例8、用字母A、B、C组成五个字母的符号，要求在每个符号里，A至多出现2次，B至多出现1次，C至多出现3次，求此类符号的个

20、数。,解：这也是一个重排列问题。根据分析，符合题意的符号个数相当于求重集M=2*A,1*B,3*C的5排列个数，可分为三种情况：需要分别求M-A、M-B和M-C的全排列个数。根据加法法则，此类符号个数为,1.2 项链排列,1.2 排列,定义 1.4,1.2.4 项链排列,对圆排列，通过转动、平移、翻转、可重合的，即可看作项链排列。如n个不同元素的r项链排列个数为P(n,r)/(2r)，具体参照Plya定理。,1.3 无重组合,1.3 组合,定义 1.5,1.3.1（无重）组合,集合论定义,定理 1.5,设A=an，从A中选择r个(0rn)元素组合起来，A的r无序子集，A的r组合。,如rn，有C

21、(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)或。,证明：从n个不同元素中取r个元素的组合数为C(n,r)，而r个元素可组成r!个r排列，即一个r组合对应r!个r排列。于是C(n,r)个r组合对应r!C(n,r)个r排列，这是从n个不同元素中取r个元素的r排列数P(n,r)，因此有,1.3 无重组合推论1,1.3 组合,1.3.1（无重）组合,三个推论,推论1.5.1：C(n,r)=C(n,n-r),证明：实际上，从n个不同元素中选出r个元素的同时，

22、就有n-r个元素没有被选出，因此选出r个元素的方式数等于选出n-r个元素的方式数，即C(n,r)=C(n,n-r)。得证。另外，也可通过计算得出证明如下,1.3 无重组合推论2,1.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。相当于从除去a1的n-1个元素中选出r-1个元素的组合，再加上a1而得到，组合数为C(n-1,

23、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.3 无重组合推论3,1.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个不同

24、元素选出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个元素中不包含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 无重组合例1,1

25、.3 组合,1.3.1（无重）组合,例 题,例1、有5本日文书，7本英文书，10本中文书，从中取两本不同文字的书，问有多少种方案？若取两本相同文字的书，问有多少种方案？任取两本书，有多少种方案？,解：从三种文字的书中取两种共有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本书中取两本的组合，即C(22,2)=23

26、1,1.3 无重组合例2,1.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整除的情况如下：三个数同属于集合A，有C(100,3)种方案；三个数同属于集合B，有C(100,3)种方案；三个数同属于集合C，有C(100,3)种方案；三个数分别属于集合A,B,C，由乘法法则有1003种方案。由加法法则得，所求的方案数为3C(100,3

27、)+1003=1485100,1.3 无重组合例3,1.3 组合,1.3.1（无重）组合,例 题,例3、某车站有1到6个入口处，每个入口处每次只能进一个人，问一小组9个人进站的方案数有多少？,解I：按照从入口1到入口6的顺序可得到9个人一个排列，再把两个入口间设上一个标志，加上这5个标志相当于每一个排列有14个元素，其中5个标志没有区别，但其位置将区分各入口的进站人数，相当于14个元素集合的5组合，故进站方案数为9!C(14,5)=726485760解II：同上分析，问题转化为重集1*p1,1*p2,1*p9,5*标志的全排列（pi代表9个人，i=1,9），故进站方案数为14!/5!=7264

28、85760解III：考虑9个人选择方案，第1个人有6种选择，第2个人除了选择入口，还要考虑在第1个人的前面或后面，故有7种选择同理，第9个人有14种选择，根据乘法法则，故进站方案数为6714=726485760,1.3 无重组合例4,1.3 组合,1.3.1（无重）组合,例 题,例4、求5位数中至少出现一个6，而被3整除的数的个数。,解：10进制数被3整除的充要条件是各位数的和能被3整除。据此可进行如下讨论：从左往右计，如最后一个6出现在个位，则十百千位各有10种选择，万位有3种可能，根据乘法法则，总个数为3103；如最后一个6出现在十位，则个位有9种选择，百千位各有10种选择，万位有3种可能

29、，根据乘法法则，总个数为31029；如最后一个6出现在百位，则个十位各有9种选择，千位有10种选择，万位有3种可能，根据乘法法则，总个数为31092；如最后一个6出现在千位，则个十百位各有9种选择，万位有3种可能，根据乘法法则，总个数为393；如最后一个6出现在万位，则个十百位各有9种选择，千位有3种可能，根据乘法法则，总个数为393；根据加法法则，符合条件的整数个数为3103+31029+31092+393+393=12504,1.3 无重组合例5,1.3 组合,1.3.1（无重）组合,例 题,例5、求1000!的末尾有几个零。,解：此问题在于求将1000!分解为素数的乘积时，2和5的幂是多

30、少。末尾零的个数应该等于2和5的幂中较小的那个数。11000中5的倍数的数共200个，其中有40个52的倍数，这40个数中有8个53的倍数，而这8个数中又有1个54的倍数，故1000!分解为素数的乘积时，5的幂应该是200+40+8+1=249显然，2的幂必然大于249，因此1000!的末尾有249个零。,1.3 无重组合例6,1.3 组合,1.3.1（无重）组合,例 题,例6、求能除尽1400的正整数数目（1除外），其中包含多少个奇数？,解：1400=23527，故除尽1400的正整数分解为素数的乘积的形式应该为2l5m7n，其中0l3,0m2,0n1，但应排除l=m=n=0的情况。故满足条

31、件的数目为(3+1)(2+1)(1+1)-1=23其中包含的奇数为(1)(2+1)(1+1)-1=5,1.3 重复组合,1.3 组合,定义 1.6,1.3.2 重复组合,集合论定义,定理 1.6,从n个不同元素中，可重复选取r个不考虑顺序组合起来，其组合数F(n,r)。,从重集B=k1*b1,k2*b2,kn*bn中取r个元素不考虑顺序的组合。,重集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

32、连续排在一起，不妨设c1c2cr。又令di=ci+i-1(i=1,2,r)，即d1=c1,d2=c2+1,dr=cr+r-1。因1cin，故1din+r-1，得到一个集合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 重复组合例7,1.3 组合,定理 1.7,1.3.2 重复组合,例 题,r个无区别的球放入n个

33、有标志的盒子里，每盒的球数可多于1个，则共有F(n,r)种方案。,例7、试问(x+y+z)4的展开式有多少项？,证明：这是一个允许重复组合的典型问题，实质上定理1.6的另一种说法。由于每盒的球数不受限制，相当于重集*a1,*a2,*an的r组合。,解：(x+y+z)4展开式每一项都是4次方的，相当于从3个不同元素中可以重复的选择4个，或者相当于将4个无区别的球放到3个有标志的盒子里。故展开项个数为 F(3,4)=C(3+4-1,4)=15,1.3 重复组合例8、9,1.3 组合,例 题,1.3.2 重复组合,例8、某餐厅有7种不同的菜，为了招待朋友，一个顾客需要买14个菜，问有多少种买法？,例

34、9、求n个无区别的球放入r个有标志的盒子里(nr)而无一空盒的方案数。,解：这个问题相当于重集*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 重复组合例10,1.3 组合,例 题,1.3.2 重复组合,例10、在由数0,1,9组成的r位整数所组成的集合

35、中，如果将一个整数重新排列得到另一个整数，则称这两个整数是等价的。那么，有多少不等价的整数？如果0和9最多只能出现一次，又有多少不等价的整数？,解：分析题意知，一个r位整数只和所取的数字有关，与其顺序无关，因而是个组合问题。又每一整数的每一位可从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

36、,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)+2C(r+6,r-1)+C(r+5,r-2),1.3 重复组合例11,1.3 组合,例 题,1.3.2 重复组合,例11、求方程x1+x2+xn=r的非负整数解的个数，其中n,r为正整数。,解：设重集B=*b1,*b2,*bn，B的任一个r组合都具有形式x1*b1,x2*b2,xn*bn，其中xi(i=1,2,n)是非负整数且满足方程x1+x2+xn=r。反之，每一个满足

37、方程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.7,1.3.3 不相邻组合,定理 1.8,从序列A=1,2,n个中选取r个，其中不存在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

38、。因1din，故1cin-r+1，得到一个集合1,2,n-r+1的r组合。显然有一种d1,d2,dr的取法，就有一种c1,c2,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个的不相邻组合数，和从n-r+1个不同元素中选取r个的组合数是相

39、同的，即C(n-r+1,r)。,1.4 二项式定理,1.4 二项式定理,定理 1.9,证明：因为(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的系数为上述选法的个数C(n,r)。故有证毕。注：可用数学归纳法证明，证明略；C(n,k)又称二项式系数。,1.4 二项式定理推论1,1.4 二项式定理,四个推论,推论1.9.1：,推论1.9.2：,推论1.9.3：,证明：在推论1.9.2中令x=1，即可得证。利用组合分析，等式左

40、端相当于从A=an中任意选择k(0kn)个元素的所有可能数目，即对n个元素，每一个都有被选择和不被选择的可能，总的可能数为2n。另外，该等式还表明A的所有子集个数为2n。,1.4 二项式定理推论2,1.4 二项式定理,四个推论,推论1.9.1：,推论1.9.2：,推论1.9.3：,推论1.9.4：,证明：在推论1.9.2中令x=-1，即可得证。另外，该等式还表明A=an的偶数子集个数和奇数子集个数相等。,1.4 广义二项式定理,1.4 二项式定理,定理 1.10,定义 1.8,广义二项式系数 为：,牛顿二项式定理：,1.4 广义二项式定理推论1,1.4 二项式定理,六个推论,推论1.10.1：

41、,推论1.10.2：,证明：,1.4 广义二项式定理推论2,1.4 二项式定理,六个推论,推论1.10.1：,推论1.10.2：,推论1.10.3：,推论1.10.4：,推论1.10.5：,证明：当=1/2时，C(,0)=1，而对于k0，有将上式代入推论1.10.1即可得证。,1.4 广义二项式定理推论3,1.4 二项式定理,六个推论,推论1.10.1：,推论1.10.2：,推论1.10.3：,推论1.10.4：,推论1.10.5：,推论1.10.6：,1.5 组合恒等式及其含义1,1.5 组合恒等式及其含义,恒等式1：如n,kN，有C(n,k)=(n/k)C(n-1,k-1),证明：从n个元

42、素中取k个的组合可先从n个元素中取1个，再从剩下的n-1个元素中选择k-1个，组合数为C(n-1,k-1)。选出的k个元素都有可能被第一次选中，因是组合，故重复度为k。得证。或通过计算证明：,1.5 组合恒等式及其含义2,1.5 组合恒等式及其含义,恒等式2：,证明：考虑盒子1中有n个有区别的球，从中取一个球放入盒子2中，再取任意多个球放入盒子3中。等式左端表示先从盒子1中取k(k=1,2,n)个球，再从中取一个放入盒子2中，剩下的k-1个球放入盒子3中。等式右端表示先从盒子1中取一个放入盒子2中，剩下的n-1个球是否放入盒子3中均有两种可能。显然两种取法结果是一样的。得证。或通过计算证明：,

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

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

45、n,r)=C(m,0)C(n,r)+C(m,1)C(n,r-1)+C(m,r)C(n,0),1.5 组合恒等式及其含义10、11,1.5 组合恒等式及其含义,恒等式10：如p,q,nZ且p,q,n0，有,恒等式11：如p,q,nZ且p,q,n0，有,1.5 组合恒等式及其含义12,1.5 组合恒等式及其含义,恒等式12：,证明：利用组合分析法，在集合A=an+1的n+1个不同元素选出k+1个元素的组合可分为以下多种情况：如k+1个元素中包含a1，相当于从除去a1的n个元素中选出k个元素的组合，组合数为C(n,k)；如不包含a1但包含a2，相当于从除去a1,a2的n-1个元素中选出k个元素的组合

46、，再加上a2而得到，组合数为C(n-1,k),同理如不包含a1,a2,an-k+1，但包含an-k+2，相当于从剩下的k个元素中选出k个元素的组合，再加上an-k+2而得到，组合数为C(k,k)；注意，ik时，C(k,k)=0。由加法法则得或对固定的k，对n使用归纳法，当n=0时，有可见，当n=0时，等式成立。如对任意n等式成立，则有可见等式对n+1也成立。由归纳原理，得证。,1.5 组合恒等式及其含义13,1.5 组合恒等式及其含义,恒等式13：,证明：注意，这个恒等式与前面的有一个很不一样的地方，就是C(+j,j),C(+k+1,k)是广义的二项式系数。根据广义的二项式系数的定义，Pasc

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

48、当于从除去a1,a2的n+r-1个元素中选出r-1个元素的组合，再加上a1而得到，组合数为C(n+r-1,r-1),同理如r个元素中包含a1,a2,ar-1，但不包含ar，相当于从剩下的n+1个元素中选出1个元素的组合，再加上a1,a2,ar-1而得到，组合数为C(n+1,1)；如r个元素中包含a1,a2,ar，相当于从剩下的n个元素中选出0个元素的组合，组合数为C(n,0)。由加法法则得C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0),1.5 组合恒等式及其含义14-2,1.5 组合恒等式及其含义,恒等式14：如n,rN，有C(n+r+1,r)

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

50、理如r个元素中包含r个a1，其组合数为C(n,0)。由加法法则得C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+C(n+1,1)+C(n,0),1.5 组合恒等式及其含义15,1.5 组合恒等式及其含义,恒等式15：如n,l,rN,lr，有C(n,l)C(l,r)=C(n,r)C(n-r,l-r),证明：等式的左端可看作是先从n个元素中取l个的组合，从所得的l个元素中再选择r个组合。由此形成了三个组合，所得的全部结果相当于直接从n个元素中取r个的组合，再从剩下的n-r个元素中选择l-r个。得证。或通过计算证明：,1.5 组合恒等式证明方法,1.5 组合恒等式及其含义,常用的证