组合数学7-2003

1、组合数学(Combinatorics),哈尔滨工业大学(威海)计算机科学与技术学院 孟凡超 Email: Tele主要内容,概述 鸽巢原理 排列与组合 生成排列和组合 二项式系数 容斥原理及应用 递推关系和生成函数 特殊计数序列 Polya计数法,递推关系和生成函数,数列：令h0,h1,h2,hn,表示一个数列，其中，hn叫做数列的一般项。 常见数列：,n个元素的集合的排列数:,n个元素的集合的r排列数:,n个元素的集合的循环r排列数：,具有k种不同类型元素且每种都有无限重数的多重集的n排 列数：,令S为具有k种不同类型元素，各元素的重数分别为 n1,n2,nk，且n

2、1+n2+nk=n，则S的排列数：,n个元素的集合的循环排列数：,递推关系和生成函数,n个元素集合的k组合数:,具有k种不同类型元素且每种都有无限重数的多重集的n组 合数：,错位排列数：,禁排位置排列数：,递推关系和生成函数,算术序列：其中的每一项比前一项大一个常数q。,几何序列：其中的每一项是前一项的常数q倍。,递推关系和生成函数,例：确定平面一般位置上的n个相交叠的圆所形成的区域数。所谓相互交叠是指每两个圆相交在不同的两个点上(因此，不相交或相切是不允许的)。一般位置指的是不存在有一个公共点的三个圆。,h0=1 h1=2 h2=4 h3=8 ,递推关系和生成函数,设n-1个一般位置上相互交

3、叠的圆形成的区域数为hn-1。 放入第n个圆后，前n-1个圆的每一个都与第n个圆相交于两点，由于这些圆都是在一般位置上，所以得到2(n-1)个不同的点P1,P2,P2(n-1)。 这2(n-1)个点把n个圆分成2(n-1)条弧：P1P2，P2P3,P2(n-1)-1P2(n-1)和P2(n-1)P1。这2(n-1)条弧中的每一条都把前n-1个圆形成的区域一分为二，形成了2(n-1)个区域。因此，,递推关系和生成函数,利用递推关系可以得到hn关于参数n的公式。,递推关系和生成函数,例：在一年之初把性别相反的一对新生的兔子放进围栏。从第二个月开始，母兔每月生出一对性别相反的小兔。每对新生兔也从它们

4、第二个月大开始每月生出一对新兔。求一年后围栏内兔子的对数。,斐波那契数： fn=fn-1+fn-2 (n3),递推关系和生成函数,例：确定2n棋盘用多米诺牌完美覆盖的方法数hn。,h1=1,h2=2,h3=3,递推关系和生成函数,令n2，我们将2n棋盘划分成两部分A和B。 A部分：有一块竖直多米诺牌覆盖左上角方格的那些完美覆盖。 B部分：有一块水平的多米诺牌放在左上角方格，另一块水平多米诺牌覆盖棋盘左下角方格的那些完美覆盖。,A,B,|A|=hn-1,|B|=hn-2,hn=|A|+|B|=hn-1+hn-2,递推关系和生成函数,定理：沿Pascal三角形左下到右上对角线上的二项式系数的和是斐

5、波那契数fn。更一精确地说，第n个斐波那契数fn满足：,递推关系和生成函数,f1=1 f2=1 f3=2 f4=3 f5=5 f6=8 ,递推关系和生成函数,线性递推关系 令h0,h1,h2,hn,是一个数列，如果存在a1,a2,ak0和bn(每个量都可能依赖于n)，使得,则称该序列满足k阶线性递推关系。 如果bn=0，则称(1)为齐次递推关系。如果a1,a2,ak为常数，则称(1)为具有常系数。,(1),递推关系和生成函数,例：错位排列D0,D1,Dn,满足两个递推关系 Dn=(n-1)Dn-1+(n-1)Dn-2 (n2) Dn=nDn-1+(-1)n (n1) 第一个为2阶线性齐次递推关

