生成函數(shù)理論及應(yīng)用論文

1引言組合數(shù)學(CombinatorialMathematics),又稱為離散數(shù)學。狹義的組合數(shù)學主要研究滿足一定條件的組態(tài)(也稱組合模型)的存在、計數(shù)以及構(gòu)造等方面問題。組合數(shù)學等領(lǐng)域中都有著廣泛的應(yīng)用價值，特別是在計算機科學中有著重要的應(yīng)用。計數(shù)技術(shù)、排列組合、Polya計數(shù)法、二項式系數(shù)、容斥原理、生2生成函數(shù)數(shù)有普通型生成函數(shù)和指數(shù)型生成函數(shù)兩種，其中普通型用的比較多，并被廣泛應(yīng)用。 2.1生成函數(shù)的基本概念x1x1x?x2x?。(1+x)3(1+x+x2)2=(x?+x1)(x?+x1)(x?+x1)×(x?+x1+x2)(x?+x1+x2)然數(shù)),它的生成函數(shù)就是f(x)=1+x+x2+x3+x?+…(每一項都是1,即使n=0是1,4,6,4,1,0,0,0,(從4個x3)(x2)3+(1+x+x2)(x2)?+(1+x)(x2)?+(x2)?=x2+x3+2x?+2x?+3x?+2.2生成函數(shù)的性質(zhì) 性質(zhì)1例1已知性質(zhì)2若bk=ak+l:則 例2已知則則性質(zhì)3若證明：由假設(shè)條件，有b?=a?:b?x=a?x+a?x:b?x2=a?x2+a?x2+a?x2,bx=a?x?+a?x*+a?x*+…+akx*,把以上各式的兩邊分別相加，得B(x)=a?(1+x+x2+…)+a?x(1+x+x2+…)+a?x2(1+x+x2+…)+…例3已知性質(zhì)4若則b?=a?+a?+a?+…=A(1),b?x=a?x+a?x+…=[A(1)-a?]x,b?x2=a?x2+a?x3+…=[A(1)-a?-a?]x2,bkx*=axx*+ak+ixk+1+…=[A(1)-ao-a?-…-ak-1]x*,B(x)=A(1)+[A(1)-a?]x+[A(1)-ao-a?]x2+…=A(1)(1+x+x2+…)-anx(1+x+x2+…)-a?x2(1+x+x2+…) 則則=x·B(x),Ck=aak+βb,則 性質(zhì)8若則=a?(b?+b?x+b?x2+…)+a?x(b?+b?x+b?x2+…)+a?x2(b?+b?x+b?x2+…)+…=(a?+a?x+a?x2)(b?+b?x+b?x2+…)=A(x)·B(x)。則 例6求序列{5,6,7,…,n+5,…}A(x)=5+6x+7x2+…+(n+5)x"=5(1+x+x2+…)+(x+2x2+3x3+…)=5G{1}+G{k}2.3普通型生成函數(shù)O≤k?≤5,0≤k?≤4,0≤k?≤3。(1+x+x2+x3),(1+x+x2+x3+x?),(1+x+x2+x3+x?+x?)2.4指數(shù)型生成函數(shù)若α=1,則序列(1,1,…,1)的指數(shù)生成函數(shù)e*。故 例10五個數(shù)字1,1,2,2,3能組成多少個四位數(shù)?2.5生成函數(shù)的基本運算C;=a;+b?(i=0,1,2,…,r,…)。設(shè)A(x)是序列(a?,a?,…,a,,…)的普通生成函數(shù)，則A(x)/(1-x)故是序列(1,1,…,1,…)的普通生成函數(shù)。令和是序列 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相比較，可見有;數(shù)。由于是序列(a?,a?,…,a,,…)=(1,1/2,…,1/(r+1),…)的指數(shù)生成函數(shù)。又由定義7知，,2.6生成函數(shù)的應(yīng)用2.6.1生成函數(shù)法在求解遞推關(guān)系中的應(yīng)用利用生成函數(shù)求解各類遞推關(guān)系有廣泛的適用性，其基本步驟如下則所以f(n)=2n-2-(-2)n-2。 2.6.1.1用生成函數(shù)求解常系數(shù)線性齊次遞推關(guān)系定理2設(shè)設(shè)q是Q(x)=0的k重根，則Q(x)=(x-q)*Q?(x)(Q?(q)≠0)。設(shè)P(x)與Q(x)互素，用待定系數(shù)法，設(shè)AQ?(x)+(x-q)P?(x)=P(x),將AQ?(x)+(x-q)P?(x)=P(x),得本科畢業(yè)論文第17頁共28頁可分項表示，因此，可分項表示。由和式得知表示是唯一的。設(shè)有常系數(shù)線性齊次遞推關(guān)系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?x2[A(x)-f(0)-f(1)x-…f(k-3)xk-3]+…+crx*·A(x)。整理后得 A(x)·(1-c?x-c?x2-…-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?x2-…-由此可以看出，Q(x)由遞推關(guān)系中的系數(shù)c?,c?,…,c完全確定，P(x)由系數(shù)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)的次數(shù)低于分母Q(x)的次數(shù)，由定理2可得例13用生成函數(shù)求解下列遞推關(guān)系解：令則將f(0)=0,f(1)=1,f(2)=2代入， 整理得所以2.6.1.2用生成函數(shù)求解常系數(shù)線性非齊次遞推關(guān)系用生成函數(shù)可以找出常系數(shù)線性非齊次遞推關(guān)系的特解結(jié)構(gòu)，下面以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的系數(shù)和常數(shù)項，可以依次確定d,d?-1,…,d?、得例14求解遞推關(guān)系解得利用求得作為生成函數(shù)應(yīng)用的一個實例，下面我們討論把n個無區(qū)別的球放在一些無區(qū)別的盒子中的問題把n個無區(qū)別的球分別放在一些無區(qū)別的盒子中，究竟有多少種方法呢?無區(qū)別的盒子意味著，如果有四個相同的球，則在第一個盒子中放入三個球，第二個盒子放入一個球和第一個盒子中放入一個球，第二個盒子中放入三個球的放法是一樣的。一個整數(shù)的拆分是把整數(shù)分拆為若干個正整數(shù)部分，而這些部分的次序是無關(guān)緊要的。比如6=2+4和6=4+2被認為是同樣的拆分法。顯然整數(shù)n的一個拆分等價于把n個無區(qū)別的球分放在一些無區(qū)別的盒子中的一種方法。正整數(shù)n的拆分數(shù)記作P(n)。例如，對于正整數(shù)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+x2+x3+…)(1+x2+x?+x?+…)(1+x3+x?+x?+…)=1+x+2x2+3x3+4x?+5x?+7x從上式中可以看出xn的系數(shù)等于n拆分為1、2、3的和的方法數(shù)。例如x3的系數(shù)是3,這表示整數(shù)3拆分成1、2、3的和的方法數(shù)是3,即又例如x?的系數(shù)是4,它表明有4種方法將4拆分為1、2、3的和。即4=3+1,4=2+2,4=2+1+1,4=1+1+1+1在因子(1+x+x2+x3+…)中的1,x,x2,x3,…,分別表示數(shù)字1沒有被選，選一個1,選二個1,選三個1,……;同樣的，因子(1+x2+x?+x?+…)則表示2沒有被選，或選一個2,或選二個2,或選三個2,……;因子(1+x3+x?+x?+…)則表示3沒有被選，或選一個3,或選二個3,或選三個3,……。這樣，上面三個因子的乘積的x"的系數(shù)就是n拆分為1、2、3的和定理3設(shè)a,b,c,…是大于0的正整數(shù)，則的級數(shù)展開式中的xn系數(shù)等于把正整數(shù)n拆分成a,b,c,…=(1+x?+x2a+…)(1+xb+x2b+…)(1+x“+x2c+…),如果xn是由x3a,xb,x2c,…的乘積所組成，則 (1+x+x2+x3+x?…)(1+x2+x?+x?+…)(1+x?+x10+…)=1+x+2x2+2x3+3x?+4x5+5x?+6x?+…,例如，郵費為6的方案數(shù)(拆分數(shù))為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+x2+x3)(1+x2+x?+x?+x?)(1+x?+x?)=1+x+2x2+2x3+3x?+3x?+4x?+4x?+5x?+5x?+5x10+5x11+4x12+4x13+3x14+3x15+2x16+2x17+x18+x19,根據(jù)上式可以看出共能稱出19種重量，每種重量的方案數(shù)為各個xn的系數(shù)，例如稱出本科畢業(yè)論文第26頁共28頁圍，并通過簡單的例子來說明。并闡述了生成函數(shù)法在遞推關(guān)系和整數(shù)拆分中的應(yīng)用。致謝我由衷地感謝!也祝愿老師能夠在她的研究道路上能夠取得更高的成就。本科畢業(yè)論文第28頁共28頁參考文獻1田廷彥.組合幾何.第1版.上海：上?？萍冀逃霭嫔?，20102南基洙.組合數(shù)學.第1版.北京：高等教育出版社，20083馮舜璽，羅平等.組合數(shù)學.第3版.北京：機械工業(yè)出版社，20024李喬.組合學講義.第2版.北京：高等教育出版社，20085柯召，魏萬迪.組合論(上冊).第1版.北京：科學出版社，20106盧開澄，盧華明.組合數(shù)學.第3版.北京：清華大學出