组合数学第二章二章六节.ppt

1、1,第2章 递推关系与母函数,2.1 递推关系 2.2 母函数(生成函数) 2.3 Fibonacci数列 2.4 优选法与Fibonacci序列的应用 2.5 母函数的性质 2.6 线性常系数齐次递推关系 2.7 关于常系数非齐次递推关系 2.8 整数的拆分 2.9 ferrers图像 2.10 拆分数估计 2.11 指数型母函数 2.12 广义二项式定理 2.13 应用举例 2.14 非线性递推关系举例 2.15 递推关系解法的补充,2,2.14 非线性递推关系举例,(一)多项式展开式的讨论 (二)第一类司特林(Stirling)数的讨论 (三)第二类司特林(Stirling)数的讨论,3

2、,2.14 非线性递推关系举例,(1)多项式系数 (x+y)n展开式的通项xkyn-k项的系数是:C(n,k) 相当于2个不同的球取n个作有重复的排列，其中x取k个，y取n-k个。 也相当于n个不同的球放入2个不同盒子，x盒子放k个，y盒子放n-k个。,指数型母函数是？,(一)多项式展开式的讨论,4,2.14 非线性递推关系举例,(一)多项式展开式的讨论 (2)多项式系数和 (x+y)n展开式的系数和是:2n,这种情况对应着指数型母函数是？,展开式的过程相当于两个不同的元素取n个的有重复的排列。,也相当于把n个不同的球放进两个不同的盒子中。,5,2.14 非线性递推关系举例,(一)多项式展开式

3、的讨论 (3)多项式的项数 (x+y)n展开式的项数是n+1,相当于从两个不同元素中取n个的组合数，允许重复。 也相当于把n个相同的球放进两个不同的盒子中的方案数。 母函数是？,6,定理2.14 (x1+x2+xm)n 展开式通项,项数等于C(m+n-1,n),2.14.1 司特林(Stirling)数,*,系数之和等于mn 。,的系数是:,7,定义2.14.1,称s(n,0),s(n,1),s(n,n)为第一类司特林数。,2.14.1 司特林(Stirling)数,8,其中xk项的系数为s(n-1,k-1)-(n-1)s(n-1,k),2.14.1 司特林(Stirling)数,递推关系式s

4、(n,k)=s(n-1,k-1)-(n-1)s(n-1,k),9,2.14.1 司特林(Stirling)数,递推关系式s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k),初始条件：s(n,0)=0,当kn时，s(n,k)=0,s(n,n)=1,*,10,定义2.14.2 n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类司特林数。,例如：红、黄、蓝3种颜色的球3个，放到两个无区别的盒子里，不允许空盒。其方案如下：,2.14.1 司特林(Stirling)数,讨论的是生活中的分堆现象: 与拆分有什么区别？,11,定理2.14 第二类司特林

5、数S(n,k)有以下性质：,2.14.1 司特林(Stirling)数,12,性质1的意思是把n个不同的球放进0个盒子中或把0个不同的球放进n个盒子的方案数都是0。,性质2的意思是把n个不同的球放进k个盒子中,当球等于或多于盒子时，至少有一种方案。,2.14.1 司特林(Stirling)数,13,性质3的意思是把n个球放进k个盒子中,当盒子多于球数时，要想使盒子不空是不可能的。,性质4的意思是把n个球放进1个盒子中,放法只有一种。,性质5的意思是把n个不同的球放进n个相同的盒子中,不允许空盒，放法也只有一种。,2.14.1 司特林(Stirling)数,14,意思是把n个不同的球放进2个相同

6、的盒子中,当第一个球放进其中一个盒子后，其余n-1个有标志的球都有两种选择，一种是选择与第一个球同盒，第二种选择是与第一个球不同盒。共有2n-1种可能，,要排除都放在同一个盒子的情况。因此共有2n-1-1种方案。,2.14.1 司特林(Stirling)数,15,2.14.1 司特林(Stirling)数,把n个有标志的球放进n-1个相同的盒子中，因为必须保证每个盒子中都有球，因此只有1个盒子中有2个球，问题就是求两个球的组合数，因此有C(n,2)种方案。,16,(1)、剩余的两个球放进一个盒子中，这样的方案对应着从n中取3个的组合数，是C(n,3)。,(2)、剩余的两个球放进二个盒子中，这样

7、的方案对应着从n中取4个，然后再把4个球两两分成2组，将4个球分成两组的方案数是C(4,2)/2。 因此在这种情况下方案数是：C(n,4)C(4,2)/2=3C(n,4)。,例如：1,2,3,4分成两两2组的方案。 (1,2),(3,4),(1,3),(2,4),(1,4),(2,3),2.14.1 司特林(Stirling)数,17,定理2.15 第二类司特林数满足下面的递推关系：,证明：设有n个有区别的球b1,b2,bn,对于其中的某一个球bi, 根据bi的情况分为两类：,1、 bi独占一盒，其方案为S(n-1,m-1),2、 bi不独占一盒，这相当于先将剩下的n-1个球放到m个盒子，不允