6、系，第二个为1阶非齐次递推关系。,递推关系和生成函数,例：平面上圆的区域划分序列h1,h2,hn,满足1阶非齐次递推关系 hn=hn-1+2(n-1) (n2) 例：斐波那契序列f1,f2,fn,满足2阶齐次递推关系 fn=fn-1+fn-2 (n2),递推关系和生成函数,例：算术序列h1,h2,hn,满足1阶非齐次递推关系 hn=hn-1+q (n1) 例：几何序列h1,h2,hn,满足1阶齐次递推关系 hn=qhn-1 (n1),递推关系和生成函数,常系数线性齐次递推关系求解方法 hn=a1hn-1+a2hn-2+akhn-k (nk) 其中，a1,a2,ak是常系数且ak0。,如果初始值

7、h0,h1,hk-1的值能够给出，则满足递推关系(2)的数列h0,h1,hn,就被唯一确定。,(2),递推关系(2)从n=k开始解开。 我们首先忽略初始值并没有给出的情况下寻求(2)的解。,递推关系和生成函数,常系数线性齐次微分方程求解方法(高等数学) 例：求微分方程y-5y+6y=0的解,初始条件:y(0)=a，y(0)=b。,在基本指数函数y=eqx中寻找这个方程的解。,递推关系和生成函数,定理：令q为一非零数，则hn=qn是常系数线性齐次递推关系 hn=a1hn-1+a2hn-2+akhn-k (ak0,nk) (a) 的解，当且仅当q是多项式方程 xk-a1xk-1-a2xk-2-ak

8、=0 (b) 的一个根。如果多项式方程有k不同的根q1,q2,qk，则 hn=c1q1n+c2q2n+ckqkn (c) 是下述意义下式(a)的一般解：无论给定h0,h1,hk-1什么初始值，都存在常数c1,c2,ck使得式(c)满足递推关系(a)和初始条件的唯一的序列。,递推关系和生成函数,多项式方程(b)叫作递推关系(a)的特征方程，它的k个根叫作特征根。如果特征互异，那么(c)就是(a)的一般解。,递推关系和生成函数,证明：hn=qn为式(a)的解当且仅当 qn-a1qn-1-a2qn-2-akqn-k=0 对所有的nk都成立。由于假设q0，可以消去qn-k。于是上述方程等价于方程 qk

9、-a1qk-1-a2qk-2-ak=0 所以hn=qn是式(a)的解，当且仅当q是多项式方程(b)的根。 由于ak0，所以0不是式(b)的根。因此，式(b)有k个异于零的根q1,q2,qk。我们假设根q1,q2,qk是互异的。于是 hn=q1n,hn=q2n,hn=qkn是式(a)的k个不同的解。递推关系(a)线性和齐次意味着对于任意选择常数c1,c2,ck hn=c1q1n+c2q2n+ckqkn 也是式(a)的解。,递推关系和生成函数,现在证明式(c)在定理所述的意义下是式(a)的一般解。 设初始值h0=b0,h1=b1,hk-1=bk-1 我们需要证明无论b0,b1,bk-1如何选取，我

10、们都能够选择常数c1,c2,ck使得hn满足这些初始条件。即， 无论c1,c2,ck如何选取我们都能够解出下面方程：,递推关系和生成函数,这个方程组的系数矩阵是,该矩阵为范德蒙矩阵。范德蒙矩阵为可逆的当且仅当q1,q2,qk互异。因此，当q1,q2,qk互异且不为0时，方程组对于b0,b1,bk-1的每种选择都有唯一解。因此，式(c)是式(a)的一般解。,递推关系和生成函数,例：求斐波那契序列fn-fn-1-fn-2=0，f0=0,f1=1的一般解。,例：求解满足初始值h0=1,h1=2和h2=0的递推关系hn=2hn-1+hn-2-2hn-3 (n3),递推关系和生成函数,如果特征方程的根q

