組合數(shù)學(xué)(18)教材

第七章遞推關(guān)系和生成函數(shù)

7.4.0生成函數(shù)上次課我們講到由數(shù)列生成函數(shù)。由數(shù)列h0,h1,h2,……,hn

,….生成函數(shù)為：

g(x)=h0+h1x+h2x2+……+hnxn+….

hn是系數(shù)，x按照冪級數(shù)升冪排列。稱函數(shù)g(x)是序列{hn}的生成函數(shù)。

下面我們將介紹與組合問題有關(guān)的生成函數(shù)1例：設(shè)k是整數(shù)，并且序列h0,h1,h2,…,hn,…

定義hn等于方程：e1+e2+…+ek＝n

的非負(fù)整數(shù)解的個(gè)數(shù),求生成函數(shù)。解：由于方程的非負(fù)整數(shù)解的個(gè)數(shù)(見P44)為：2由牛頓二項(xiàng)式定理(P94)我們可以求出上述冪級數(shù)的收斂函數(shù)為：再將生成函數(shù)展開來分析：3其中xe1是第一個(gè)因子的典型項(xiàng),xe2是第二個(gè)因子的典型項(xiàng)，……xek是第k個(gè)因子的典型項(xiàng)，將這些典型項(xiàng)乘起來，當(dāng)e1+e2+…+ek＝n時(shí)同底數(shù)項(xiàng)乘指數(shù)相加，就得到：4于是公式：中xn的系數(shù)就等于方程e1+e2+…+ek＝n非負(fù)整數(shù)解的個(gè)數(shù)(見P44)：5

將這個(gè)例子應(yīng)用到更一般的情況中去

例：是什么樣的序列的生成函數(shù)？解：設(shè)

6則原式的典型項(xiàng)記為：

假設(shè)e1+e2+e2＝n，可見乘積中xn的系數(shù)是方程e1+e2+e2＝n的整數(shù)解的個(gè)數(shù)hn

；其中0≤e1≤5,0≤e2≤2,0≤e3≤4,當(dāng)n≥5+2+4=11時(shí)，hn

=0

生成函數(shù)：可以展開得到。77.4.1組合的生成函數(shù)

與組合問題有關(guān)的計(jì)數(shù)常使用生成函數(shù)。命題：設(shè)多重集S={r1·e1,r2·e2,…,

rm·em},且r1+r2+…+rm=n,則S的k可重復(fù)組合數(shù)ck對應(yīng)序列{ck}的生成函數(shù)為：其中，k可重復(fù)組合數(shù)ck為G(x)展開式中xk的系數(shù)。

8

證明:令G(x)中各∑的項(xiàng)分別對應(yīng)諸元素的某種可能取法。例如,對i=t,xr表示元素et選取了r次。依次類推。顯然G(x)展開式中的項(xiàng)xk具有一般形式其中

k1+k2+…+km=k,0≤ki≤ri,i=1,2,…,m

9對此方程的一非負(fù)整數(shù)解(k1,k2,…,km)（在前提0≤ki≤ri,i=1,2,…,m下），乘積 就對應(yīng)了諸元素e1,e2,…,em的一種可重復(fù)取法。合并同類項(xiàng)后，xk的系數(shù)就表示了從多重集S中取出k個(gè)元素的所有可能的可重組合數(shù)ck。10

推論

1設(shè)S={e1,e2,…,em}，則S的k可重復(fù)組合數(shù)ck對應(yīng)序列{ck}的生成函數(shù)為G(x)=(1+x)m其組合數(shù)ck為G(x)展開式中xk的系數(shù)11推論2設(shè)S={∞·e1,∞·e2,…,∞·em},則S的k(無限)

可重復(fù)組合數(shù)ck對應(yīng)序列{ck}的生成函數(shù)為:其組合數(shù)ck為G(x)展開式中xk的系數(shù)推論2無0≤ki≤ri,i=1,2,…,m限制，由書中(見P44定理3.5.1)即知：12推論