8、许空盒，共有S(n-1,m)种不同方案，,2.14.1 司特林(Stirling)数,然后将bi球放进其中一盒，共有m种选择方式。bi球不独占一盒的方案数为mS(n-1,m),18,2.14.1 司特林(Stirling)数,19,2、n个有标志的球放进m个有区别的盒子，不允许空盒问题,2.14.1 司特林(Stirling)数,1、n个有标志的球放进m个相同的盒子，不允许空盒问题,n个有标志的球b1,b2,bn ，放进有区别的m个盒子c1,c2,cm中，无一空盒，其方案数为m!S(n,m),其中1mn,20,2.14.1 司特林(Stirling)数,21,n个球放到m个盒子里，则球和盒子是

9、否有区别？是否允许空盒？共有23=8种状态，其方案情况如下：,1、n个不同的球放到m个不同的盒子里，允许空盒？,2、n个不同的球放到m个不同的盒子里，不允许空盒。,有mn个方案。,有m!S(n,m)。,2.14.1 司特林(Stirling)数,22,4、n个不同的球放到m个相同的盒子里，允许空盒，方案数情况？,S(n,1)+S(n,2)+S(n,m),nm S(n,1)+S(n,2)+S(n,n),nm。,可分为空m-1盒，m-2盒，空1盒，都不空。,3、n个不同的球放到m个相同的盒子里，不允许空盒，方案数情况？,有S(n,m),2.14.1 司特林(Stirling)数,23,5、n个相同

10、的球放到m个不相同的盒子里，允许空盒，方案数情况？,有C(m+n-1,n)。,6、n个相同的球放到m个不相同的盒子里，不允许空盒，方案数情况？,先取m个球每盒一个，余下的n-m无区别的球放进m个不相同的盒子中。则有C(m+(n-m)-1,n-m)=C(n-1,n-m)=C(n-1,m-1),2.14.1 司特林(Stirling)数,24,7、n个相同的球放到m个相同的盒子里，允许空盒，方案数为：,xn项系数，相当于n用1,2,m进行拆分的拆分数。,8、n个相同的球放到m个相同的盒子里，不允许空盒，方案数为：,的xn项系数。,2.14.1 司特林(Stirling)数,*,25,2.13 应用

11、举例,错排问题：若一个排列使得所有的元素都不在原来的位置上，则称这个排列为错排，也叫重排。,1,2的错排是唯一的,即21,1,2,3的错排有312,231。,26,2.13 应用举例,对于1,2,n，设n个数的错排数为Dn,综合以上分析得到递推关系：,取n分别与其它的n-1个数之一互换，其余n-2个数进行错排，共得(n-1)Dn-2个错排。,1、与Dn-1的关系：,n-1个数进行错排，然后n与其中每一个数互换得到(n-1)Dn-1个错排。,2、与Dn-2的关系：,27,2.13 应用举例,28,2.13 应用举例,29,2.13 应用举例,30,2.13 应用举例,例2.13.1 数1,2,3

12、,9的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。,实际上这是一个13579的错排问题。,31,2.13 应用举例,例2.13.2 求在8个字母A,B,C,D,E,F,G,H的全排列中，只有4个元素不在原来位置上的排列数。,从8个字母中任取4个的组合数为C(8,4),4个字母的错排数为：,32,例2.13.3 求,解：,2.13 应用举例,特解:,33,2.13 应用举例,34,2.13 应用举例,例2.13.4 10个数字(0到9)和4个四则运算符（+、-、）组成的14个元素。求由其中的n个元素的排列构成一算术表达式的个数。,1、与an-1的关系,解：设n个元素的算术表达式

13、个数为an。,10an-1 。,2、与an-2的关系,40an-2 。,35,2.13 应用举例,例2.13.5 n条直线将平面分成多少个域？假定无三线共点，且两两相交。,设n条直线将平面分成Dn个域，则第n条直线被其余的n-1条直线分割成n段。这n段正好是新增加的n个域的边界。,所以：Dn=Dn-1+n,D1=2, D0=1,36,2.13 应用举例,例2.13.6 设有n条椭圆曲线，两两相交于两点，任意3条椭圆曲线不相交于一点，试问这样的n个椭圆将平面分隔成多少部分？,一个椭圆将平面分隔成内、外两部分。,an= an-1+2(n-1), a1=2,37,2.13 应用举例,例 2.13.7

14、 一个圆域，依圆心等分成n个部分如图所示，用k种颜色对这n个域进行涂色，要求相邻的域不同色，试问有多少种涂色方案。,设an表示n个域的涂色方案数，分两种情况来讨论。,(1)与an-1的关系，,(k-2)an-1。,(2)与an-2的关系，,(k-1)an-2。,38,2.13.8 两名教师分别对6名学生进行面试（每位教师各负责一门课）每名学生面试时间固定，试问共有多少种面试的顺序？,解：第一位教师的面试顺序有6!种,第一位教师：a1a2a3a4a5a6,第二位教师：a2a1a4a3a6a5,3.3 容斥原理举例,共有6!265,对第一位教师的任何一种面试顺序， 第二门课的顺序有：,*,39,第3章 容斥原理与鸽巢原理,3.1 De