11、1,q2,qk不互异，那么 hn=c1q1n+c2q2n+ckqkn 就不是递推关系的一般解。 例：求递推关系hn=4hn-1-4hn-2的一般解。 求微分方程y-4y+4y=0的解。,递推关系和生成函数,定理：令q1,q2,qt为常系数线性齐次递推关系 hn=a1hn-1+a2hn-2+akhn-k (ak0,nk) 的特征方程互异根。此时，如果qi是si重根，则递推关系对qi的部分一般解为,递推关系的一般解则是,递推关系和生成函数,非齐次递推关系 例(hanoi塔问题)：有三个针柱，在一个针柱上穿有大小递增的n个圆盘，其中最大的圆盘在底部。现在一次一个地将这些圆盘移到另一个针柱上，规定任意

12、时刻不允许将大圆盘放到小圆盘上面。确定将圆盘从一个针柱移到另一个针柱所必需的移动次数。,第1个针柱,第2个针柱,第3个针柱,hn=2hn-1+1 (n1) h0=0,递推关系和生成函数,求递推关系：hn=2hn-1+1 (n1) h0=0,首先考虑对应的齐次递推关系: hn=2hn-1 (n1) 其特征方程为x-2=0，它有一个特征根q=2，并给出一般解:hn=c2n (n1) 。 然后求非齐次递推关系: hn=2hn-1+1 (n1)的一个特解。我们试图寻找形如hn=d的解。代入递推关系，得到d=-1。 将齐次关系的一般解和非齐次关系的特解结合，得到hn=c2n-1，根据初始条件，得到c=1

13、，所以， hn=2n-1。,递推关系和生成函数,求解非齐次递推关系方法： 求齐次关系的一般解。 求非齐次关系的一个特解。 将一般解与特解联合，确定在一般解中出现的常数值，使得联合的解满足初始条件。,递推关系和生成函数,如果bn是n的k次多项式，那么寻找也是n的k次多项式的特解hn。因此，尝试 a) hn=r(常数)，如果bn=d(常数) b) hn=rn+s，如果bn=dn+e c) hn=rn2+sn+t，如果bn=fn2+dn+e,递推关系和生成函数,如果bn是指数形式，那么寻找的特解也是指数的形式。因此，尝试 hn=pdn，如果bn=dn。 例：求解hn=3hn-1-4n (n1)，h0

14、=2。 例：求解hn=2hn-1+3n (n1)，h0=2。 例：求解hn=3hn-1+3n (n1)，h0=2。 例：求解hn=hn-1+n3 (n1)，h0=0。,递推关系和生成函数,生成函数 无穷级数生成函数：令h0,h1,h2,hn,为一无穷数列。它的生成函数定义为无穷级数 g(x)=h0+h1x+h2x2+hnxn+ 在g(x)中，xn的系数是数列的第n项hn，从而xn作为hn的位置持有者。 有穷级数生成函数：有限序列h0,h1,hm可以看成无穷序列h0,h1,h2,hn,中除去有限项外所有的其余的项都等于0。因此，每个有限序列都有一个生成函数g(x)=h0+h1x+h2x2+hnx

15、n。 它是一个多项式。,递推关系和生成函数,常见生成函数 例：序列1,1,1,的生成函数为 g(x)=1+x+x2+xn+=1/(1-x) 例：二项式系数 的生成函数为,例：牛顿二项式系数 的生成函数为,递推关系和生成函数,例：令k是一个整数，并令序列h0,h1,hn, 使hn等于e1+e2+ek=n的非负整数解的个数。,序列的生成函数为：,递推关系和生成函数,证明：,递推关系和生成函数,这些典型项相乘，得到,如果,于是xn的系数等于上述方程的非负整数解的个数，而这个数为：,所以,递推关系和生成函数,例: (1+x+x2+x3+x4+x5)(1+x+x2)(1+x+x2+x3+x4)是什么样序

