1摘要線性齊次遞推關(guān)系生成函數(shù)遞歸和生成函數(shù)一個(gè)幾何的例子指數(shù)生成函數(shù)作業(yè)1摘要線性齊次遞推關(guān)系2線性齊次遞推關(guān)系2線性齊次遞推關(guān)系3線性遞推關(guān)系令h0,h1,…,hn,…是一個(gè)數(shù)列，如果存在量a1,a2,…,ak,ak≠0,和量bn(每一個(gè)量a1,a2,…,ak,

bn可能依賴于n)，使得hn=a1hn-1+a2hn-2+…+akhn-k+bn,(n≥k).則稱該序列滿足k階線性遞推關(guān)系.3線性遞推關(guān)系令h0,h1,…,hn,…是一個(gè)數(shù)列4例子錯(cuò)位排列數(shù)列D0,D1,D2,…,Dn滿足兩個(gè)遞推關(guān)系Dn=(n-1)Dn-1+(n-1)Dn-2,(n≥2)Dn=nDn-1+(-1)n,(n≥1).第一個(gè)遞推關(guān)系的階是多少且a1，a2，bn等于多少。第二個(gè)遞推關(guān)系的……..4例子錯(cuò)位排列數(shù)列D0,D1,D2,…,Dn滿足5齊次的

如果bn=0，則線性遞推關(guān)系hn=a1hn-1+a2hn-2+…+akhn-k+bn,(n≥k)稱為齊次的.如果a1,a2,…,ak是常數(shù),則稱線性遞推關(guān)系式具有常系數(shù).5齊次的如果bn=0，則線性遞推關(guān)系6定理7.2.1令q為一個(gè)非零數(shù).則hn=qn

是常系數(shù)線性遞推關(guān)系hn–a1hn-1–a2hn-2–…–akhn-k=0,(ak≠0,n≥k)(7.20)

的解，當(dāng)且僅當(dāng)q是多項(xiàng)式

xk–a1xk-1–a2xk-2–…–ak=0.

(7.21) 的一個(gè)根。如果多項(xiàng)式方程有k個(gè)不同的根q1,q2,…,qk,則

hn=c1q1n+c2q2n+…+ckqkn

(7.22)

是下述意義下式(7.20)的一般解:無論給定h0,h1,…,什么初始值，都存在常數(shù)c1,c2,…,ck使得式(7.22)是滿足遞推關(guān)系(7.20)和初始條件的唯一的序列.

6定理7.2.1令q為一個(gè)非零數(shù).則hn=qn7注解

多項(xiàng)式方程(7.21)叫做遞推關(guān)系(7.20)的特征方程，而它的k個(gè)根叫做特征根.

如果特征根互異,那么式(7.22)就是式(7.20)的一般解.7注解多項(xiàng)式方程(7.21)叫做遞推關(guān)系(7.208例題求解滿足h0=1,h1=2andh2=0的遞推關(guān)系hn=2hn-1+hn-2–2hn-3,(n≥3).提示:這個(gè)遞推關(guān)系的特征方程為 x3–2x2–x+2=0 而它的三個(gè)根1,-1,2.根據(jù)定理7.2.1, hn=c11n+c2(-1)n+c32n是一般解.8例題求解滿足h0=1,h1=2andh2=9例題（續(xù)）由三個(gè)字母a,b,c組成的長度為n的一些單詞將在通信信道上傳輸，滿足條件：傳輸中不得有兩個(gè)a連續(xù)出現(xiàn)在任一個(gè)單詞中。確定通信信道允許傳輸?shù)膯卧~個(gè)數(shù)。9例題（續(xù)）由三個(gè)字母a,b,c組成的長度為n的一些單詞10提示首先,找到特征關(guān)系式并且求出它的解.令hn表示允許傳輸?shù)拈L度為n的單詞的個(gè)數(shù).我們有h0=1和h1=3.令n≥2.如果第一個(gè)字母是b或者c,那么這個(gè)單詞就可以有hn-1種方法構(gòu)成.如果第一個(gè)字母是a,那么第二個(gè)字母是b或者c.這樣,hn=2hn-1+2hn-2,(n≥2).bab10提示首先,找到特征關(guān)系式并且求出它的解.bab11練習(xí)