3設(shè)S={∞·e1,∞·e2,…,∞·em}，則S的每個(gè)元素至少取一次的k(無限)可重復(fù)組合數(shù)ck(k≥m)對應(yīng)序列{ck}的生成函數(shù)為：其組合數(shù)ck為G(x)展開式中xk的系數(shù)。這是由于:換元13推論

4設(shè)S={∞·e1,∞·e2,…,∞·em}，且S的每個(gè)元素出現(xiàn)非負(fù)偶數(shù)次，則S的k(無限)可重組復(fù)合數(shù)ck對應(yīng)序列{ck}的生成函數(shù)為:其組合數(shù)ck為G(x)展開式中xk的系數(shù)，即14

推論

5設(shè)S={∞·e1,∞·e2,…,∞·em}，則S的每個(gè)元素出現(xiàn)奇數(shù)次的k（無限）可重復(fù)組合數(shù)ck對應(yīng)序列{ck}的生成函數(shù)為:其組合數(shù)ck為G(x)展開式中xk的系數(shù)，即:15

推論

6設(shè)S={∞·e1,∞·e2,…,∞·em}，若限定元素ei出現(xiàn)的次數(shù)集合為Pi(1≤i≤n)，則從S中取出k個(gè)元素的組合數(shù)ck對應(yīng)序列{ck}的生成函數(shù)為:16

推論

7設(shè)多重集S={r1·e1,r2·e2,…,rm·em}，且

r1+r2+…+rm=n，則S中的每個(gè)元素ei至少出現(xiàn)ki(i=1,2,…,m)次的r可重組合數(shù)cr對應(yīng)序列{cr}的生成函數(shù)為:其組合數(shù)cr為G(x)展開式中xr的系數(shù)，

r=k,k+1,…,n;k=k1+k2+…+km。17例:求不定方程k1+k2+k3+k4=20的解數(shù)。其中,限制k1可取0,2,4;k2可取1,3,5;k3可取6,7;k4可取8,9。解:設(shè)不定方程 的解組數(shù)目為ck，本例中m=4,k=20。注意到對ki(i=1,2,3,4)的限制，序列{ck}對應(yīng)的生成函數(shù)為:

G(x)=(1+x2+x4)(x+x3+x5)(x6+x7)(x8+x9)18G(x)=(1+x2+x4)(x+x3+x5)(x6+x7)(x8+x9)=(1+x2+x4)(1+x2+x4)x(1+x)x6(1+x)x8=(1+x2+x4)2(1+x)2x15=(1+x+x2+x3+x4+x5)2x15只需要多項(xiàng)式(1+x+x2+x3+x4+x5)2展開式中x5的系數(shù)就等于x20的系數(shù)，由(P92)多項(xiàng)式定理：

C20=2(1+1+1)=619由G(x)展開式中x20的系數(shù)可知,題給出不定方程解組數(shù)目為c20=6。

注意:有時(shí)會(huì)因?qū)i的限制使ck取值為0。例如，對S={a,b,c},若限制a可重復(fù)1,3,5次;限制b可重復(fù)2,4,6次;限制c必須出現(xiàn)6次,則由G(x)=(x+x3+x5)(x2+x4+x6)x6雖可求出c9=c17=1,c11=c15=2,c13=3,但對小于9及偶數(shù)的k,ck的取值全為0。20

例：確定蘋果、香蕉、橘子和梨的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ù)hn其中e1是偶數(shù)，e2是奇數(shù)，0≤e3≤4，1≤e4我們?yōu)槊糠N水果建立一個(gè)因子，其中的指數(shù)為21那種水果的n-組合中所允許的數(shù)量：22

這是個(gè)有理函數(shù)，泰勒級數(shù)中的系數(shù)就是對所考慮類型的組合計(jì)數(shù)。下面這個(gè)例子說明一個(gè)計(jì)數(shù)問題，有時(shí)候可以直接通過生成函數(shù)求解：23例：確定可以由蘋果、香蕉、橘子和梨的袋裝水果的袋數(shù)hn，其中在每個(gè)袋子中要求：蘋果的個(gè)數(shù)是偶數(shù)，香蕉的個(gè)數(shù)是5的倍數(shù)，橘子的個(gè)數(shù)最多4個(gè)，梨的個(gè)數(shù)是0或者1個(gè)。解：該問題是求蘋果、香蕉、橘子和梨的某些n-組合數(shù)。確定序列h0,h1,h2,…,hn,…的生成函數(shù)，我們?yōu)槊糠N水果建立一個(gè)因子：24