16、列的生成函数？,令,递推关系和生成函数,例: 确定苹果、香蕉、橘子和梨的n-组合的个数，其中在每个n-组合中苹果的个数为偶数，香蕉的个数为5的倍数，桔子的个数在0和4之间，而且至少要有一个梨。,计算苹果、香蕉、橘子和梨的某些n-组合。我们需要确定h0, h1,hn,的生成函数。 对于每种类型的水果引入一个因子，则,递推关系和生成函数,因此，hn=n+1。,递推关系和生成函数,凸多边形的三角形区域划分问题 4凸多边形的三角形区域划分方法数为多少？ 5凸多边形的三角形区域划分方法数为多少？,n凸多边形的三角形区域划分方法数为多少？,递推关系和生成函数,基本概念 凸集：对于平面或空间中的点集K，如果

17、K中的任意两个点p和q的连接pq线段上的所有的点都在K内，则K叫做凸集。例如，平面上的三角形区域、圆形区域和矩形区域等都是凸集。而下图(a)的区域则不是凸集。,(a),(b),递推关系和生成函数,多边形区域：多边形区域是指由n个不同的平面坐标点首尾相连而成的闭折线及其所围的有限平面区域。任意多边形区域至少有三条边。多边形区域分为凸多边形区域和非凸多边形区域。,递推关系和生成函数,顶点：在多边形区域中边和边相交的点叫做顶点(隅点)。 对角线：连接两个非邻接顶点的线段叫做对角线。,1,2,3,4,5,定理：令K是具有n条边的一个多边形区域，则其对角线的数目为n(n-3)/2。,递推关系和生成函数,

18、凸集划分：设K为一个凸集，则K的每一条对角线把K分成具有k条边的一个凸多边形区域和另外一个具有n-k+2条边的区域，其中，k=3,4,n-1。,1,2,3,4,5,K1,K2,K,凸集三角形区域划分：设K为一个包含n个点的凸集，对于K中的每一个顶点，存在n-3条对角线，这些对角线将K划分成n-2个三角形区域。,1,2,3,4,5,K1,K2,K3,K,递推关系和生成函数,凸集三角形区域划分问题：设K为一个包含n个点的凸集，存在多少种方法在K中插入n-3条不相交的对角线将K划分为n-2个三角形区域？,定理：通过画出在区域内部不相交的对角线将具有n+1条边的凸多边形区域分成三角形区域，令hn表示分

19、成三角形区域的方法数。定义h1=1。则hn满足递推关系：,该递推关系的解为：,递推关系和生成函数,n=1表示两条边的多边形，我们规定h1=1。 n=2表示三角形，由于三角形区域没有对角线而且也不能进一步再分，我们有h2=1。递推关系对于n=2时也成立。,h1=1,h2=1,h3=2,递推关系和生成函数,n3表示边大于等于4的凸多边形K。 选定K的一条边并把它作为基边。在将K划分为成三角形区域的每一种分法中基边都是这些三角形区域T中的一个三角形区域的边，并且这个三角形区域将K的其余部分分成具有k+1条边的多边形区域K1和具有n-k+1条边的多边形区域K2，k=1,2,n-1。,基边,K1 (k+

20、1边),K2 (n-k+1边),递推关系和生成函数,通过分别插入K1和K2的对角线，将K进一步分成三角形区域，这些对角线区域内部不相交。 由于K1有k+1条边，因此，K1可以有hk种方法分成三角形区域。由于K2有n-k+1条边，因此，K2可以用hn-k种方法分成三角形区域。 于是对于含有基边的特定三角形区域T的特定的选择。存在内部不相交的对角线把区域K分成三角形区域的方法数为hkhn-k。 根据加法原理，总共的方法数为：,递推关系和生成函数,1,2,3,4,5,基边,K2 (4边),K1 (2边),1,2,3,4,5,基边,K2 (3边),K1 (3边),1,2,3,4,5,基边,K2 (2边

21、),K1 (4边),k=1,k=2,k=3,k=1时，h1h3=12=2 k=2时，h2h2=11=1 k=3时，h3h1=21=2 所以，h4=h1h3+h2h2+h3h1=2+1+2=5。,n=4的情况(5凸多边形),递推关系和生成函数,n=5的情况(6凸多边形),k=1,K1 (2边),K2 (5边),k=2,K1 (3边),K2 (4边),k=3,K1 (4边),K2 (3边),k=4,K1 (5边),K2 (2边),k=1时，h1h4=15=5 k=2时，h2h3=12=2 k=3时，h3h2=21=2 k=4时，h4h1=51=5 所以h5=h1h4+h2h3+h3h2+h4h5=