一個(gè)1＊n棋盤.我們把每個(gè)方格都涂上紅色或者藍(lán)色.令hn表示沒有兩個(gè)連續(xù)的方格被同時(shí)涂上紅色的方法的個(gè)數(shù).找到并且證明這樣的一個(gè)遞推關(guān)系hn.然后求得公式hn.求解遞推關(guān)系hn=4hn-1–4hn-2,(n≥2).11練習(xí)一個(gè)1＊n棋盤.我們把每個(gè)方格都涂上紅色或者12注解

如果特征方程的根q1,q2,…,qk不是互異的,那么hn=c1q1n+c2q2n+…+ckqkn就不是遞推關(guān)系的一個(gè)一般解.12注解如果特征方程的根q1,q2,…,qk不是13定理7.2.2令q1,q2,…,qt為常系數(shù)線性齊次遞推關(guān)系(7.20)的特征方程的互異的根.此時(shí)，如果qi是si重根,則該遞推關(guān)系對qi的部分一般解為 Hn(i)=c1qin+c2nqin+…+csinsi-1qin=(c1+c2n+…+csinsi-1)qin

遞推關(guān)系的一般解則是 hn=Hn(1)+Hn

(2)+…+Hn(t).13定理7.2.2令q1,q2,…,qt為常14例題求遞推關(guān)系hn=4hn-1–4hn-2,(n≥2).提示:特征方程是x2-4x+4=0.這樣2是２重特征根.特征關(guān)系的一般解為hn=c12n+c2n2n.14例題求遞推關(guān)系15練習(xí)

求特征關(guān)系hn=-hn-1+3hn-2+5hn-3+2hn-4,(n≥4).15練習(xí)求特征關(guān)系16生成函數(shù)16生成函數(shù)17生成函數(shù)的方法利用代數(shù)的方法計(jì)算一個(gè)問題可能性的次數(shù)生成函數(shù)是無窮次可微函數(shù)的泰勒級(jí)數(shù)如果你可以找到一個(gè)函數(shù)和它的泰勒級(jí)數(shù),那么泰勒級(jí)數(shù)的系數(shù)則給出這個(gè)問題的解.17生成函數(shù)的方法利用代數(shù)的方法計(jì)算一個(gè)問題可能性的次數(shù)18生成函數(shù)的定義令h0,h1,…,hn,……是一個(gè)無窮的數(shù)列.它的生成函數(shù)被定義為無窮級(jí)數(shù)g(x)=h0+h1x+h2x2+…+hnxn+……在g(x)中，xn的系數(shù)是這個(gè)序列的第n項(xiàng)hn,從而，xn作為hn的“位置持有者”。18生成函數(shù)的定義令h0,h1,…,hn,……是19例題1.無限序列的生成函數(shù)1,1,1,…,1,…,它的每一項(xiàng)都等于1g(x)=1+x+x2+…+xn+…=1/(1-x)2.M是一個(gè)正整數(shù).二項(xiàng)式序列c(m,0),c(m,1)c(m,2),….,c(m,m)的生成函數(shù)是gm(x)=c(m,0)+c(m,1)x+c(m,2)x2+…+c(m,m)xm=(1+x)m(二項(xiàng)式定理).19例題1.無限序列的生成函數(shù)1,1,1,…,120練習(xí)令a為一個(gè)實(shí)數(shù).根據(jù)牛頓二項(xiàng)式定理,二項(xiàng)式系數(shù)c(a,0),c(a,1),…c(a,n),…的無窮生成函數(shù)是什么？令k是一個(gè)整數(shù)，并令序列h0,h1,h2,…,hn,…使得hn等于e1+e2+…ek=n的非負(fù)整數(shù)的個(gè)數(shù).這個(gè)序列的生成函數(shù)是什么?20練習(xí)令a為一個(gè)實(shí)數(shù).根據(jù)牛頓二項(xiàng)式定理,二項(xiàng)式系數(shù)21復(fù)習(xí)令a是一個(gè)實(shí)數(shù).那么對于所有的x

和y

（0≤|x|<|y|）,

