二章六节 非线性递推关系举例

1第2章递推关系与母函数2.1递推关系2.2母函数(生成函数)2.3Fibonacci数列2.4优选法与Fibonacci序列的应用2.5母函数的性质2.6线性常系数齐次递推关系2.7关于常系数非齐次递推关系2.8整数的拆分2.9ferrers图像2.10拆分数估计2.11指数型母函数2.12广义二项式定理2.13应用举例2.14非线性递推关系举例2.15递推关系解法的补充22.14非线性递推关系举例(一)多项式展开式的讨论(二)第一类司特林(Stirling)数的讨论(三)第二类司特林(Stirling)数的讨论32.14非线性递推关系举例(1)多项式系数(x+y)n展开式的通项xkyn-k项的系数是:C(n,k)相当于2个不同的球取n个作有重复的排列，其中x取k个，y取n-k个。也相当于n个不同的球放入2个不同盒子，x盒子放k个，y盒子放n-k个。指数型母函数是？(一)多项式展开式的讨论42.14非线性递推关系举例(一)多项式展开式的讨论(2)多项式系数和(x+y)n展开式的系数和是:2n这种情况对应着指数型母函数是？展开式的过程相当于两个不同的元素取n个的有重复的排列。也相当于把n个不同的球放进两个不同的盒子中。52.14非线性递推关系举例(一)多项式展开式的讨论(3)多项式的项数(x+y)n展开式的项数是n+1相当于从两个不同元素中取n个的组合数，允许重复。也相当于把n个相同的球放进两个不同的盒子中的方案数。母函数是？6定理2.14(x1+x2+…+xm)n展开式通项项数等于C(m+n-1,n)nnnnxxxmnnnmm...,...2122112.14.1司特林(Stirling)数***系数之和等于mn。的系数是:!!...!!21mnnnn7定义2.14.1)1)...(2)(1(nxxxxxn称s(n,0),s(n,1),…,s(n,n)为第一类司特林数。nkxnnsxknsxnsns),(...),(...)1,()0,(2.14.1司特林(Stirling)数8)1)](2)...(2)(1([nxnxxxx其中xk项的系数为s(n-1,k-1)-(n-1)s(n-1,k)1)1,1(...)1,1()0,1([kxknsxnsns2.14.1司特林(Stirling)数)1)...(2)(1(nxxxxxnnkxnnsxknsxnsns),(...),(...)1,()0,()1(nx递推关系式s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)])1,1(...),1(1nkxnnsxkns92.14.1司特林(Stirling)数)1)...(2)(1(nxxxxxnnkxnnsxknsxnsns),(...),(...)1,()0,(递推关系式s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)初始条件：s(n,0)=0当kn时，s(n,k)=0s(n,n)=1****10定义2.14.2n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类司特林数。例如：红、黄、蓝3种颜色的球3个，放到两个无区别的盒子里，不允许空盒。其方案如下：2.14.1司特林(Stirling)数123盒ryb盒ybrbry讨论的是生活中的分堆现象:与拆分有什么区别？11定理2.14第二类司特林数S(n,k)有以下性质：;1,1.5;1,11.4;1,0.3;1,0.2;000.1nS(n,n)n)S(n,nkS(n,k)knS(n,k),n)S()S(n,若若若若)4,(3)3,(2.9)2,(1.8;2)13(213.7;122.6111nCnC)S(n,nnC)S(n,n)S(n,)S(n,nnn2.14.1司特林(Stirling)数12;000.1,n)S()S(n,性质1的意思是把n个不同的球放进0个盒子中或把0个不同的球放进n个盒子的方案数都是0。性质2的意思是把n个不同的球放进k个盒子中,当球等于或多于盒子时，至少有一种方案。;1,0.2knS(n,k)若2.14.1司特林(Stirling)数13;1,0.3nkS(n,k)若性质3的意思是把n个球放进k个盒子中,当盒子多于球数时，要想使盒子不空是不可能的。;1,11.4n)S(n,若性质4的意思是把n个球放进1个盒子中,放法只有一种。;1,1.5nS(n,n)若性质5的意思是把n个不同的球放进n个相同的盒子中,不允许空盒，放法也只有一种。2.14.1司特林(Stirling)数14;122.61n)S(n,意思是把n个不同的球放进2个相同的盒子中,当第一个球放进其中一个盒子后，其余n-1个有标志的球都有两种选择，一种是选择与第一个球同盒，第二种选择是与第一个球不同盒。共有2n-1种可能，要排除都放在同一个盒子的情况。因此共有2n-1-1种方案。2.14.1司特林(Stirling)数15;2)13(213.711nn)S(n,2.14.1司特林(Stirling)数)2,(1.8nC)S(n,n把n个有标志的球放进n-1个相同的盒子中，因为必须保证每个盒子中都有球，因此只有1个盒子中有2个球，问题就是求两个球的组合数，因此有C(n,2)种方案。16)4,(3)3,(2.9nCnC)S(n,n(1)、剩余的两个球放进一个盒子中，这样的方案对应着从n中取3个的组合数，是C(n,3)。(2)、剩余的两个球放进二个盒子中，这样的方案对应着从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第二类司特林数满足下面的递推关系：1,1),1,1(),1(mnmnSmnmSS(n,m)证明：设有n个有区别的球b1,b2,…,bn,对于其中的某一个球bi,根据bi的情况分为两类：1、bi独占一盒，其方案为S(n-1,m-1)2、bi不独占一盒，这相当于先将剩下的n-1个球放到m个盒子，不允许空盒，共有S(n-1,m)种不同方案，2.14.1司特林(Stirling)数然后将bi球放进其中一盒，共有m种选择方式。bi球不独占一盒的方案数为mS(n-1,m)181,1),1,1(),1(mnmnSmnmSS(n,m)2.14.1司特林(Stirling)数;1,1.4;1,11.3;1,0.2;000.1nS(n,n)n)S(n,nkS(n,k),n)S()S(n,若若若192、n个有标志的球放进m个有区别的盒子，不允许空盒问题2.14.1司特林(Stirling)数1、n个有标志的球放进m个相同的盒子，不允许空盒问题n个有标志的球{b1,b2,…,bn}，放进有区别的m个盒子{c1,c2,…,cm}中，无一空盒，其方案数为m!S(n,m),其中1≤m≤nmknknkmkmCa0))(,()1(mknkkmkmCmmnS0))(,()1(!1),(202.14.1司特林(Stirling)数mknkkmkmCmmnS0))(,()1(!1),(;122.61n)S(n,;2)13(213.711nn)S(n,21n个球放到m个盒子里，则球和盒子是否有区别？是否允许空盒？共有23=8种状态，其方案情况如下：1、n个不同的球放到m个不同的盒子里，允许空盒？2、n个不同的球放到m个不同的盒子里，不允许空盒。有mn个方案。有m!S(n,m)。2.14.1司特林(Stirling)数mknknkmkmCa0))(,()1(224、n个不同的球放到m个相同的盒子里，允许空盒，方案数情况？S(n,1)+S(n,2)+…+S(n,m),n≥mS(n,1)+S(n,2)+…+S(n,n),n≤m。可分为空m-1盒，m-2盒，…，空1盒，都不空。3、n个不同的球放到m个相同的盒子里，不允许空盒，方案数情况？有S(n,m)2.14.1司特林(Stirling)数mknknkmkmCma0))(,()1(!1235、n个相同的球放到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)数247、n个相同的球放到m个相同的盒子里，允许空盒，方案数为：)1)...(1)(1(1)(2mxxxxGxn项系数，相当于n用{1,2,…,m}进行拆分的拆分数。8、n个相同的球放到m个相同的盒子里，不允许空盒，方案数为：)1)...(1)(1()(2mmxxxxxG的xn项系数。2.14.1司特林(Stirling)数***252.13应用举例错排问题：若一个排列使得所有的元素都不在原来的位置上，则称这个排列为错排，也叫重排。1,2的错排是唯一的,即211,2,3的错排有312,231。262.13应用举例对于1,2,…,n，设n个数的错排数为Dn综合以上分析得到递推关系：1,0),)(1(2121DDDDnDnnn取n分别与其它的n-1个数之一互换，其余n-2个数进行错排，共得(n-1)Dn-2个错排。1、与Dn-1的关系：n-1个数进行错排，然后n与其中每一个数互换得到(n-1)Dn-1个错排。2、与Dn-2的关系：272.13应用举例!nDEnn令21!)1(!)1(!nnnDnnDnnnD1,0),)(1(2121DDDDnDnnn)!2(1)!1()1(21nDnnDnnnn211)11(nnnEnEnE))(1(211nnnnEEnEE282.13应用举例))(1(211nnnnEEnEE1nnnEEF设11nnFnF2221!2)1(...))(11)(1(1FnFnnFnFnnnn21!1!212122DDEEF292.13应用举例!1)1(,!1)1(1nEEnFnnnnn即211)!1(1)1(!1)1(!1)1(nnnnnnEnnEnE1!)!1)1(...!31!21!111(!!ennnEnDnnn121!2)1(...)!1()1(!)1(Ennnn302.13应用举例例2.13.1数1,2,3,…,9的全排列中，求偶数在原来位置上，其余都不在原来位置上的错排数目。实际上这是一个13579的错排问题。441-520-60)12012416121120()!51!41!31!21!111(!55D312.13应用举例例2.13.2求在8个字母A,B,C,D,E,F,G,H的全排列中，只有4个元素不在原来位置上的排列数。914-12)2416121(24)!41!31!21!111(!44D从8个字母中任取4个的组合数为C(8,4)6309)4,8(C4个字母的错排数为：32例2.13.3求nknkS02解：2222)1(...321nnSn2221)1(...321nSn21nSSnn2.13应用举例特解:)(33