第7章递推关系和生成函数

组合数学—第7章递推关系和生成函数计算机与软件学院陆克中1第7章递推关系和生成函数2许多组合计数问题依赖于一个整数参数n参数n常常表示问题中某个基础集合或多重集合的大小、子集的大小、排列中的位置数目，等等例，设hn表示{1,2,…,n}的排列数，hn=n!。因此，得到一个数的序列h0,h1,h2,…,hn,…，它的一般项hn等于n！例，令gn表示方程x1+x2+x3+x4=n的非负整数解的个数，序列g0,g1,g2,…,gn,…的通项满足gn=𝑛+33本章讨论涉及一个整数参数n的某些计数问题的代数求解方法或者导出一个明确的公式或者导出一个生成函数，其幂级数的系数给出计数问题的解7.1若干数列3设h0,h1,h2,…,hn,…表示一个数列，hn叫做数列的一般项或通项算术数列，其中的每一项比前一项大一个常数qh0,h0+q,h0+2q,…,h0+nq,…hn=hn-1+q,hn=h0+nq部分和sn=(ℎ0+𝑘𝑞)𝑛𝑘=0=(n+1)h0+𝑞𝑛(𝑛+1)2几何数列，其中的每一项是前一项的常数q倍h0,qh0,q2h0,…,qnh0,…hn=qhn-1,hn=h0qn部分和sn=𝑞𝑘𝑛𝑘=0ℎ0=𝑞𝑛+1−1𝑞−1ℎ0(𝑞≠1)(𝑛−1)ℎ0(𝑞=1)例子几何数列(a)hn=2n，求n元素集合的子集数的计数问题的数列，也是确定二进制数表示问题中所使用的数列(b)hn=3n×5，求有n+1种不同类型的对象，而且每一种对象的重数分别是4,2,2,…,2(n个2)的多重集合的组合数7.1若干数列4斐波那契数列斐波那契提出的问题•在一年的伊始，把新近出生的雌雄一对兔子放进一个笼子里。从第二个月开始，每个月这个雌兔子生出雌雄一对兔子。而每对新出生的雌雄兔子也从第二个月开始每个月生出一对雌雄兔子。确定一年后笼子里有多少对兔子设fn表示在第n月开始时笼子里的兔子对数•f0=0,f1=1•fn=fn-1+fn-2在第n月开始，笼子里的兔子对数可以分成两部分：在第n-1月开始已有的那些兔子和第n-1月期间出生的那些兔子在第n-1个月期间出生的兔子的对数是在第n-2个月开始时存在的兔子对数f0,f1,f2,f3,…叫做斐波那契数列，这个数列的项叫做斐波那契数，其递推关系叫做斐波那契递推公式7.1若干数列5例子斐波那契数列的项的部分和为sn=f0+f1+…+fn=fn+2-1通过对n施归纳法证明对于n=0，等式退化成f0=f2-1，成立假设等式对n成立，n≥1。当用n+1代替n时，f0+f1+…+fn+1=(f0+f1+…+fn)+fn+1=(fn+2-1)+fn+1=fn+2+fn+1-1=fn+3-1，成立例子斐波那契数fn是偶数当且仅当n能被3整除显然这一事实与斐波那契数f1,f2,f3的值相符对于一般情况，如果有前三项是偶,奇,奇，则利用斐波那契递推公式，接下来的三项也是偶,奇,奇•奇+奇=偶•奇+偶=奇•偶+奇=奇因此，斐波那契数fn是偶数当且仅当n能够被3整除7.1若干数列6斐波那契数的公式求解递推关系fn-fn-1-fn-2=0的一种方法是寻找形式为fn=qn的解将fn=qn带入以上递推关系可得qn-qn-1-qn-2=0求解上式可得q1=1+52,q2=1−52fn=c1(1+52)𝑛+c2(1−52)𝑛•斐波那契递推关系是线性的且是齐次的定理7.1.1斐波那契数满足公式fn=15(1+52)𝑛-15(1−52)𝑛•f0=c1+c2=0•f1=c11+52+c21−52=1•c1=15,c2=−157.1若干数列7例子设g0,g1,g2,…,gn,…是满足下面给出的斐波那契递推关系和初始条件的数列：gn=gn-1+gn-2,g0=2,g1=-1确定满足下列条件的c1和c2：𝑐1+𝑐2=2𝑐1(1+52)+𝑐21−52=−1解这个方程组，得到c1=5−25,c2=5+25因此，gn=5−25(1+52)𝑛+5+25(1−52)𝑛例子确定用多米诺骨牌完美覆盖2×n棋盘的方法数hn例子确定用单牌和多米诺骨牌完美覆盖1×n棋盘的方法数bn7.1若干数列8定理7.1.2在帕斯卡三角形从左下到右上的对角线上的二项式系数的和是斐波那契数。更精确地说，第n个斐波那契数fn满足fn=𝑛−10+𝑛−11+𝑛−12+…+𝑛−𝑡𝑡−1，其中t=𝑛+12是𝑛+12的向下取整定义g0=0且gn=𝑛−10+𝑛−11+𝑛−12+…+𝑛−𝑡𝑡−1gn=𝑛−10+𝑛−11+𝑛−12+…+0𝑛−1=𝑛−1−𝑝𝑝𝑛−1𝑝=0g0=0−1=0,g1=00=1gn-1+gn-2=𝑛−2−𝑘𝑘𝑛−2𝑘=0+𝑛−3−𝑗𝑗𝑛−3𝑗=0=𝑛−20+𝑛−2−𝑘𝑘𝑛−2𝑘=1+𝑛−2−𝑘𝑘−1𝑛−2𝑘=1=𝑛−20+(𝑛−2−𝑘𝑘𝑛−2𝑘=1+𝑛−2−𝑘𝑘−1)=𝑛−20+𝑛−1−𝑘𝑘𝑛−2𝑘=1=𝑛−10+𝑛−1−𝑘𝑘𝑛−2𝑘=1+0𝑛−1=𝑛−1−𝑘𝑘𝑛−1𝑘=0=gn7.2生成函数9设h0,h1,h2,…,hn,…是无穷数列，它的生成函数定义为无穷级数g(x)=h0+h1x+h2x2+…+hnxn+…。在g(x)中，xn的系数是hn，因此，xn充当hn的“占位符”有限数列h0,h1,h2,…,hm可以看成是无穷数列h0,h1,h2,…,hm,0,0,…。在这个数列中，除去有限项外其余项都等于0。因此，每个有限数列都有一个生成函数g(x)=h0+h1x+h2x2+…+hmxm例子每一项都等于1的无穷数列1,1,1,…,1,…的生成函数是g(x)=1+x+x2+…+xn+…=11−𝑥，它以一种非常简明的形式承载了各项都是1的这样一个无穷数列的全部信息例子二项式系数𝑚0,𝑚1,𝑚2,…,𝑚𝑚的生成函数是gm(x)=𝑚0+𝑚1x+𝑚2x2+…+𝑚𝑚xm=(1+x)m，它以一种简明的形式展示了二项式系数数列的信息例子设α为实数，下面的二项式系数的无穷数列α0,α1,α2,…,α𝑛,…的生成函数是(1+x)α=α0+α1x+α2x2+…+α𝑛xn+…7.2生成函数10例子设k为整数，并设数列h0,h1,h2,…,hn,…，hn等于e1+e2+…+ek=n的非负整数解的数目hn=𝑛+𝑘−1𝑘−1的生成函数是g(x)=∞𝑛=0=𝑛+𝑘−1𝑘−1𝑥𝑛=1(1−𝑥)𝑘1(1−𝑥)𝑘=11−𝑥×11−𝑥×…×11−𝑥(k个因子)=(1+x+x2+…)(1+x+x2+…)…(1+x+x2+…)=(𝑥𝑒1∞𝑒1=0)(𝑥𝑒2∞𝑒2=0)…(𝑥𝑒𝑘∞𝑒𝑘=0)•𝑥𝑒1是第一个因子的代表项，𝑥𝑒2是第二个因子的代表项，…，𝑥𝑒𝑘是第k个因子的代表项•将这些代表项乘起来，得到𝑥𝑒1𝑥𝑒2…𝑥𝑒𝑘=xn,如果e1+e2+…+ek=n•于是，xn的系数等于e1+e2+…+ek=n的非负整数解的个数7.2生成函数11例子什么样的数列的生成函数是如下式子？(1+x+x2+x3+x4+x5)(1+x+x2)(1+x+x2+x3+x4)设𝑥𝑒1(0≤e1≤5),𝑥𝑒2(0≤e2≤2)和𝑥𝑒3(0≤e3≤4)分别表示第一个因子，第二个因子和第三个因子的代表项假设e1+e2+e3=xn，则𝑥𝑒1,𝑥𝑒2,𝑥𝑒3相乘后得到𝑥𝑒1𝑥𝑒2𝑥𝑒3=xnxn的系数是e1+e2+e3=xn的整数解的个数hn，其中0≤e1≤5,0≤e2≤2,0≤e3≤4例子确定苹果、香蕉、橘子和梨的n组合的个数，其中在每个n组合中苹果的个数是偶数，香蕉的个数是奇数，橘子的个数在0和4之间，而且至少要有一个梨这个问题等价于求出方程e1+e2+e3+e4=xn的非负整数解的个数hn，其中e1是偶数(苹果数)，e2是奇数(香蕉数)，0≤e3≤4(橘子数)，而e4≥1(梨数)为每种类型的水果创建一个因子，其中的指数为该类型水果的n组合中所允许的数量：g(x)=(1+x2+x4+…)(x+x3+x5+…)(1+x+x2+x3+x4)(x+x2+x3+x4…)•第一个因子是“苹果因子”，第二个因子是“香蕉因子”，依此类推g(x)=11−𝑥2𝑥1−𝑥21−𝑥51−𝑥𝑥1−𝑥=𝑥2(1−𝑥5)(1−𝑥2)2(1−𝑥)27.2生成函数12例子求装有苹果、香蕉、橘子和梨的果篮的数量hn，其中在每个果篮中苹果数是偶数，香蕉数是5的倍数，橘子数最多是4个，而梨的个数是0或1确定数列h0,h1,h2,…,hn,…的生成函数g(x)，为每种类型的水果引入一个因子g(x)=(1+x2+x4+…)(1+x5+x10+…)(1+x+x2+x3+x4)(1+x)=1(1−𝑥)2=𝑛+1𝑛𝑥𝑛∞𝑛=0=𝑛+1𝑥𝑛∞𝑛=0因此，hn=n+1例子确定方程e1+e2+…+ek=n的非负奇整数解e1,e2,…,ek的个数hn的生成函数g(x)=(x+x3+x5+…)…(x+x3+x5+…)(k个因子)=𝑥1−𝑥2…𝑥1−𝑥2=𝑥𝑘(1−𝑥2)𝑘7.2生成函数13例子设hn表示方程3e1+4e2+2e3+5e4=n的非负整数解的个数。求h0,h1,h2,…,hn,…的生成函数g(x)作如下变量替换：f1=3e1,f2=4e2,f3=2e3,f4=5e4于是hn还等于方程f1+f2+f3+f4=n的非负整数解的个数，其中f1是3的倍数，f2是4的倍数，f3是偶数，f4是5的倍数g(x)=(1+x3+x6+…)(1+x4+x8+…)(1+x2+x4+…)(1+x5+x10+…)=11−𝑥311−𝑥411−𝑥211−𝑥5例子有无限多的一分、五分、一角、两角五分和五角的硬币。确定用这些硬币凑成n分钱的方法数hn的生成函数g(x)hn是方程e1+5e2+10e3+25e4+50e5=n的非负整数解的个数其生成函数是g(x)=11−𝑥11−𝑥511−𝑥1011−𝑥2511−𝑥507.2生成函数14定理7.2.1设h(n,t)表示{1,2,…,n}的排列中有t个逆序的排列的数目，则数列h(n,0),h(n,1),h(n,2),…,h(n,n(n-1)/2)的生成函数是gn(x)=1(1+x)(1+x+x2)(1+x+x2+x3)…(1+x+x2+…+xn-1)=(1−𝑥𝑗)𝑛𝑗=1(1−𝑥)𝑛展开gn(x)，每一项都是形如𝑥𝑎𝑛𝑥𝑎𝑛−1𝑥𝑎𝑛−2…𝑥𝑎1=xp的多项式，其中p=an+an-1+an-2+…+a1，且有0≤an≤0,0≤an-1≤1,0≤an-2≤2,…,0≤a1≤n-1满足0≤an≤0,0≤an-1≤1,0≤an-2≤2,…,0≤a1≤n-1的解与{1,2,…,n}的排列存在一一对应满足p=an+an-1+an-2+…+a1，且有0≤an≤0,0≤an-1≤1,0≤an-2≤2,…,0≤a1≤n-1解与有p个逆序的{1,2,…,n}的排列存在一一对应因此，gn(x)中xp的系数等于h(n,p)7.3指数生成函数15数列h0,h1,h2,…,hn,…的指数生成函数定义为g(e)(x)=ℎ𝑛𝑥𝑛𝑛!∞𝑛=0=h0+h1x+h2𝑥22!+…+hn𝑥𝑛𝑛!+…例子确定数列P(n,0),P(n,1),P(n,2),…,P(n,n)的指数生成函数，其中P(n,k)表示n元素集合的k排列的数目n!/(n-k)!指数生成函数是g(e)(x)=P(n,0)+P(n,1)x+P(n,2)𝑥22!+…+P(n,n)𝑥𝑛𝑛!=1+nx+𝑛!2!𝑛−2!x2+…+𝑛!𝑛!