21復(fù)習(xí)令a是一個(gè)實(shí)數(shù).那么對于所有的x和y（22又因?yàn)閨y|<1令 22又因?yàn)閨y|<1令 23例題（續(xù)）(1+x+x2+x3+x4+x5)(1+x+x2)(1+x+x2+x3+x4)是什么樣序列的生成函數(shù)?令xe1(0≤e1≤5),xe2,(0≤e2≤2),xe3(0≤e3≤4)分別表示第一因子，第二因子和第三因子中的典型項(xiàng)。假設(shè)e1+e2+e3=n.相乘后得到xe1xe2xe3=xn,因此，乘積中xn的系數(shù)是e1+e2+e3=n的整數(shù)解的個(gè)數(shù)hn，其中0≤e1≤5,0≤e2≤2以及0≤e3≤4.(注意hn=0如果n>11)23例題（續(xù)）(1+x+x2+x3+x4+x5)(1+x+x24例題（續(xù)）確定蘋果、香蕉、橘子和梨的n-組合的個(gè)數(shù),其中在每個(gè)n-組合中蘋果的個(gè)數(shù)是偶數(shù)，香蕉的個(gè)數(shù)是奇數(shù)，橘子的個(gè)數(shù)在0和4之間，而且至少要有一個(gè)梨提示:該問題等價(jià)于找出e1+e2+e3+e4=n.的非負(fù)整數(shù)解的個(gè)數(shù)24例題（續(xù)）確定蘋果、香蕉、橘子和梨的n-組合的個(gè)數(shù),其25

其中e1是偶數(shù)(e1為蘋果數(shù)),e2是奇數(shù),0≤e3≤4,而e4≥1.我們?yōu)槊糠N類型的水果建立一個(gè)因子，其中的指數(shù)為那種類型水果的n-組合中所允許的數(shù):g(x)=(1+x2+x4+…)(x+x3+x5+…)(1+x+x2+x3+x4)(x+x2+x3+x4+…)

2526練習(xí)

令hn代表好幾袋子蘋果、香蕉、橘子和梨的總個(gè)數(shù),并且每個(gè)袋子中蘋果的個(gè)數(shù)是偶數(shù),香蕉的隔數(shù)是5的倍數(shù),橘子的個(gè)數(shù)至多為4并且梨的個(gè)數(shù)為0或者1.提示:計(jì)算這個(gè)問題的生成函數(shù)的xn的系數(shù).26練習(xí)令hn代表好幾袋子蘋果、香蕉、橘子和梨的總個(gè)27練習(xí)（續(xù)）確定方程e1+e2+…+ek=n非負(fù)整數(shù)解e1,

e2,…,ek的個(gè)數(shù)hn的生成函數(shù)。提示:∏k(x+x3+x5+x7+……).27練習(xí)（續(xù)）確定方程e1+e2+…+ek28練習(xí)(續(xù))令hn表示方程3e1+4e2+2e3+5e4=n非負(fù)整數(shù)解的個(gè)數(shù).找到h0,h1,h2,…,hn,…….的生成函數(shù)g(x)提示:令f1=3e1,f2=4e2,f3=2e3并且f4=5e4.于是hn也等于f1+f2+f3+f4=n的非負(fù)整數(shù)解的個(gè)數(shù)，其中f1是3的倍數(shù),f2是4的倍數(shù),f3是偶數(shù)并且f4是5的倍數(shù).28練習(xí)(續(xù))令hn表示方程3e1+4e229遞歸生成函數(shù)29遞歸生成函數(shù)30內(nèi)容利用生成函數(shù)來求解常系數(shù)的線性齊次遞推關(guān)系.牛頓二項(xiàng)定理的應(yīng)用.30內(nèi)容利用生成函數(shù)來求解常系數(shù)的線性齊次遞推關(guān)系.31復(fù)習(xí):牛頓二項(xiàng)定理如果n是一個(gè)正整數(shù)并且r是一個(gè)非零整數(shù),那么31復(fù)習(xí):牛頓二項(xiàng)定理如果n是一個(gè)正整數(shù)并且r是一32例題確定平方項(xiàng)的序列0,1,4,…,n2,…..的生成函數(shù)解答:把n=2、r=1帶入上面的牛頓二項(xiàng)式,(1-x)-2=1+2x+3x2+…+nxn-1+….因此x/(1-x)2=x+2x2+3x3+…+nxn+…..微分,我們得到（1+x)/(1-x)3=1+22x+32x2+…+n2xn-1+…..乘x,得到x(1+x)/(1-x)3.32例題確定平方項(xiàng)的序列0,1,4,…,n2,….33例題(續(xù))求解滿足初始值h0=1和h1=-2的遞推關(guān)系hn=5hn-1–6hn-2,(n≥2).提示:令g(x)=h0+h1x+h2x2+…+hnxn+….為h0,h1,h2,…,hn…的生成函數(shù)。此時(shí)，我們有下列方程33例題(續(xù))求解滿足初始值h0=1和h1=34g(x)=h0+h1x+h2x2+…+hnxn+….-5xg(x)=-5h0x

