組合數(shù)學(xué)幻燈片43

1、母函數(shù)有著廣泛的應(yīng)用，它不僅可以用來(lái)處理排列組合的計(jì)數(shù)問(wèn)題、整數(shù)分拆問(wèn)題，……而且還可以用來(lái)證明(或推導(dǎo))各種有用的組合恒等式。,4.3母函數(shù)在排列、組合中的應(yīng)用,從這節(jié)開(kāi)始我們分別討論母函數(shù)在某些問(wèn)題中的應(yīng)用。,特別是在第五章討論的遞歸關(guān)系中有著重要的應(yīng)用。,同樣，從這三個(gè)不同的物體中選取兩個(gè)有三種方法，或者選取a和b，或者選取b和c，或者選取c和a。,首先，我們考慮下列事實(shí)。令a,b,c表示三個(gè)不同的物體。顯然有三種方法從這三個(gè)不同

2、的物體中選取一個(gè)，或者選a，或者選b，或者選c,我們把這些可能的選取象征性地記為 a+b+c,我們把這些可能選取也象征性地記為 ab+bc+ca,而從這三個(gè)不同的物體中選取三個(gè)只有一種方法，把這種可能的選取象征性地記為 abc,考慮多項(xiàng)式 (1+ax)(1+bx)(1+cx) =1+(a+b+c)x1+(ab+bc+ca)x2+(abc)x3,從這個(gè)多項(xiàng)式可以看出，以上所有的可能選取方法都作為x的冪的

3、系數(shù)被表示出來(lái)了。,下面，利用乘法規(guī)則和加法規(guī)則對(duì)上面的多項(xiàng)式予以解釋。,特別是，xi的系數(shù)就是從三個(gè)不同的物體中選取i個(gè)物體的方法的表示。這并不是偶然的巧合。,對(duì)物體a, 因子 (1+ax) 象征性地表示有兩種選取方法: 不選取 a，或選取 a。,對(duì)于(1+bx),(1+cx)可作類似的解釋。這樣，(1+ax)(1+bx)(1+cx)就表明：對(duì)三個(gè)不同的物體a,b,c，其選擇方法是，不選取a或選取a；不選取b或選取b；不選

4、取c或選取c。,其中x僅是一個(gè)形式變量。 x0 的系數(shù)表明不選取 a, x1 的系數(shù)表明a被選取。,于是這三個(gè)因子的乘積中x的冪指數(shù)就表示被選取的物體的個(gè)數(shù)，而對(duì)應(yīng)的系數(shù)則表明了所有可能的選取方法。 因此，由普通母函數(shù)的定義知，三個(gè)因子 的乘積(1+ax)(1+bx)(1+cx)就是選取物體a，b，c的所有不同方法的普通母函數(shù)。,如果由于某種實(shí)際的需要，我們只對(duì)可能的選取方法的個(gè)數(shù)感興趣，而不是對(duì)不

5、同的選取方法感興趣，則可令a=b=c=1。,于是有 (1+x) (1+x) (1+x)=(1+x)3=1+3x+3x2+x3,該多項(xiàng)式表明 只有一種方法 從三個(gè)物體中一個(gè)也不選取，有三種方法 從這三個(gè)物體中選取一個(gè)，有三種方法 從這三個(gè)物體中選取兩個(gè)。有一種方法 這三個(gè)物體中選取三個(gè)。一般說(shuō)來(lái)，考慮多項(xiàng)式,對(duì)于這個(gè)多項(xiàng)式可作上面n=3時(shí)的同樣的解釋。也就是說(shuō)，從n個(gè)不同的物體中選其r個(gè)物體，其方法數(shù)