22、5+2+2+5=14。,递推关系和生成函数,接下来需要证明：,可以验证上述公式对于n=1,2,3,4,5都成立。,递推关系和生成函数,令g(x)=h1+h2x2+hnxn+是序列h1,h2,hn,的生成函数。我们将g(x)自乘，可以得到,于是g(x)满足方程,递推关系和生成函数,由g(x)的定义可知g(0)=0，由于g1(0)=1和g2(0)=0，因此,根据牛顿二项式定理有:,用-4x代替z，有,递推关系和生成函数,从而,上式也称为Catalan数。,递推关系和生成函数,排列问题,n个元素的集合的排列数:,n个元素的集合的r排列数:,n个元素的集合的循环r排列数：,具有k种不同类型元素且每种都

23、有无限重数的多重集的n排 列数：,令S为具有k种不同类型元素，各元素的重数分别为 n1,n2,nk，且n1+n2+nk=n，则S的排列数：,n个元素的集合的循环排列数：,递推关系和生成函数,令S为具有k种不同类型元素，各元素的重数分别为n1,n2,nk，则S的n排列数为多少？,如果n=n1+n2+nk，则排列数为,如果nn1+n2+nk，则排列数为0,如果nn1+n2+nk，则排列数为？,递推关系和生成函数,指数生成函数 生成函数：令h0,h1,h2,hn,为一无穷数列，它的生成函数定义为无穷级数 g(x)=h0+h1x+h2x2+hnxn+ 在g(x)中，xn的系数是数列的第n项hn，从而x

24、n作为hn的位置持有者。 指数生成函数：令h0,h1,h2,hn,为一无穷数列，它的指数生成函数定义为无穷级数,在g(x)中，xn/n!的系数是数列的第n项hn，从而xn/n!作为hn的位置持有者。,递推关系和生成函数,常见指数生成函数 数列1,1,1,的指数生成函数为,数列P(n,0),P(n,1),P(n,n)的指数生成函数为,递推关系和生成函数,数列k0,k1,k2,kn,(k为一实数)的指数生成函数为,对于正整数k，kn表示每一种都有无穷重数的k种不同类型物体的多重集的n-排列的个数。,递推关系和生成函数,定理：令S为多重集n1a1,n2a2,nkak，其中，n1,n2,nk为非负整数

25、。令hn表示S的n排列。则序列h0,h1,h2,hn,的指数生成函数g(e)(x)由下式给定,其中，对于i=1,2,k,递推关系和生成函数,证明：,被乘开后得到形如,的项，其中，0m1n1, 0m2n2, 0mknk,令n=m1+m2+mk，则上式可以写成,递推关系和生成函数,xn/n!的系数为,其中，0m1n1, 0m2n2, 0mknk以及n=m1+m2+mk。,等于S的多重子集m1e1,m2e2,mkek的n排列的个数。由于S的n排列的个数等于具有m1+m2+mk=n的所有 子多重集排列个数，因此S的n排列数hn等于,它是xn/n!的系数。所以,递推关系和生成函数,例：考虑3种类型9个元素的多重集S=3a,2b,4c。求S的8排列的个数。,递推关系和生成函数,方法2：S的8排列首先可以按照a划分为2部分：a的重数为2和a的重数为3。a的重数为0和1的情况不满足。 对于a的重数为2的情况，必有b的重数为2，c的重数为3，因此，等价于S的多重子集2a