-5h1x2-5h2x3-…-5hn-1xn-….6x2g(x)=6h0x2

+6h1x3+6h2x4+…+6hn-2xn+….將三個(gè)方程相加,得到(1-5x+6x2)g(x)=h0+(h1-5h0)x+(h2-5h1+6h0)x2+…+(hn-5hn-1+6hn-2)xn+….=h0+(h1-5h0)x=1-7x因此,g(x)=(1-7x)/(1-5x+6x2)=5/(1-2x)–4/(1-3x)34g(x)=h0+h1x+h2x2+…+hnxn+….35通過牛頓二項(xiàng)定理(1-2x)-1=1+2x+22x2+…+2nxn…..(1-3x)-1=1+3x+32x2+…+3nxn…..于是,g(x)=1+(-2)x+(-15)x2+…+(5×2n–4×3n)xn+…可以得到hn=5×2n–4×3n(n=0,1,2,…).35通過牛頓二項(xiàng)定理36練習(xí)滿足h0=0,h1=1，h2=-1的遞推關(guān)系hn+hn-1–16hn-2+20hn-3=0(n≥3)求hn的一般公式。36練習(xí)滿足h0=0,h1=1，h2=-137一個(gè)幾何的例子37一個(gè)幾何的例子38劃分凸多邊形的方法通過畫出在區(qū)域內(nèi)部不相交的對角線將具有n+1條邊的凸多邊形區(qū)域分成三角形區(qū)域，令hn表示分成三角形區(qū)域的方法數(shù)。定義h1=1.則hn滿足遞推關(guān)系hn=h1hn-1+h2hn-2+…+hn-1h1,(n≥2).該遞推關(guān)系的解為hn=n-1C(2n-2,n-1),(n=1,2,3,…).38劃分凸多邊形的方法通過畫出在區(qū)域內(nèi)部不相交的對角線將具有39指數(shù)生成函數(shù)39指數(shù)生成函數(shù)40復(fù)習(xí):ex的泰勒級(jí)數(shù)40復(fù)習(xí):ex的泰勒級(jí)數(shù)41指數(shù)生成函數(shù)的定義

序列h0,h1,h2,…,hn,…的指數(shù)生成函數(shù)41指數(shù)生成函數(shù)的定義序列h0,h1,h2,…,42例子