6、為(1+x)n的冪級(jí)數(shù)展開(kāi)式中xr的系數(shù) 。,以上討論的是從n個(gè)不同物體中選取r個(gè)物體(每個(gè)物體至多選取一次)的簡(jiǎn)單情形。 當(dāng)從n個(gè)不同的物體中，允許重復(fù)選取r個(gè)物體時(shí)，上面的情況就可作如下的推廣。,那么，類似地，我們可以用因子(1+x+x2)象征性地表示某一物體可以不選，或者選一次，或者選兩次。也就是說(shuō)某一物體至多選兩次。 同樣，用因子(1+x+x2+x3+…)象征性地表示某一物體可以不選，或者選一次，或者選兩次，或者

7、選三次，……。 那么，(1+x+x2+x3+…)n的冪級(jí)數(shù)展開(kāi)式中，xr的系數(shù)ar就表示從n個(gè)不同的物體中允許重復(fù)地選取r個(gè)物體的方式數(shù)。,由于因子(1+x)象征性地表示某一物體可以不選，或者只選一次。,下面，我們舉例加以說(shuō)明。,例1 證明從n個(gè)不同的物體中允許重復(fù)地選取r個(gè)物體的方式數(shù)為,這個(gè)問(wèn)題可以等價(jià)地?cái)⑹鰹椋鹤C明重集B=｛∞·b1,∞·b2,…,∞·bn｝的r-組合數(shù)為 。這就是

8、定理1.6已經(jīng)證明過(guò)的結(jié)論。,下面用母函數(shù)法證明：設(shè)ar表示從n個(gè)不同物體中允許重復(fù)選取r個(gè)物體的方式數(shù)，由上面的分析可知，序列(a0,a1,…,ar,…)的普通母函數(shù)為,例2 證明從n個(gè)不同的物體中允許重復(fù)地選取r個(gè)物體，但每個(gè)物體至少出現(xiàn)一次的方式數(shù)為,證明：設(shè)ar表示從n個(gè)不同物體中允許重復(fù)地選取r個(gè)物體，但每個(gè)物體至少出現(xiàn)一次的方式數(shù)，則序列(a0,a1,…,ar,…)的普通母函數(shù)為,故有,解：設(shè)a2r為所求的方式數(shù)，由于每

9、個(gè)物體出現(xiàn)偶數(shù)次。故可用因子(1+x2+x4+…)表示某一物體可以不選，或選取兩次，或選取4次，……。,例3 求從n個(gè)不同的物體中允許重復(fù)地選取2r個(gè)物體，但每個(gè)物體出現(xiàn)偶數(shù)次的方式數(shù)。,因此序列(a0,a1,…,ar,…)的普通母函數(shù)為,故有,例4 在一個(gè)書架上共有16本書，其中4本是高等數(shù)學(xué)，3本是普通物理，4本是數(shù)據(jù)結(jié)構(gòu)，5本是離散數(shù)學(xué)。求從中選取r本書的方式數(shù)，其中r=12。,解：這個(gè)問(wèn)題實(shí)際上是求重集 B=｛4·

10、;M,3·P,4·S,5·D｝的r-組合數(shù)也是§3.2節(jié)中例1的問(wèn)題。,設(shè)ar是選取r本書的方式數(shù)。由于高等數(shù)學(xué)最多只能選4本， 普通物理最多只能選3本， 數(shù)據(jù)結(jié)構(gòu)最多只能選4本， 離散數(shù)學(xué)最多只能選5本。,故序列(a0,a1,…,ar,…)的普通母函數(shù)為,這個(gè)答案與§3.2節(jié)中例1用容斥原理所求的結(jié)果是一致的。,取f(x)展開(kāi)式中xr的系數(shù)即為所求的方式數(shù)。當(dāng)

11、r=12,x12的系數(shù)為34，即 a12=34,解：這個(gè)問(wèn)題實(shí)際上是求重集 B=｛2n·A,2n·B,2n·C｝的3n組合數(shù)。 設(shè)ar為所求的方式數(shù)， 則序列(a0,a1,…, ar,…)的普通母函數(shù)為,例5 現(xiàn)有2n個(gè)A，2n個(gè)B和2n個(gè)C，求從它們之中選出3n個(gè)字母的不同的方式數(shù),在上式中x3n的系數(shù)為,故當(dāng)r=3n時(shí)有,以上，我們討論了普通母函數(shù)在組合計(jì)數(shù)問(wèn)題中的應(yīng)用。下面說(shuō)明指數(shù)母