通項(xiàng)hn為：hn=n+1,僅僅通過代數(shù)運(yùn)算得到。25

例：確定方程：e1+e2+…+ek＝n的非負(fù)奇整數(shù)解

e1,e2,…,ek的個(gè)數(shù)hn的生成函數(shù)。解：我們有：26例：令hn表示方程：3e1+4e2+2e3+5e4＝n

的非負(fù)整數(shù)解的個(gè)數(shù)，求hn的生成函數(shù)。解：作代換：f1=3e1,f2=4e2,f3=2e3,f4=5e4,于是，原方程的非負(fù)整數(shù)解的個(gè)數(shù)也是方程：

f1+f2+f3+f4=n,的非負(fù)整數(shù)解的個(gè)數(shù)。其中

f1是3的倍數(shù)，f2是4的倍數(shù)f3是偶數(shù)f4是5的倍數(shù)。與分袋子中水果的解法一樣，因此：27例：有無數(shù)個(gè)1分,5分,10分,25分,50分的硬幣。確定用這些硬幣拼湊成n分錢的方法數(shù)hn的生成函數(shù)g(x);解：hn是方程e1+5e2+10e3+25e4+50e4＝n的非負(fù)整數(shù)解的個(gè)數(shù)28例:求S={3·a,4·b,5·c}的10組合數(shù)。解:設(shè)S的k組合數(shù)為ck，則{ck}對應(yīng)的生成函數(shù)為:展開式中x10的系數(shù)即S的10組合數(shù)為6。

29

例:設(shè)有5個(gè)紅球和8個(gè)黃球，要求每次取出不少于2個(gè)紅球和偶數(shù)個(gè)黃球，求所有的組合方式數(shù)。解:組合方式數(shù)對應(yīng)序列的生成函數(shù)為因此，由系數(shù)得總的組合方式數(shù)為1×4+2×8=2030

若考慮同色球各不相同或加有標(biāo)記，這時(shí)可分別設(shè)紅球與黃球取法所成序列的生成函數(shù)為A(x)與B(x)。易知:

31從而：

C(x)展開式中xk的系數(shù)即為每次取出k個(gè)球的組合方式數(shù)，總的組合方式數(shù)目為所有系數(shù)之和,很明顯，各個(gè)球由各自的標(biāo)志后取出的變化就更多。32例：設(shè)有紅球2個(gè)，黑、白球各1個(gè)，問：

(1)共有多少不同的選取方法？試加以枚舉。(2)若每次從中任取3個(gè)，有多少種不同取法？解:(1)設(shè)用r，b，w分別代表紅、黑、白三種球，兩個(gè)紅球的取法與r0,r1,r2對應(yīng)，即紅球的可能取法與1+r+r2中r的各次冪一一對應(yīng)，亦即r0=133表示不取紅球，r表示取1個(gè)紅球，r2表示取2

個(gè)紅球。對其它球，依此類推法，則不同選取方法數(shù)所成序列對應(yīng)的尋常生成函數(shù)為:分析上式，不難發(fā)現(xiàn)

1：一個(gè)球都不取，僅有一種方案；34

r+b+w:取1個(gè)球的方案有3種,分別為紅,黑,白；

r2+rb+rw+bw：取2個(gè)球的方案有4種，分別為紅紅,紅黑，紅白，黑白；r2b+r2w+rbw：取3個(gè)球的方案有3種，即2紅1黑，2紅1白，三色球各取其一；

r2bw：取4個(gè)球的方案僅1種，即所有球全取。若令r=b=w=1，即可求得所有不同的選取方案總數(shù)為:G(1,1,1)=1+3+4+3+1=1235（2）若只考慮每次取3個(gè)球的方案數(shù)，而不需枚舉，則可令r=b=w=x。寫出G(x)=(1+x+x2)(1+x)2=1+3x+4x2+3x3+x4由x3的系數(shù)知所求