令n為一正整數(shù).確定數(shù)列P(n,0),P(n,1),P(n,2),…,P(n,n),的指數(shù)生成函數(shù),其中P(n,k)表示n-元素集的k-排列的個(gè)數(shù),對于k=0,1,…,n其值為n!/(n-k)!.指數(shù)生成函數(shù)為42例子令n為一正整數(shù).確定數(shù)列P(n,0),P(n,43因此,(1+x)n既是序列P(n,0),P(n,1),P(n,2),…,P(n,n)的指數(shù)生成函數(shù)又是序列C(n,0),C(n,1),C(n,2),…,C(n,n)的常規(guī)生成函數(shù).4344練習(xí)(續(xù))序列1,1,1,…,1,….的指數(shù)生成函數(shù)是更一般的,如果a是一個(gè)實(shí)數(shù),那么序列a0=1,a,a2,…,an,….的指數(shù)生成函數(shù)是44練習(xí)(續(xù))序列1,1,1,…,1,….的指45定理令S為多重集{n1.a1,n2.a2,…,nk.ak},其中n1,n2,…,nk均為非負(fù)整數(shù).令hn是S的n-排列數(shù).則序列h0,h1,h2,…,hn,…的指數(shù)生成函數(shù)g(e)(x)由g(e)(x)=fn1(x)fn2(x)….fnk(x)給定其中,對于i=1,2,…,k,fni(x)=1+x+x2/2!+…+xni/ni!.45定理令S為多重集{n1.a1,n2.a2,…,nk46例題如果把一個(gè)1*n的棋盤上的偶數(shù)個(gè)方格染成紅,白,藍(lán)三種顏色,共有多少種染色方案?線索:令hn表示這樣的染色方案數(shù),定義h0=1.

此時(shí)hn等于三種顏色的多重集的n-排列數(shù),其中每一種顏色都有無窮重復(fù)數(shù),且紅色出現(xiàn)偶數(shù)次.因此,h0,h1,h2,…h(huán)n,…的指數(shù)生成函數(shù)是紅,白,藍(lán)因子的乘積:46例題如果把一個(gè)1*n的棋盤上的偶數(shù)個(gè)方格染成紅,白,藍(lán)三47因此,hn=(3n+1)/2.4748練習(xí)確定每個(gè)數(shù)字都是奇數(shù)的n位數(shù)的個(gè)數(shù),其中要求1和3出現(xiàn)偶數(shù)次.線索:令h0=1.hn等于多重集S={∞1,∞3,∞5,∞7,∞9}的n-排列的個(gè)數(shù),其中要求1和3出現(xiàn)偶數(shù)次.48練習(xí)確定每個(gè)數(shù)字都是奇數(shù)的n位數(shù)的個(gè)數(shù),其中要求1和3出49練習(xí)(續(xù))用紅,白,藍(lán)三種顏色給一個(gè)1*n的棋盤染色,如果有偶數(shù)方格必須染成紅色,并且至少有一個(gè)藍(lán)色的,求一共有多少種染色方案?49練習(xí)(續(xù))用紅,白,藍(lán)三種顏色給一個(gè)1*n的棋盤染色,50摘要線性齊次遞推關(guān)系生成函數(shù)遞歸和生成函數(shù)一個(gè)幾何的例子指數(shù)生成函數(shù)作業(yè)1摘要線性齊次遞推關(guān)系51線性齊次遞推關(guān)系2線性齊次遞推關(guān)系52線性遞推關(guān)系令h0,h1,…,hn,…是一個(gè)數(shù)列，如果存在量a1,a2,…,ak,ak≠0,和量bn(每一個(gè)量a1,a2,…,ak,

bn可能依賴于n)，使得hn=a1hn-1+a2hn-2+…+akhn-k+bn,(n≥k).則稱該序列滿足k階線性遞推關(guān)系.3線性遞推關(guān)系令h0,h1,…,hn,…是一個(gè)數(shù)列53例子錯(cuò)位排列數(shù)列D0,D1,D2,…,Dn滿足兩個(gè)遞推關(guān)系Dn=(n-1)Dn-1+(n-1)Dn-2,(n≥2)Dn=nDn-1+(-1)n,(n≥1).第一個(gè)遞推關(guān)系的階是多少且a1，a2，bn等于多少。第二個(gè)遞推關(guān)系的……..4例子錯(cuò)位排列數(shù)列D0,D1,D2,…,Dn滿足54齊次的

如果bn=0，則線性遞推關(guān)系hn=a1hn-1+a2hn-2+…+akhn-k+bn,(n≥k)稱為齊次的.如果a1,a2,…,ak是常數(shù),則稱線性遞推關(guān)系式具有常系數(shù).5齊次的如果bn=0，則線性遞推關(guān)系55定理7.2.1令q為一個(gè)非零數(shù).則hn=qn

是常系數(shù)線性遞推關(guān)系hn–a1hn-1–a2hn-2–…–akhn-k=0,(ak≠0,n≥k)(7.20)

的解，當(dāng)且僅當(dāng)q是多項(xiàng)式

xk–a1xk-1–a2xk-2–…–ak=0.

(7.21) 的一個(gè)根。如果多項(xiàng)式方程有k個(gè)不同的根q1,q2,…,qk,則

hn=c1q1n+c2q2n+…+ckqkn

(7.22)

是下述意義下式(7.20)的一般解:無論給定h0,h1,…,什么初始值，都存在常數(shù)c1,c2,…,ck使得式(7.22)是滿足遞推關(guān)系(7.20)和初始條件的唯一的序列.

6定理7.2.1令q為一個(gè)非零數(shù).則hn=qn56注解

多項(xiàng)式方程(7.21)叫做遞推關(guān)系(7.20)的特征方程，而它的k個(gè)根叫做特征根.

如果特征根互異,那么式(7.22)就是式(7.20)的一般解.7注解多項(xiàng)式方程(7.21)叫做遞推關(guān)系(7.2057例題求解滿足h0=1,h1=2andh2=0的遞推關(guān)系hn=2hn-1+hn-2–2hn-3,(n≥3).提示:這個(gè)遞推關(guān)系的特征方程為 x3–2x2–x+2=0 而它的三個(gè)根1,-1,2.根據(jù)定理7.2.1, hn=c11n+c2(-1)n+c32n是一般解.8例題求解滿足h0=1,h1=2andh2=58例題（續(xù)）由三個(gè)字母a,b,c組成的長度為n的一些單詞將在通信信道上傳輸，滿足條件：傳輸中不得有兩個(gè)a連續(xù)出現(xiàn)在任一個(gè)單詞中。確定通信信道允許傳輸?shù)膯卧~個(gè)數(shù)。9例題（續(xù)）由三個(gè)字母a,b,c組成的長度為n的一些單詞59提示首先,找到特征關(guān)系式并且求出它的解.令hn表示允許傳輸?shù)拈L度為n的單詞的個(gè)數(shù).我們有h0=1和h1=3.令n≥2.如果第一個(gè)字母是b或者c,那么這個(gè)單詞就可以有hn-1種方法構(gòu)成.如果第一個(gè)字母是a,那么第二個(gè)字母是b或者c.這樣,hn=2hn-1+2hn-2,(n≥2).bab10提示首先,找到特征關(guān)系式并且求出它的解.bab60練習(xí)

一個(gè)1＊n棋盤.我們把每個(gè)方格都涂上紅色或者藍(lán)色.令hn表示沒有兩個(gè)連續(xù)的方格被同時(shí)涂上紅色的方法的個(gè)數(shù).找到并且證明這樣的一個(gè)遞推關(guān)系hn.然后求得公式hn.求解遞推關(guān)系hn=4hn-1–4hn-2,(n≥2).11練習(xí)一個(gè)1＊n棋盤.我們把每個(gè)方格都涂上紅色或者61注解

如果特征方程的根q1,q2,…,qk不是互異的,那么hn=c1q1n+c2q2n+…+ckqkn就不是遞推關(guān)系的一個(gè)一般解.12注解如果特征方程的根q1,q2,…,qk不是62定理7.2.2令q1,q2,…,qt為常系數(shù)線性齊次遞推關(guān)系(7.20)的特征方程的互異的根.此時(shí)，如果qi是si重根,則該遞推關(guān)系對qi的部分一般解為 Hn(i)=c1qin+c2nqin+…+csinsi-1qin=(c1+c2n+…+csinsi-1)qin

遞推關(guān)系的一般解則是 hn=Hn(1)+Hn

(2)+…+Hn(t).13定理7.2.2令q1,q2,…,qt為常63例題求遞推關(guān)系hn=4hn-1–4hn-2,(n≥2).提示:特征方程是x2-4x+4=0.這樣2是２重特征根.特征關(guān)系的一般解為hn=c12n+c2n2n.14例題求遞推關(guān)系64練習(xí)

求特征關(guān)系hn=-hn-1+3hn-2+5hn-3+2hn-4,(n≥4).15練習(xí)求特征關(guān)系65生成函數(shù)16生成函數(shù)66生成函數(shù)的方法利用代數(shù)的方法計(jì)算一個(gè)問題可能性的次數(shù)生成函數(shù)是無窮次可微函數(shù)的泰勒級(jí)數(shù)如果你可以找到一個(gè)函數(shù)和它的泰勒級(jí)數(shù),那么泰勒級(jí)數(shù)的系數(shù)則給出這個(gè)問題的解.17生成函數(shù)的方法利用代數(shù)的方法計(jì)算一個(gè)問題可能性的次數(shù)67生成函數(shù)的定義令h0,h1,…,hn,……是一個(gè)無窮的數(shù)列.它的生成函數(shù)被定義為無窮級(jí)數(shù)g(x)=h0+h1x+h2x2+…+hnxn+……在g(x)中，xn的系數(shù)是這個(gè)序列的第n項(xiàng)hn,從而，xn作為hn的“位置持有者”。18生成函數(shù)的定義令h0,h1,…,hn,……是68例題1.無限序列的生成函數(shù)1,1,1,…,1,…,它的每一項(xiàng)都等于1g(x)=1+x+x2+…+xn+…=1/(1-x)2.M是一個(gè)正整數(shù).二項(xiàng)式序列c(m,0),c(m,1)c(m,2),….,c(m,m)的生成函數(shù)是gm(x)=c(m,0)+c(m,1)x+c(m,2)x2+…+c(m,m)xm=(1+x)m(二項(xiàng)式定理).19例題1.無限序列的生成函數(shù)1,1,1,…,169練習(xí)令a為一個(gè)實(shí)數(shù).根據(jù)牛頓二項(xiàng)式定理,二項(xiàng)式系數(shù)c(a,0),c(a,1),…c(a,n),…的無窮生成函數(shù)是什么？令k是一個(gè)整數(shù)，并令序列h0,h1,h2,…,hn,…使得hn等于e1+e2+…ek=n的非負(fù)整數(shù)的個(gè)數(shù).這個(gè)序列的生成函數(shù)是什么?20練習(xí)令a為一個(gè)實(shí)數(shù).根據(jù)牛頓二項(xiàng)式定理,二項(xiàng)式系數(shù)70復(fù)習(xí)令a是一個(gè)實(shí)數(shù).那么對于所有的x

和y

（0≤|x|<|y|）,

21復(fù)習(xí)令a是一個(gè)實(shí)數(shù).那么對于所有的x和y（71又因?yàn)閨y|<1令 22又因?yàn)閨y|<1令 72例題（續(xù)）(1+x+x2+x3+x4+x5)(1+x+x2)(1+x+x2+x3+x4)是什么樣序列的生成函數(shù)?令xe1(0≤e1≤5),xe2,(0≤e2≤2),xe3(0≤e3≤4)分別表示第一因子，第二因子和第三因子中的典型項(xiàng)。假設(shè)e1+e2+e3=n.相乘后得到xe1xe2xe3=xn,因此，乘積中xn的系數(shù)是e1+e2+e3=n的整數(shù)解的個(gè)數(shù)hn，其中0≤e1≤5,0≤e2≤2以及0≤e3≤4.(注意hn=0如果n>11)23例題（續(xù)）(1+x+x2+x3+x4+x5)(1+x+x73例題（續(xù)）確定蘋果、香蕉、橘子和梨的n-組合的個(gè)數(shù),其中在每個(gè)n-組合中蘋果的個(gè)數(shù)是偶數(shù)，香蕉的個(gè)數(shù)是奇數(shù)，橘子的個(gè)數(shù)在0和4之間，而且至少要有一個(gè)梨提示:該問題等價(jià)于找出e1+e2+e3+e4=n.的非負(fù)整數(shù)解的個(gè)數(shù)24例題（續(xù)）確定蘋果、香蕉、橘子和梨的n-組合的個(gè)數(shù),其74

其中e1是偶數(shù)(e1為蘋果數(shù)),e2是奇數(shù),0≤e3≤4,而e4≥1.我們?yōu)槊糠N類型的水果建立一個(gè)因子，其中的指數(shù)為那種類型水果的n-組合中所允許的數(shù):g(x)=(1+x2+x4+…)(x+x3+x5+…)(1+x+x2+x3+x4)(x+x2+x3+x4+…)