12、函數(shù)在排列計(jì)數(shù)問(wèn)題中的一些應(yīng)用。,我們已知道,是從n個(gè)不同的物體中選取r個(gè)物體的組合數(shù)ar所成的序列的普通母函數(shù)。利用式(1.7)將上式變形有,而(1+x)=(1+x1/1!)象征性地表示某一物體在 排列中可以不選取，或者選取一次。由此我們得到啟發(fā)，某一物體在排列中可以不取，或取一次，或取兩次，……，或取r次可用如下形式表示：,這表明從n個(gè)不同的物體中選取r個(gè)物體的排列數(shù)恰好是xr/r!的系數(shù)。,特別是，如果某物體的重復(fù)次數(shù)是∞時(shí)，

13、則上式的形式變?yōu)?同樣地，如果某一物體在排列中至少取兩次，至多取五次，則可用下面的形式表示,證明：這個(gè)問(wèn)題實(shí)質(zhì)上是證明重集B=｛∞·b1,∞·b2,…,∞·bn｝的r排列數(shù)為nr。這就是§1.2節(jié)定理1.3已經(jīng)證明過(guò)的結(jié)論。這里用母函數(shù)的方法證明。,下面，我們舉例說(shuō)明。,例6 證明從n個(gè)不同的物體中允許重復(fù)地選取r個(gè)物體的排列數(shù)為nr,設(shè)ar為所求的排列數(shù)，由上面的分析知，序列(a0,a1,…,

14、ar,…)的指數(shù)母函數(shù)為,故有,解：這個(gè)問(wèn)題等價(jià)于求重集B=｛∞·1,∞·3,∞·5，∞·7，∞·9)｝的r排列數(shù)。其中要求7，9出現(xiàn)偶數(shù)次。,例7 求1，3，5，7，9五個(gè)數(shù)字組成r位數(shù)的個(gè)數(shù)。其中要求7，9出現(xiàn)的次數(shù)為偶數(shù)。其余數(shù)字的出現(xiàn)不加限制。,而,故,設(shè)所求的r-排列數(shù)為ar，則序列(a0,a1,…, ar,…)的指數(shù)母函數(shù)為,故,所以有,例8 用紅、白和綠三種顏色給1&

15、#215;n棋盤中的正方形著色，要求偶數(shù)個(gè)正方形著紅色，而著白色和綠色的正方形個(gè)數(shù)不加限制，求不同的著色方式數(shù)。,解：若用R，B和V分別表示紅、白和綠三種顏色，則該問(wèn)題實(shí)際上是求重集B=｛∞·R,∞·B,∞·V｝的n-排列。其中要求R出現(xiàn)偶數(shù)次。,設(shè)an為所求的方式數(shù)。定義a0=1，于是序列(a0,a1,…,an,…)的指數(shù)母函數(shù)為,故有,解：這是第三章容斥原理的習(xí)題8。這里用母函數(shù)法來(lái)求解。這個(gè)問(wèn)題實(shí)

16、際上是求重集B=｛∞·1,∞·2,∞·3，∞·5，∞·6，∞·7，∞·8，∞·9  ｝的n排列個(gè)數(shù)，其中要求數(shù)字3，8，9至少出現(xiàn)一次，而其他的數(shù)字則不加限制。,例9 在所有的n位數(shù)中，包含數(shù)字3，8，9，但不包含數(shù)字0，4的數(shù)有多少?,設(shè)符合題意的數(shù)有an個(gè)，則序列(a0,a1,…,an,…)的指數(shù)母函數(shù)為,故有,這個(gè)結(jié)果與用容斥原理所得的結(jié)