生成函数理论及应用论文

1引言组合数学(CombinatorialMathematics),又称为离散数学。狭义的组合数学主要研究满足一定条件的组态(也称组合模型)的存在、计数以及构造等方面问题。组合数学等领域中都有着广泛的应用价值，特别是在计算机科学中有着重要的应用。计数技术、排列组合、Polya计数法、二项式系数、容斥原理、生2生成函数数有普通型生成函数和指数型生成函数两种，其中普通型用的比较多，并被广泛应用。 2.1生成函数的基本概念x1x1x⁰x²x⁰。(1+x)³(1+x+x²)²=(x⁰+x¹)(x⁰+x¹)(x⁰+x¹)×(x⁰+x¹+x²)(x⁰+x¹+x²)然数),它的生成函数就是f(x)=1+x+x²+x³+x⁴+…(每一项都是1,即使n=0是1,4,6,4,1,0,0,0,(从4个x³)(x²)³+(1+x+x²)(x²)⁴+(1+x)(x²)⁵+(x²)⁶=x²+x³+2x⁴+2x⁵+3x⁶+2.2生成函数的性质 性质1例1已知性质2若bk=ak+l:则 例2已知则则性质3若证明：由假设条件，有b₀=a₀:b₁x=a₀x+a₁x:b₂x²=a₀x²+a₁x²+a₂x²,bx=a₀x⁴+a₁x*+a₂x*+…+akx*,把以上各式的两边分别相加，得B(x)=a₀(1+x+x²+…)+a₁x(1+x+x²+…)+a₂x²(1+x+x²+…)+…例3已知性质4若则b₀=a₀+a₁+a₂+…=A(1),b₁x=a₁x+a₂x+…=[A(1)-a₀]x,b₂x²=a₂x²+a₃x³+…=[A(1)-a₀-a₁]x²,bkx*=axx*+ak+ixk+1+…=[A(1)-ao-a₁-…-ak-1]x*,B(x)=A(1)+[A(1)-a₀]x+[A(1)-ao-a₁]x²+…=A(1)(1+x+x²+…)-anx(1+x+x²+…)-a₁x²(1+x+x²+…) 则则=x·B(x),Ck=aak+βb,则 性质8若则=a₀(b₀+b₁x+b₂x²+…)+a₁x(b₀+b₁x+b₂x²+…)+a₂x²(b₀+b₁x+b₂x²+…)+…=(a₀+a₁x+a₂x²)(b₀+b₁x+b₂x²+…)=A(x)·B(x)。则 例6求序列{5,6,7,…,n+5,…}A(x)=5+6x+7x²+…+(n+5)x"=5(1+x+x²+…)+(x+2x²+3x³+…)=5G{1}+G{k}2.3普通型生成函数O≤k₁≤5,0≤k₂≤4,0≤k₃≤3。(1+x+x²+x³),(1+x+x²+x³+x⁴),(1+x+x²+x³+x⁴+x⁵)2.4指数型生成函数若α=1,则序列(1,1,…,1)的指数生成函数e*。故 例10五个数字1,1,2,2,3能组成多少个四位数?2.5生成函数的基本运算C;=a;+b₁(i=0,1,2,…,r,…)。设A(x)是序列(a₀,a₁,…,a,,…)的普通生成函数，则A(x)/(1-x)故是序列(1,1,…,1,…)的普通生成函数。令和是序列 Co=a₀·1=a₀,C₁=a₀·1+a₁·1=a₀+a₁,C₂=a₀·1+a₁·1+a₂·1=ao+a₁+a₂,C₁=a₀·1+a₁·1+…+a,·1=a₀+a₁+…+a,定义6C(x)=A(x)+B(x)当且仅当对所有的i,都有C₁=a₁+b₁(i=0,1,2,…,r,…)。例11证明恒等式将上式与定义7相比较，可见有;数。由于是序列(a₀,a₁,…,a,,…)=(1,1/2,…,1/(r+1),…)的指数生成函数。又由定义7知，,2.6生成函数的应用2.6.1生成函数法在求解递推关系中的应用利用生成函数求解各类递推关系有广泛的适用性，其基本步骤如下则所以f(n)=2n-2-(-2)n-2。 2.6.1.1用生成函数求解常系数线性齐次递推关系定理2设设q是Q(x)=0的k重根，则Q(x)=(x-q)*Q₁(x)(Q₁(q)≠0)。设P(x)与Q(x)互素，用待定系数法，设AQ₁(x)+(x-q)P₁(x)=P(x),将AQ₁(x)+(x-q)P₁(x)=P(x),得本科毕业论文第17页共28页可分项表示，因此，可分项表示。由和式得知表示是唯一的。设有常系数线性齐次递推关系f(n)=c₁f(n-1)+c₂f(n-2)+…+cxf(n-k)(ck≠0,n≥k),令则A(x)-f(0)-f(1)x-…-f(k-1)x*-1=c₁x[A(x)-f(0)-f(1)x-…f(k-2)xk-2]+c₂x²[A(x)-f(0)-f(1)x-…f(k-3)xk-3]+…+crx*·A(x)。整理后得 A(x)·(1-c₁x-c₂x²-…-crx*)=f(0)+[f(1)-c₁f(0)]x+…+[f(k-1)-c₁f(k-2)-…-cr-if(0)]xk-1,P(x)=f(0)+[f(1)-c₁f(0)]x+…+[f(k-1)-c₁f(k-2)-…-ck-if(0)]xk-1,Q(x)=(1-c₁x-c₂x²-…-由此可以看出，Q(x)由递推关系中的系数c₁,c₂,…,c完全确定，P(x)由系数f(n)=c₁f(n-1)+c₂f(n-2)+…+ckf(n-k)(cx≠0,n≥k)C(x)=xk-c₁xk-1-c₂xk-2-…-Ck-1x-Ck=0C(x)=xk-c₁xk-1-c₂xk-2-…-ck-1x-ck=0=(x-q₁)m₁(x-q₂)mt,而=(1-q₁x)m1(1-q₂x)m2…(1-q₁x)mt,Q(x)=(1-q₁x)M1(1-q₂x)m2…(1-qtx)mt, 是有理分式，且分子P(x)的次数低于分母Q(x)的次数，由定理2可得例13用生成函数求解下列递推关系解：令则将f(0)=0,f(1)=1,f(2)=2代入， 整理得所以2.6.1.2用生成函数求解常系数线性非齐次递推关系用生成函数可以找出常系数线性非齐次递推关系的特解结构，下面以f(n)=n⁵βnf(n)=c₁f(n-1)+c₂f(n-2)+…+cxf(n-k)+n⁸βn(ck≠0,n≥k)令f(n)=c₁f(n-1)+c₂f(n-2)+…+cxf(n-k)+n⁵β"(ck≠0,n≥k)得而通过比较等式两边i⁵,i⁵-1,…,i的系数和常数项，可以依次确定d,d₅-1,…,d₀、得例14求解递推关系解得利用求得作为生成函数应用的一个实例，下面我们讨论把n个无区别的球放在一些无区别的盒子中的问题把n个无区别的球分别放在一些无区别的盒子中，究竟有多少种方法呢?无区别的盒子意味着，如果有四个相同的球，则在第一个盒子中放入三个球，第二个盒子放入一个球和第一个盒子中放入一个球，第二个盒子中放入三个球的放法是一样的。一个整数的拆分是把整数分拆为若干个正整数部分，而这些部分的次序是无关紧要的。比如6=2+4和6=4+2被认为是同样的拆分法。显然整数n的一个拆分等价于把n个无区别的球分放在一些无区别的盒子中的一种方法。正整数n的拆分数记作P(n)。例如，对于正整数n=1,2,3,4的拆分是P(1)=1(1=1),P(2)=2(2=2,2=1+1),P(3)=3(3=3,3=2+1,3=1+1+1),P(4)=5(4=4,4=3+1,4=2+2,4=2+1+1,4=1+1+1+1),首先考虑恒等式 =(1+x+x²+x³+…)(1+x²+x⁴+x⁶+…)(1+x³+x⁶+x⁹+…)=1+x+2x²+3x³+4x⁴+5x⁵+7x从上式中可以看出xn的系数等于n拆分为1、2、3的和的方法数。例如x³的系数是3,这表示整数3拆分成1、2、3的和的方法数是3,即又例如x⁴的系数是4,它表明有4种方法将4拆分为1、2、3的和。即4=3+1,4=2+2,4=2+1+1,4=1+1+1+1在因子(1+x+x²+x³+…)中的1,x,x²,x³,…,分别表示数字1没有被选，选一个1,选二个1,选三个1,……;同样的，因子(1+x²+x⁴+x⁶+…)则表示2没有被选，或选一个2,或选二个2,或选三个2,……;因子(1+x³+x⁶+x⁹+…)则表示3没有被选，或选一个3,或选二个3,或选三个3,……。这样，上面三个因子的乘积的x"的系数就是n拆分为1、2、3的和定理3设a,b,c,…是大于0的正整数，则的级数展开式中的xn系数等于把正整数n拆分成a,b,c,…=(1+x⁴+x²a+…)(1+xb+x²b+…)(1+x“+x²c+…),如果xn是由x3a,xb,x2c,…的乘积所组成，则 (1+x+x²+x³+x⁴…)(1+x²+x⁴+x⁶+…)(1+x⁵+x10+…)=1+x+2x²+2x³+3x⁴+4x5+5x⁶+6x⁷+…,例如，邮费为6的方案数(拆分数)为5种1+1+1+1+1+1,1+1+1+1+2,1+1+2+2,1+5,2+2+2.又比如有1克的砝码3枚，2克的4枚，4克的2枚，能称出多少种重量呢?这属于有限重复分拆问题，所以(1+x+x²+x³)(1+x²+x⁴+x⁶+x⁸)(1+x⁴+x⁸)=1+x+2x²+2x³+3x⁴+3x⁵+4x⁶+4x⁷+5x⁸+5x⁹+5x10+5x¹1+4x12+4x13+3x14+3x15+2x16+2x17+x18+x19,根据上式可以看出共能称出19种重量，每种重量的方案数为各个xn的系数，例如称出本科毕业论文第26页共28页围，并通过简单的例子来说明。并阐述了生成函数法在递推关系和整数拆分中的应用。致谢我由衷地感谢!也祝愿老师能够在她的研究道路上能够取得更高的成就。本科毕业论文第28页共28页参考文献1田廷彦.组合几何.第1版.上海：上海科技教育出版社，20102南基洙.组合数学.第1版.北京：高等教育出版社，20083冯舜玺，罗平等.组合数学.第3版.北京：机械工业出版社，20024李乔.组合学讲义.第2版.北京：高等教育出版社，20085柯召，魏万迪.组合论(上册).第1版.北京：科学出版社，20106卢开澄，卢华明.组合数学.第3版.北京：清华大学出