2575練習(xí)

令hn代表好幾袋子蘋果、香蕉、橘子和梨的總個(gè)數(shù),并且每個(gè)袋子中蘋果的個(gè)數(shù)是偶數(shù),香蕉的隔數(shù)是5的倍數(shù),橘子的個(gè)數(shù)至多為4并且梨的個(gè)數(shù)為0或者1.提示:計(jì)算這個(gè)問題的生成函數(shù)的xn的系數(shù).26練習(xí)令hn代表好幾袋子蘋果、香蕉、橘子和梨的總個(gè)76練習(xí)（續(xù)）確定方程e1+e2+…+ek=n非負(fù)整數(shù)解e1,

e2,…,ek的個(gè)數(shù)hn的生成函數(shù)。提示:∏k(x+x3+x5+x7+……).27練習(xí)（續(xù)）確定方程e1+e2+…+ek77練習(xí)(續(xù))令hn表示方程3e1+4e2+2e3+5e4=n非負(fù)整數(shù)解的個(gè)數(shù).找到h0,h1,h2,…,hn,…….的生成函數(shù)g(x)提示:令f1=3e1,f2=4e2,f3=2e3并且f4=5e4.于是hn也等于f1+f2+f3+f4=n的非負(fù)整數(shù)解的個(gè)數(shù)，其中f1是3的倍數(shù),f2是4的倍數(shù),f3是偶數(shù)并且f4是5的倍數(shù).28練習(xí)(續(xù))令hn表示方程3e1+4e278遞歸生成函數(shù)29遞歸生成函數(shù)79內(nèi)容利用生成函數(shù)來求解常系數(shù)的線性齊次遞推關(guān)系.牛頓二項(xiàng)定理的應(yīng)用.30內(nèi)容利用生成函數(shù)來求解常系數(shù)的線性齊次遞推關(guān)系.80復(fù)習(xí):牛頓二項(xiàng)定理如果n是一個(gè)正整數(shù)并且r是一個(gè)非零整數(shù),那么31復(fù)習(xí):牛頓二項(xiàng)定理如果n是一個(gè)正整數(shù)并且r是一81例題確定平方項(xiàng)的序列0,1,4,…,n2,…..的生成函數(shù)解答:把n=2、r=1帶入上面的牛頓二項(xiàng)式,(1-x)-2=1+2x+3x2+…+nxn-1+….因此x/(1-x)2=x+2x2+3x3+…+nxn+…..微分,我們得到（1+x)/(1-x)3=1+22x+32x2+…+n2xn-1+…..乘x,得到x(1+x)/(1-x)3.32例題確定平方項(xiàng)的序列0,1,4,…,n2,….82例題(續(xù))求解滿足初始值h0=1和h1=-2的遞推關(guān)系hn=5hn-1–6hn-2,(n≥2).提示:令g(x)=h0+h1x+h2x2+…+hnxn+….為h0,h1,h2,…,hn…的生成函數(shù)。此時(shí)，我們有下列方程33例題(續(xù))求解滿足初始值h0=1和h1=83g(x)=h0+h1x+h2x2+…+hnxn+….-5xg(x)=-5h0x

-5h1x2-5h2x3-…-5hn-1xn-….6x2g(x)=6h0x2

+6h1x3+6h2x4+…+6hn-2xn+….將三個(gè)方程相加,得到(1-5x+6x2)g(x)=h0+(h1-5h0)x+(h2-5h1+6h0)x2+…+(hn-5hn-1+6hn-2)xn+….=h0+(h1-5h0)x=1-7x因此,g(x)=(1-7x)/(1-5x+6x2)=5/(1-2x)–4/(1-3x)34g(x)=h0+h1x+h2x2+…+hnxn+….84通過牛頓二項(xiàng)定理(1-2x)-1=1+2x+22x2+…+2nxn…..(1-3x)-1=1+3x+32x2+…+3nxn…..于是,g(x)=1+(-2)x+(-15)x2+…+(5×2n–4×3n)xn+…可以得到hn=5×2n–4×3n(n=0,1,2,…).35通過牛頓二項(xiàng)定理85練習(xí)滿足h0=0,h1=1，h2=-1的遞推關(guān)系hn+hn-1–16hn-2+20hn-3=0(n≥3)求hn的一般