組合數(shù)學(xué)課件--第二章母函數(shù)與遞推關(guān)系-

1、第二章 母函數(shù)與遞推關(guān)系組合數(shù)學(xué)2.1 母函數(shù) 遞推關(guān)系是計數(shù)的一個強有力的工具，特別是在做算法分析時是必需的。遞推關(guān)系的求解主要是利用母函數(shù)。當然母函數(shù)尚有其他用處，但這主要是介紹解遞推關(guān)系上的應(yīng)用。例如2.1 母函數(shù) 項的系數(shù) 中所有的項包括n個元素a1，a2， an中取兩個組合的全體；同理項系數(shù)包含了從n個元素a1，a2， an中取3個元素組合的全體。以此類推。2.1 母函數(shù) 若令a1=a2= =an=1，在（2-1-1）式中 項系數(shù)： 中每一個組合有1個貢獻，其他各項以此類推。故有：2.1 母函數(shù) 另一方面：2.1 母函數(shù)比較等號兩端項對應(yīng)系數(shù)，可得一等式2.1 母函數(shù) 同樣對于 ，（

2、設(shè) ），用類似的方法可得等式： 正法如下：2.1 母函數(shù)比較等式兩端的常數(shù)項，即得公式(2-1-3)2.1 母函數(shù)又如等式：令x=1 可得2.1 母函數(shù)(2-1-2)式等號的兩端對x求導(dǎo)可得：等式(2-1-5)兩端令x=1，得：2.1 母函數(shù) 用類似的方法還可以得到： 定義：對于序列 構(gòu)造一函數(shù)：2.1 母函數(shù) 還可以類似地推出一些等式，但通過上面一些例子已可見函數(shù) 在研究序列 的關(guān)系時所起的作用。對其他序列也有同樣的結(jié)果?，F(xiàn)引進母函數(shù)概念如下： 稱函數(shù)G(x)是序列 的母函數(shù)序列 可記為 。 如若已知序列 則對應(yīng)的母函數(shù)G(x)便可根據(jù)定義給出。反之，如若以求得序列的母函數(shù)G(x)，則該序列

3、也隨之確定。 2.1 母函數(shù) 例如 是序列 的母函數(shù)。 2.2 遞推關(guān)系 利用遞推關(guān)系進行計數(shù)這個方法在算法分析中經(jīng)常用到，舉例說明如下： 例一.Hanoi問題：這是個組合數(shù)學(xué)中的著名問題。N個圓盤依其半徑大小，從下而上套在A柱上，如下圖示。每次只允許取一個移到柱B或C上，而且不允許大盤放在小盤上方。若要求把柱A上的n個盤移到C柱上請設(shè)計一種方法來，并估計要移動幾個盤次?，F(xiàn)在只有A、B、C三根柱子可用。2.2 遞推關(guān)系 Hanoi問題是個典型的問題，第一步要設(shè)計算法，進而估計它的復(fù)雜性，集估計工作量。算法：N=2時第一步先把最上面的一個圓盤套在B上 第二步把下面的一個圓盤移到C上 最后把B上的

4、圓盤移到C上 到此轉(zhuǎn)移完畢A B C2.2 遞推關(guān)系 對于一般n個圓盤的問題， 假定n-1個盤子的轉(zhuǎn)移算法已經(jīng)確定。 先把上面的n-1個圓盤經(jīng)過C轉(zhuǎn)移到B。 第二步把A下面一個圓盤移到C上 最后再把B上的n-1個圓盤經(jīng)過A轉(zhuǎn)移到C上A B C2.2 遞推關(guān)系 上述算法是遞歸的運用。n=2時已給出算法；n=3時，第一步便利用算法把上面兩個盤移到B上，第二步再把第三個圓盤轉(zhuǎn)移到柱C上；最后把柱B上兩個圓盤轉(zhuǎn)移到柱C上。N=4，5，以此類推。2.2 遞推關(guān)系 算法分析：令h(n)表示n個圓盤所需要的轉(zhuǎn)移盤次。根據(jù)算法先把前面n-1個盤子轉(zhuǎn)移到B上；然后把第n個盤子轉(zhuǎn)到C上；最后再一次將B上的n-1個

5、盤子轉(zhuǎn)移到C上。 n=2時，算法是對的，因此，n=3是算法是對的。以此類推。于是有2.2 遞推關(guān)系算法復(fù)雜度為： H(x)是序列 的母函數(shù)。給定了序列，對應(yīng)的母函數(shù)也確定了。反過來也一樣，求得了母函數(shù)，對應(yīng)的序列也就可得而知了。當然，利用遞推關(guān)系(2-2-1)式也可以依次求得 ，這樣的連鎖反應(yīng)關(guān)系，叫做遞推關(guān)系。2.2 遞推關(guān)系 下面介紹如何從(2-2-1)式求得母函數(shù)H(x)的一種形式算法。所謂形式算法說的是假定這些冪級數(shù)在作四則運算時，一如有限項的代數(shù)式一樣。2.2 遞推關(guān)系 根據(jù)(2-2-1)， 或利用遞推關(guān)系(2-2-1)有2.2 遞推關(guān)系 上式左端為： 右端第一項為： 右端第二項為：

6、2.2 遞推關(guān)系 整理得 這兩種做法得到的結(jié)果是一樣的。即：2.2 遞推關(guān)系 令 如何從母函數(shù)得到序列 ？下面介紹一種化為部分分數(shù)的算法。2.2 遞推關(guān)系 由上式可得： 即：2.2 遞推關(guān)系因為：2.2 遞推關(guān)系 例2. 求n位十進制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)。 先從分析n位十進制數(shù)出現(xiàn)偶數(shù)個5的數(shù)的結(jié)構(gòu)入手 是n-1位十進制數(shù)，若含有偶數(shù)個5，則 取5以外的0，1，2，3，4，6，7，8，9九個數(shù)中的一個，若 只有奇數(shù)個5，則取 ，使 成為出現(xiàn)偶數(shù)個5的十進制數(shù)。2.2 遞推關(guān)系 解法1： 令 位十進制數(shù)中出現(xiàn)5的數(shù)的個數(shù)， 位十進制數(shù)中出現(xiàn)奇數(shù)個5的數(shù) 的個數(shù)。 故有： 也有類似解釋。2.

7、2 遞推關(guān)系 (2-2-2)式中的 表達了含有偶數(shù)個5的n位十進制數(shù)的兩個組成部分。 表達由含有偶數(shù)個5的n-1位十進制數(shù) ，令 取5以外的0，1，2，3，4，6，7，8，9九個數(shù)中的一個數(shù)構(gòu)成的。 項表示當 是含有奇數(shù)個5的n-1位十進制數(shù)，令 而得 是含偶數(shù)個5的n位十進制數(shù)。 (2-2-2)是關(guān)于序列 和 的連立關(guān)系。2.2 遞推關(guān)系 設(shè)序列 的母函數(shù)為 ，序列 的母函數(shù)為 。即：2.2 遞推關(guān)系承前頁：2.2 遞推關(guān)系 又：故得關(guān)于母函數(shù) 和 得連立方程組：2.2 遞推關(guān)系2.2 遞推關(guān)系2.2 遞推關(guān)系 解法二： n-1位的十進制數(shù)的全體共 從中去掉含有偶數(shù)個5的數(shù)，余下的便是n-1

8、位中含有奇數(shù)個5的數(shù)。故有： 2.2 遞推關(guān)系令2.2 遞推關(guān)系 1）不出現(xiàn)某特定元素設(shè)為 ，其組合數(shù)為 ，相當于排除 后從 中取r個做允許重復(fù)的組合。2.2 遞推關(guān)系 例三：從n個元素 中取r個進行允許重復(fù)的組合。假定允許重復(fù)的組合數(shù)用 表示，其結(jié)果可能有以下兩種情況。 2.2 遞推關(guān)系 2）至少出現(xiàn)一個 ，取組合數(shù)為 相當于從 中取r-1個做允許重復(fù)的組合，然后再加上一個 得從n個元素中取r個允許重復(fù)的組合。 依據(jù)加法原則可得： 因 ，故令2.2 遞推關(guān)系 遞推關(guān)系(2-2-3)帶有兩個參數(shù)n和r。2.2 遞推關(guān)系 (2-2-3)式是關(guān)于 的遞推關(guān)系，但系數(shù) 不是常數(shù)。但2.2 遞推關(guān)系

9、由二項式定理 可得2.3 母函數(shù)的性質(zhì)2.3母函數(shù)的性質(zhì) 一個序列和它的母函數(shù)一一對應(yīng)。給了序列便得知它的母函數(shù)；反之，求得母函數(shù)序列也隨之而定。這種關(guān)系頗像數(shù)學(xué)中的積分變換，特別酷似離散序列的Z變換。如2的例子所示的那樣，為了求滿足某種第推關(guān)系的序列，可把它轉(zhuǎn)換為求對應(yīng)的母函數(shù) ， 可能滿足一代數(shù)方程，或代數(shù)方程組，甚至于是微分方程。2.3母函數(shù)的性質(zhì) 最后求逆變換，即從已求得的母函數(shù) 得到序列 。關(guān)鍵在于要搭起從序列到母函數(shù)，從母函數(shù)到序列這兩座橋。這一節(jié)便是以此為目的的。不特別說明下面假設(shè) 、 兩個序列對應(yīng)的母函數(shù)分別為 、2.3母函數(shù)的性質(zhì) 性質(zhì)1：若 則證：2.3母函數(shù)的性質(zhì) 例.

10、已知則2.3母函數(shù)的性質(zhì) 性質(zhì)2：若 ，則2.3母函數(shù)的性質(zhì)證：2.3母函數(shù)的性質(zhì) 例.2.3母函數(shù)的性質(zhì) 性質(zhì)2：若 ，則證：2.3母函數(shù)的性質(zhì)2.3母函數(shù)的性質(zhì) 例. 已知2.3母函數(shù)的性質(zhì) 類似可得：2.3母函數(shù)的性質(zhì) 性質(zhì)2：若 收斂，則2.3母函數(shù)的性質(zhì)2.3母函數(shù)的性質(zhì) 性質(zhì)5. 若 ，則 。 例. 則2.3母函數(shù)的性質(zhì)性質(zhì)5和性質(zhì)6的結(jié)論是顯而易見的。 性質(zhì)6. 若 ，則 2.3母函數(shù)的性質(zhì) 性質(zhì)7. 若 則 2.3母函數(shù)的性質(zhì)證: 。2.3母函數(shù)的性質(zhì) 例. 已知 則 2.4 Fibonacci數(shù)列2.4.1遞推關(guān)系 Fibonacci數(shù)列是遞推關(guān)系的又一個典型問題，數(shù)列的本身

11、有著許多應(yīng)用。 問題：有雌雄兔子一對，假定過兩月便可繁殖雌雄各一的一對小兔。問過了n個月后共有多少對兔子？ 設(shè)滿n個月時兔子對數(shù)為 其中當月新生兔數(shù)目設(shè)為 對。第n-1個月留下的兔子數(shù)目設(shè)為 對。2.4.1遞推關(guān)系 但即第n-2個月的所偶兔子到第n個月都有繁殖能力了。由遞推關(guān)系(2-3-1)式可依次得到2.4.2問題的求解 設(shè)2.4.2問題的求解 承前頁2.4.2問題的求解承前頁2.4.2問題的求解承前頁2.4.2問題的求解 其中2.4.3若干等式 1） 證明：2.4.3若干等式 2） 證明：2.4.3若干等式 3） 證明：2.4.4在選優(yōu)法上的應(yīng)用 設(shè)函數(shù) 在區(qū)間 上有一單峰極值點，假定為極

12、大點。 所謂單峰極值，即只有一個極值點 ，而且當x與 偏離越大，偏差 也越大。如下圖：2.4.4在選優(yōu)法上的應(yīng)用 設(shè)函數(shù) 在 點取得極大值。要求用若干次試驗找到 點準確到一定的程度。最簡單的方法，把 三等分，令：如下圖：2.4.4在選優(yōu)法上的應(yīng)用 依據(jù) 的大小分別討論如下： 當 ，則極大點 必在 區(qū)間上，區(qū)間 可以舍去。2.4.4在選優(yōu)法上的應(yīng)用 當 ，則極大點 必在 區(qū)間上，區(qū)間 可以舍去。2.4.4在選優(yōu)法上的應(yīng)用 當 ，則極大點 必在 區(qū)間上，區(qū)間 和 均可以舍去。2.4.4在選優(yōu)法上的應(yīng)用 可見做兩次試驗，至少可把區(qū)間縮至原來區(qū)間的2/3，比如 ，進一步在 區(qū)間上找極值點。若繼續(xù)用三等

13、分法，將面對著這一實事，即其中 點的試驗沒發(fā)揮其作用。為此設(shè)想在 區(qū)間的兩個對稱點 分別做試驗。2.4.4在選優(yōu)法上的應(yīng)用 設(shè)保留 區(qū)間，繼續(xù)在 區(qū)間的下面兩個點 處做試驗，若則前一次 的點的試驗，這一次可繼續(xù)使用可節(jié)省一次試驗。由(2-3-6)式有2.4.4在選優(yōu)法上的應(yīng)用 這就是所謂的0.618優(yōu)選法。即若在 區(qū)間上找單峰極大值時，可在 點做試驗。比如保留區(qū)間 ，由于 ，故只要在 點作一次試驗。2.4.4在選優(yōu)法上的應(yīng)用 優(yōu)選法中可利用Fibonacci數(shù)列，和0.618法不同之點在于它預(yù)先確定試驗次數(shù)，分兩種情況介紹其方法。 (a) 所有可能試驗數(shù)正好是某個 。2.4.4在選優(yōu)法上的應(yīng)用

14、 這時兩個試驗點放在 和 兩個分點上，如果 分點比較好，則舍去小于 的部分；如果 點更好，則舍去大于 的部分。在留下的部分共 個分點，其中第 和第 二試驗點，恰好有一個是剛才留下來的試驗可以利用。 可見在 個可能試驗中，最多用n-1次試驗便可得到所求的極值點2.4.4在選優(yōu)法上的應(yīng)用 (b)利用Fibonacci數(shù)列進行優(yōu)選不同于 0.618法之點,還在于它適合于參數(shù)只能取整數(shù)數(shù)值的情況.如若可能試驗的數(shù)目比 小,但比 大時,可以虛加幾個點湊成 個點，但新增加的點的試驗不必真做，可認定比其他點都差的點來處理。2.4.4在選優(yōu)法上的應(yīng)用 下面給出兩個定理作為這一節(jié)的結(jié)束。 定理：測試n次可將包含

15、單峰極值點的區(qū)間縮小到原區(qū)間的 ，其中 是任意小的正整數(shù)，2.4.4在選優(yōu)法上的應(yīng)用 證：對n用數(shù)學(xué)歸納法。 n=2時，將區(qū)間 平分成 段。在分點（包括端點a，b）分別標上 。在1點的兩側(cè)取 ，在 與 兩點上測試，無論哪一點較優(yōu)，保留下來的區(qū)間長度均為 ，命題成立。2.4.4在選優(yōu)法上的應(yīng)用 假設(shè)對于n-1，命題成立 對于n，將 平分成 段，對分點（包括端點a，b）依次標上 。先在 點與 點測試，無論哪一點較優(yōu)，保留下來的區(qū)間均為 段。根據(jù)歸納假設(shè)，再做n-1次測試（內(nèi)含前兩次測試之一）可將含極值點的區(qū)間縮小到 段，即原區(qū)間 的 。2.4.4在選優(yōu)法上的應(yīng)用 因 ，當n較大時，可將相繼的兩個測

16、試點取在待測區(qū)間的0.618及1-0.618處。由 可知，0.618法比 法最多多測試一次。0.618 法的優(yōu)點是不必事先定測試次數(shù)。2.4.4在選優(yōu)法上的應(yīng)用 定理：設(shè)在給定區(qū)間內(nèi)有單峰極值點。如果包含極值點在內(nèi)的可測點為 個，則測試n次必可找到極值點， 。 證：對n用數(shù)學(xué)歸納法。 n=2時， ，命題成立2.4.4在選優(yōu)法上的應(yīng)用 下面證明對n命題成立。設(shè)可測試點的標號依次是 。先在 點及 點測試。無論哪一點較優(yōu)，保留下來的可測點都為 個。根據(jù)歸納假設(shè)，再測試n-1必可找到極值點。而在保留的 個可測試點中，有一點（ 或 ）的測試結(jié)果下一次比較好時正好用上，這樣總測試次數(shù)為n。 假設(shè)對于n-1

17、，命題成立2.5 線性常系數(shù)遞推關(guān)系 2.5 線性常系數(shù)遞推關(guān)系 定義 如果序列 滿足 及 是常數(shù)， ，則稱為 的 階常系數(shù)線性遞推關(guān)系， 稱為 的初始條件，稱為 的特征多項式2.5 線性常系數(shù)遞推關(guān)系 設(shè) 為 的母函數(shù)根據(jù)(2-5-1)，有2.5 線性常系數(shù)遞推關(guān)系將這些式子兩邊分別相加，得到即其中2.5 線性常系數(shù)遞推關(guān)系 令 ，多項式 的次數(shù)不大于 。特征多項式2.5 線性常系數(shù)遞推關(guān)系因此，是 次多項式，我們知道 在復(fù)數(shù)域中有 個根。設(shè)2.5 線性常系數(shù)遞推關(guān)系則 于是2.5 線性常系數(shù)遞推關(guān)系(2-5-3)式是有理式，且分子的次數(shù)低于分母的次數(shù)，有分項表示，即：2.5 線性常系數(shù)遞推

18、關(guān)系承上頁： 的系數(shù)是 。 是常數(shù)。2.5 線性常系數(shù)遞推關(guān)系 定理：設(shè) 是有理分式，多項式的 次數(shù)低于 的次數(shù)。則 有分項表示，且表示唯一2.5 線性常系數(shù)遞推關(guān)系 證明：設(shè) 的次數(shù)為n，對n用數(shù)學(xué)歸納法。 n=1時， 是常數(shù)，命題成立。 假設(shè)對小于n的正整數(shù)，命題成立。 下面證明對正整數(shù)n命題成立。設(shè) 是 的 重根，2.5 線性常系數(shù)遞推關(guān)系不妨設(shè) 與 互素，設(shè)2.5 線性常系數(shù)遞推關(guān)系 的次數(shù)低于 。根據(jù)歸納假設(shè)，可分項表示。因此，可分項表示。由(2-5-6)式及(2-5-7)式可知表示是唯一的。2.5 線性常系數(shù)遞推關(guān)系以下分別各種情況討論具體計算的問題。（1）特征多項式 無重根 設(shè)

19、可見化為2.5 線性常系數(shù)遞推關(guān)系 的系數(shù)是可由線性方程組解出。2.5 線性常系數(shù)遞推關(guān)系 的系數(shù)矩陣的行列式是Vander mond 行列式不難看出 有唯一解。2.5 線性常系數(shù)遞推關(guān)系（2）特征多項式 有共軛復(fù)根 設(shè) 是 的一對共軛復(fù)根。中 的系數(shù)是2.5 線性常系數(shù)遞推關(guān)系 2.5 線性常系數(shù)遞推關(guān)系其中在具體計算時，可先求出各對共軛復(fù)根，再求待定系數(shù)A，B，避免中間過程的復(fù)數(shù)運算。 （3）特征多項式 有重根設(shè) 是 的 重根，則(2-5-4)可簡化為2.5 線性常系數(shù)遞推關(guān)系 的系數(shù) 。其中是n的j-1次多項式。因此， 是 與n的k-1次多項式的乘積。2.5 線性常系數(shù)遞推關(guān)系 為了簡化

20、計算，下面引入一些記號，介紹幾個命題。 設(shè)x是任意變量，n是非負整數(shù)，令2.5 線性常系數(shù)遞推關(guān)系 不難證明，多項式可用 唯一線性表示。其中 是常數(shù)2.5 線性常系數(shù)遞推關(guān)系 設(shè) 是給定序列，令 稱為 的 階差分。 不難證明，如果對任意的n有 ，則有因而序列 的特征多項式為2.5 線性常系數(shù)遞推關(guān)系 不難證明，如果 是n的r次多項式，則 是n的r+1次多項式。 以上幾個命題作為習(xí)題，請讀者自己證明。2.5 線性常系數(shù)遞推關(guān)系 總之： (1)若特征多項式 有n個不同零點 則遞推關(guān)系(2-5-1)的解其中 是待定系數(shù)，有初始條件(2-5-2)來確定。2.5 線性常系數(shù)遞推關(guān)系 (2)若特征多項式

21、有不同的復(fù)根，可依照(1)的辦法處理。不過任意復(fù)數(shù) 可寫為 形式，設(shè) 是 的一個零點，其共軛復(fù)根為2.5 線性常系數(shù)遞推關(guān)系 和 仍然是待定常數(shù)。即 有一對共軛復(fù)根 和 時，遞推關(guān)系(2-5-1)的解有對應(yīng)的項其中A，B是待定常數(shù)。2.5 線性常系數(shù)遞推關(guān)系 (3)若 k重根。不妨設(shè) 是k的重根。則遞推關(guān)系(2-5-1)的解對應(yīng)于的項為 其中 是k個待定常數(shù)。2.5 線性常系數(shù)遞推關(guān)系 例1：求下列n階行列式 的值。2.5 線性常系數(shù)遞推關(guān)系根據(jù)行列式性質(zhì)對應(yīng)的特征方程為故 是二重根2.5 線性常系數(shù)遞推關(guān)系 時有 時有即2.5 線性常系數(shù)遞推關(guān)系 例2：求同理相減得2.5 線性常系數(shù)遞推關(guān)系

22、同理對應(yīng)的特征方程為2.5 線性常系數(shù)遞推關(guān)系 是三重根即這就證明了2.5 線性常系數(shù)遞推關(guān)系 例2：求同理相減得2.5 線性常系數(shù)遞推關(guān)系同理對應(yīng)的特征方程為相減得同理2.5 線性常系數(shù)遞推關(guān)系 是四重根依據(jù) 得關(guān)于A、B、C、D的連立方程組：2.5 線性常系數(shù)遞推關(guān)系2.5 線性常系數(shù)遞推關(guān)系 已知 是n的3次式，故不妨令確定待定系數(shù)時，比較方便，無需解一聯(lián)立方程組。 例如2.5 線性常系數(shù)遞推關(guān)系2.5 線性常系數(shù)遞推關(guān)系 例4：求 解: 是n的3次多項式，因此 是滿足遞推關(guān)系：設(shè)2.5 線性常系數(shù)遞推關(guān)系2.5 線性常系數(shù)遞推關(guān)系以n=5對上面的結(jié)果驗證一下2.5 線性常系數(shù)遞推關(guān)系

23、例5：求 中 的 系數(shù)。 解： 的特征多項式是2.5 線性常系數(shù)遞推關(guān)系 是3重根 是1重根 的根是2.5 線性常系數(shù)遞推關(guān)系因此可設(shè)2.5 線性常系數(shù)遞推關(guān)系 通過做長除法，求得2.5 線性常系數(shù)遞推關(guān)系可知 利用 的值解得。 故2.5 線性常系數(shù)遞推關(guān)系 通過上式，計算得 與用長除法得到的結(jié)果相同。2.6 整數(shù)的拆分和Ferrers圖像 2.6.1 問題舉例 所謂整數(shù)拆分即把整數(shù)分解成若干整數(shù)的和，相當于把n個無區(qū)別的球放到n個無標志的盒子，盒子允許空著，也允許放多于一個球。整數(shù)拆分成若干整數(shù)的和，辦法不一，不同拆分法的總數(shù)叫做拆分數(shù)。2.6.1 問題舉例 例1：若有1克、2克、3克、4克

24、的砝碼各一枚，問能稱出那幾種重量？有幾種可能方案？2.6.1 問題舉例 從右端的母函數(shù)知可稱出從1克到10克，系數(shù)便是方案數(shù)。例如右端有 項，即稱出5克的方案有2同樣，故稱出6克的方案有2，稱出10克的方案有12.6.1 問題舉例 例2：求用1分、2分、3分的郵票貼出不同數(shù)值的方案數(shù)。因郵票允許重復(fù)，故母函數(shù)為 以其中為例，其系數(shù)為4，即4拆分成1、2、3之和的拆分數(shù)為4，即2.6.1 問題舉例 例3：若有1克砝碼3枚、2克砝碼4枚、4克砝碼2枚的砝碼各一枚，問能稱出那幾種重量？各有幾種方案？2.6.1 問題舉例2.6.1 問題舉例 例4: 整數(shù)n拆分成1，2，3，m的和，并允許重復(fù)，求其母函

25、數(shù)。如若其中m至少出現(xiàn)一次，其母函數(shù)如何？ 若整數(shù)n拆分成1，2，3，m的和，并允許重復(fù)，其母函數(shù)為：2.6.1 問題舉例2.6.1 問題舉例 若拆分中m至少出現(xiàn)一次，其母函數(shù)為：2.6.1 問題舉例顯然有等式(2-6-1)的組合意義：即整數(shù)n拆分成1到m的和的拆分數(shù)減去拆分成1到m-1的和的拆分數(shù)，即為至少出現(xiàn)一個m的拆分數(shù)。2.6.1 問題舉例 例1：若有1、2、4、8、16、32克的砝碼各一枚，問能稱出那幾種重量？有幾種可能方案？2.6.1 問題舉例 從母函數(shù)可以得知，用這些砝碼可以稱出從1克到63克的重量，而且辦法都是唯一的。 這問題可以推廣到證明任一十進制數(shù)n，可表示為而且是唯一的。

26、2.6.2 拆分數(shù)估計式 定理：設(shè) 為整數(shù)n的拆分數(shù)，則 證：令 一個整數(shù)n拆分成若干整數(shù)的和，在拆分中每個整數(shù)允許重復(fù)出現(xiàn)。故2.6.2 拆分數(shù)估計式2.6.2 拆分數(shù)估計式2.6.2 拆分數(shù)估計式由于2.6.2 拆分數(shù)估計式 把(2-6-3)式代入(2-6-2)式得由于2.6.2 拆分數(shù)估計式因而2.6.2 拆分數(shù)估計式 設(shè) ，有2.6.2 拆分數(shù)估計式把(2-6-4)式代入(2-6-5)式得曲線 是上凸，故曲線位于曲線 的切線下方，點 的切線為故有2.6.2 拆分數(shù)估計式 圖 (2-6-1)2.6.2 拆分數(shù)估計式以上式代入(2-6-5)式得：2.6.2 拆分數(shù)估計式 不等式(2-6-7

27、)的左端 是常數(shù)，右端是 的函數(shù) ，即不等式對于 成立。右端函數(shù)取極小值時將給出較好的上界值。令求導(dǎo)得2.6.2 拆分數(shù)估計式令 ，得解方程，得2.6.2 拆分數(shù)估計式因為所以 是極小值。以 的值代入 ，得2.6.2 拆分數(shù)估計式利用 ，上式可改進為2.6.3 Ferrers圖像 一個從上而下的n層格子， 為第 層的格子數(shù)，當 ，即上層的格子數(shù)不少于下層的格子數(shù)時，稱之為Ferrers圖像，如圖(2-6-2)示。 圖 2-6-22.6.3 Ferrers圖像 Ferrers圖像具有如下性質(zhì)： 1.每一層至少有一個格子。 2.第一行與第一列互換，第二行于第二列互換，即圖(2-6-3)繞虛線軸旋轉(zhuǎn)

28、所得的圖仍然是Ferrers圖像。兩個Ferrers 圖像稱為一對共軛的Ferrers圖像。2.6.3 Ferrers圖像 利用Ferrers圖像可得關(guān)于整數(shù)拆分的十分有趣的結(jié)果。 (a)整數(shù)n拆分成k個數(shù)的和的拆分數(shù)，和數(shù)n拆分成個數(shù)的和的拆分數(shù)相等。 因整數(shù)n拆分成k個數(shù)的和的拆分可用一k行的圖像表示。所得的Ferrers圖像的共軛圖像最上面一行有k個格子。例如： 2.6.3 Ferrers圖像 24=6+6+5+4+3 5個數(shù)，最大數(shù)為6 24=5+5+5+4+3+2 6個數(shù)，最大數(shù)為5圖(2-6-3)2.6.3 Ferrers圖像 (b)整數(shù)n拆分成最多不超過m個數(shù)的和的拆分數(shù)，和n拆

29、分成最大不超過m的拆分數(shù)相等。 理由和(a)相類似。 因此，拆分成最多不超過m個數(shù)的和的拆分數(shù)的母函數(shù)是2.6.3 Ferrers圖像 拆分成最多不超過m-1個數(shù)的和的拆分數(shù)的母函數(shù)是 所以正好拆分成m個數(shù)的和的拆分數(shù)的母函數(shù)為2.6.3 Ferrers圖像 所以正好拆分成m個數(shù)的和的拆分數(shù)的母函數(shù)為2.6.3 Ferrers圖像 (c)整數(shù)n拆分成互不相同的若干奇數(shù)的和的的拆分數(shù),和n拆分成自共軛的Ferrers圖像的拆分數(shù)相等. 設(shè) ，其中 。 構(gòu)造一個Ferrers圖像，其第一行，第一列都是 格，對應(yīng)于 ，第二行，第二列各 格，對應(yīng)于 。以此類推。由此得到的Ferres圖像是共軛的。反過

30、來也一樣。2.6.3 Ferrers圖像例如對應(yīng)為Ferrers圖像為9+5+3=17圖(2-6-4)2.7 指數(shù)型母函數(shù) 2.7.1 問題提出 設(shè)有n個元素，其中元素 重復(fù)了 次，元素 重復(fù)了 次， 重復(fù)了 次， 從中取r個排列，求不同的排列數(shù) 如果 ，則是一般的排列問題。2.7.1 問題提出 現(xiàn)在由于出現(xiàn)重復(fù)，故不同的排列計數(shù)便比較復(fù)雜。先考慮 個元素的全排列，若 個元素沒有完全一樣的元素，則應(yīng)有 種排列。若考慮 個元素 的全排列數(shù)為 ，則真正不同的排列數(shù)為2.7.2 解的分析 先討論一個具體問題：若有8個元素，其中設(shè) 重復(fù)3次， 重復(fù)2次， 重復(fù)3次。從中取r個組合，其組合數(shù)為 ，則序列

31、 的母函數(shù)為2.7.2 解的分析 從 的系數(shù)可知，這8個元素中取4個組合，其組合數(shù)為10。這10個組合可從下面展開式中得到2.7.2 解的分析 承前頁2.7.2 解的分析其中4次方項有(2-7-2)表達了從8個元素( 各3個, 2個)中取4個的組合。例如 為一個 ，3個 的組合， 為兩個 ，兩個 的組合，以此類推。2.7.2 解的分析 若研究從中取4個的不同排列總數(shù)，以 對應(yīng)的兩個兩個的不同排列為例，其不同排列數(shù)為即 六種。同樣，1個 3個 的不同排列數(shù)為 2.7.2 解的分析 即 以此類推。故從(2-7-2)式可得問題的解，其不同的排列數(shù)為2.7.3 指數(shù)型母函數(shù) 為了便于計算，利用上述特點

32、，形式地引進函數(shù)2.7.3 指數(shù)型母函數(shù) 承上頁2.7.3 指數(shù)型母函數(shù) 從(2-7-3)式計算結(jié)果可以得出：取一個的排列數(shù)為 ，取兩個的排列數(shù)為 取3個的排列數(shù)為 ，取4個的排列數(shù)為 ，如此等等。把(2-7-3)式改寫成下面形式便一目了然了。2.7.3 指數(shù)型母函數(shù) 定義：對于序列 ，函數(shù)稱為是序列 得指數(shù)型母函數(shù)2.7.3 指數(shù)型母函數(shù) 綜合上述可得如下兩個結(jié)論： (a) 若元素 有 個，元素 有 個，元素 有 個，由此；組成的n個元素的排列，不同的排列總數(shù)為其中2.7.3 指數(shù)型母函數(shù) (b) 若元素 有 個，元素 有 個，元素 有 個，由此；組成的n個元素中取r個排列，設(shè)其不同的排列數(shù)

33、為 。則序列 的指數(shù)型母函數(shù)為2.7.3 指數(shù)型母函數(shù) 與(2)中所用的方法相比，可以看出指數(shù)型母函數(shù)在解決有重復(fù)元素的排列時的優(yōu)越性。2.7.4 舉例 例1：求由兩個 ，1個 ，2個 組成的不同排列總數(shù)。 根據(jù)結(jié)論一，不同的排列總數(shù)為2.7.4 舉例 例2：由1，2，3，4四個數(shù)字組成的五位數(shù)中，要求數(shù)1出現(xiàn)次數(shù)不超過2次，但不能不出現(xiàn)； 2出現(xiàn)次數(shù)不超過1次； 3出現(xiàn)次數(shù)可達3次，也可以不出現(xiàn)；4出現(xiàn)次數(shù)為偶數(shù)。求滿足上述條件的數(shù)的個數(shù)。2.7.4 舉例 設(shè)滿足上述條件的r位數(shù)為 ，序列 的指數(shù)型母函數(shù)為2.7.4 舉例由此可見滿足條件的5位數(shù)共215個。2.7.4 舉例例3: 求1，3，

34、5，7，9五個數(shù)字組成的 位數(shù)的個數(shù)，要求其中3，7出現(xiàn)的次數(shù)為偶數(shù)，其他1，5，9出現(xiàn)次數(shù)不加限制。設(shè)滿足條件的 位的個數(shù)為 ，則序列 對應(yīng)的指數(shù)型母函數(shù)為2.7.4 舉例由于2.7.4 舉例2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例1：下圖是一邏輯回路，符號D是一延遲裝置，即在時間t輸入一個信號給延遲裝置D，在t+1時刻D將輸出同樣的信號，符號 表示加法裝置DDD輸入u輸出v圖 2-8-12.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 若在 時刻，輸入信號 求相同時刻的輸出信號 。顯然，一般的有2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 若信號輸入的序列 的母函數(shù)為 ，輸出的信號序列

35、的母函數(shù)為 ，則其中被裝置（圖 2-8-1）的特性所確定，可以看作是該裝置的傳遞函數(shù)，如圖2-8-22.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例2：由紅球兩個，白球、黃球各一個，試求有多少種不同的組合方案。設(shè)r，w，y分別代表紅球，白球，黃球。2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例由此可見，出一個球也不取的情況外，有： （a）取一個球的組合數(shù)為三，即分別取紅，白，黃，三種。 （b）取兩個球的組合數(shù)為四，即兩個紅的，一紅一黃，一紅一白，一白一黃。 （c）取三個球的組合數(shù)為三，即兩紅一黃，兩紅一白，一紅一黃一白。 （d）取四個球的組合數(shù)為一，即兩紅一黃一白。2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 令取r的組合數(shù)為 ，

36、則序列 的母函數(shù)為共有1+3+4+3+1=12種組合方式。2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例3：n個完全一樣的球放到m個有標志的盒子中，不允許有空盒，問共有多少種不同的方案？其中 由于不允許有空盒，令n個球放到m個有標志的盒子的方案數(shù)為 ，序列 對應(yīng)的母函數(shù)為 。則2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例因故二項式 中 項系數(shù)為2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例即2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例4：某單位有8個男同志，5個女同志，現(xiàn)要組織一個有數(shù)目為偶數(shù)的男同志和數(shù)目不少于2的女同志組成的小組，試求有多少種組成方式。 令 為從8位男同志中抽取出n個的允許組合數(shù)。由于要男同志的數(shù)目必須是偶數(shù)，故 。

37、2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例故數(shù)列 對應(yīng)一母函數(shù)類似的方法可得女同志的允許組合數(shù)對應(yīng)的母函數(shù)位2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 中 項的系數(shù) 為符合要求的 個人組成的小組的數(shù)目，總的組成方式數(shù)目為2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例5：10個數(shù)字（0到9）和4個四則運算符 組成的14個元素。求由其中的n個元素的排列構(gòu)成一算術(shù)表達式的個數(shù)。 因所求的n個元素的排列是算術(shù)表達式，故從左向右的最后一個符號必然是數(shù)字。而第n-1位有兩種可能，一是數(shù)字，一是運算符。如若第n-1位是十個數(shù)字之一，則前n-1位必然構(gòu)成一算術(shù)表達式。2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例如若不然

38、，即第 位是4個運算符之一，則前 位必然是算術(shù)表達式。根據(jù)以上分析，令 表 個元素排列成算術(shù)表達式的個數(shù)。則指的是從0到99的100個數(shù)，以及2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例利用遞推關(guān)系 ，得 特征多項式 。它的根是解方程2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例得2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例例6：設(shè)有n條封閉的曲線，兩兩相交于兩點，任意三條封閉曲線不相交于一點。求這樣的n條曲線把平面分割成幾個部分？ 設(shè)滿足條件的n條封閉 曲線所分割成的域的數(shù)目為 ，其中 條封閉曲線 所分割成的域的數(shù)目為圖 2-8-32.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例第n條封閉曲線和這些曲線相交于 個點，這 個點把第n條封閉曲線截成

39、 條弧，每條弧把 個域中的每個域一分為二。故新增加的域數(shù)為利用遞推關(guān)系 得2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例設(shè)2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例另解：利用歐拉公式 點數(shù)+域數(shù)-邊數(shù)=2點數(shù)= ，邊數(shù)= 點數(shù)域數(shù)=2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例例7：平面上有一點P，它是n個域的共同交界點，見圖 現(xiàn)取k種顏色對這n個域進行著色，要求相鄰兩個域著的顏色不同。試求著色的方案數(shù)。令 表示這n個域的著色方案數(shù)。無非有兩種情況： 圖 2-8-42.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例（1） 和 有相同的顏色；（2） 和 所著顏色不同。第一種情形， 域有 種顏色可用，即 域所用顏色除外；而且從 到 的著色方案，和 個域

40、的著色方案一一對應(yīng)。后一種 域有 種顏色可供使用；而且從 到 的每一個著色方案和 個域的著色方案一一對應(yīng)。2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例利用 得 的特征方程為2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例解方程得2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例例8：求下列行列式（n行n列）2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例利用行列式展開法，沿第一行展開得利用 式得 特征方程是解方程，得2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例設(shè)解方程2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例得2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例例9：求n位2進制最后三位出現(xiàn)010圖象的數(shù)的個數(shù)。對于n位2進制數(shù) 從左而右進行掃描，一當出現(xiàn)010圖象，便從這圖象后面一位從頭開始掃

41、描，例如對11位2進制數(shù)00101001010從左而右的掃描結(jié)果應(yīng)該是2-4，7-9位出現(xiàn)010圖象，即2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例而不是4-6，7-9位出現(xiàn)的010圖象，即不是 為了區(qū)別于前者起見，我們說4-6，9-11位是010，但不是“出現(xiàn)010圖象”，這作為約定。 為了找出關(guān)于數(shù)列 的第推關(guān)系，需對滿足條件的數(shù)的結(jié)構(gòu)進行分析。由于n位中除了最后三位是010已確定，其余 位可取0或1：2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例故最后3位是010的n位2進制數(shù)的個數(shù)是 。其中包含最后3位出現(xiàn)010圖象的以及在 位到第 位出現(xiàn)010圖象，而在最后3位并不出現(xiàn)010圖象的兩類數(shù)，后一種數(shù)為2.8 母

42、函數(shù)和遞推關(guān)系應(yīng)用舉例故有利用 推得特征方程為2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例設(shè)解方程組2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例得2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例例10：求n位的2進制數(shù)中最后三位才第一次出現(xiàn)010圖象的數(shù)的個數(shù)。 即求對n位2進制數(shù) 從左而右掃描，第一次在最后三位出現(xiàn)010圖象的數(shù)的個數(shù)。自然，最后三位除外任取連續(xù)三個都不會是010的。 設(shè) 表滿足條件的n位數(shù)個數(shù)，和前例類似，最后三位是010的n位2進制數(shù)共 個，2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例對這 個數(shù)分析如下。（a）包含了在最后三位第1次出現(xiàn)010圖象的個數(shù)，其個數(shù)為 ，排除了在第 到第位第1次出現(xiàn)010圖象的可能。（b）包含了

43、在第 到第 位第1次出現(xiàn)010圖象的數(shù)，其個數(shù)為 2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例（c）包含了在第 位到第 位第1次出現(xiàn)010圖象的數(shù)，其個數(shù)是2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例（d）包含了在第 位到第 位第1次出現(xiàn)010圖象的數(shù)，其個數(shù)是 ，因在第 位（打*號的格）可以取0或1兩種狀態(tài)。2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例一般可以歸納為對 ，從第 位到第 位第一次出現(xiàn)010圖象的數(shù)，其數(shù)目為 。從第 位到第 位中間的 位可以取0，1兩種值，故有 種狀態(tài)。 2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例故得遞推關(guān)系如下： 時有下面幾種狀態(tài)：排除了01010，因從左而右掃描時01010屬于前三位出現(xiàn)010圖象的。2

44、.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例請注意，遞推關(guān)系 式不是常系數(shù)遞推關(guān)系。故 時有 時有其它依此類推。2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例令2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例整理得2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例例11：解圖 電路網(wǎng)絡(luò)中的 設(shè)其中2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例圖 根據(jù)歐姆定律有圖 2-8-52.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例由于各點的電流代數(shù)和為零，2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 代入 得遞推關(guān)系或 由 點的電流代數(shù)和為零，可得2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例特征方程是設(shè)解方程組2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例得2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例12：

45、求圖2-8-6所示的n級網(wǎng)絡(luò)的等效電阻 。 所謂等效電路，相當于圖2-8-6中虛線所包圍的塊用一電阻 取代，使在兩端點 和 之間的效果一樣。R R R RR R R RR R R R R R圖 2-8-62.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 可以作為由 等效電阻如圖 所示的方式串并聯(lián)構(gòu)成的.圖 2-8-72.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例得遞推關(guān)系如下2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例令因此2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例令將 代入 得到2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例解方程組特征方程是2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例得2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例 例13：設(shè)有地址

46、從1到n的單元，用以紀錄一組信息。這個信息的每個元素都占用兩個單元，而且存放的地址是完全隨機的，因而可能出現(xiàn)兩個存放信息單元之間留下 一個空單元無法存放其他信息，求這n各單元留下空單元的平均數(shù)。2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例設(shè)這個平均數(shù)為 。 1 2 i+1 i+2 n-1 n存儲單元如上圖，設(shè)某一信息占用了第i+1，i+2兩個單元，把這組單元分割成兩個部分，一是從1到i，另一從i+3到n。由于用相鄰兩個單元的幾率相等，2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例（2-8-13）式是變系數(shù)遞推關(guān)系，可改為2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例設(shè)2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例2

47、.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例一般有2.9 排錯問題 2.9 排錯問題 n個有序的元素應(yīng)有 個不同的排列，如若一個排列使得所有的元素在原來的位置上，則稱這個排列為錯排；有的叫重排。 以1，2，3，4四個數(shù)的錯排為例，分析其結(jié)構(gòu)，找出規(guī)律性的東西來。2.9 排錯問題即 1 2的錯排是唯一的，即2 1。 1 2 3的錯排有3 1 2，2 3 1。這二者可以看作是1 2錯排，3分別與1，2換位而得的。2.9 排錯問題 1 2 3 4的錯排有4 3 2 1，4 1 2 3，4 3 1 2，3 4 1 2，3 4 2 1，2 4 1 3，2 1 4 3，3 1 4 2，2 3 4 1。 第一列是4分別與

48、1，2，3互換位置，其余兩個元素錯排，由此生成的。2.9 排錯問題 第2列是4分別與3，1，2（123的一個錯排）的每一個數(shù)互換而得到的。即2.9 排錯問題 第三列則是由另一個錯排231和4換位而得到，即2.9 排錯問題 上面的分析結(jié)果，實際上是給出一種產(chǎn)生錯排的結(jié)果。 設(shè)n個數(shù)1，2，n錯排的數(shù)目為 ，任取其中一數(shù) ，數(shù) 分別與其他的n-1個數(shù) 之一互換，其余n-2個數(shù)進行錯排，共得 個錯排。另一部分位數(shù) 以外的n-1個數(shù)進行錯排，然后 與其中每個數(shù)互換得 個錯排。2.9 排錯問題 綜合以上分析結(jié)果得遞推關(guān)系2.9 排錯問題（2-9-1）是一非常系數(shù)的遞推關(guān)系，下面提供一種解法。 由于 故得

49、關(guān)于 得遞推關(guān)系2.9 排錯問題令2.9 排錯問題可得2.10 Stirling數(shù) 2.10 Stirling數(shù) 前面見到的遞推關(guān)系都是一個參數(shù)的。Stirling數(shù)問題則不然。它導(dǎo)出的遞推關(guān)系式是兩個參數(shù)的。 （1）多項式系數(shù) n個有區(qū)別的球放到兩個有區(qū)別的盒子里，若要求第1個盒子放k個球，第二個盒子放n-k個球 方案數(shù)應(yīng)是 中 2.10 Stirling數(shù) 項的系數(shù) 依據(jù)加法法則有可把上面的討論推廣到n個有區(qū)別的球放到m個有區(qū)別的盒子里，要求m個盒子放的球數(shù)分別是 的情況，其不同方案數(shù)用2.10 Stirling數(shù)表示。 從n個有區(qū)別的球中取出 個放到第1個盒子里去，其選取方案數(shù)為 ；當?shù)?/p>

50、1個盒子的 個球選定后，第2個盒子里的 個2.10 Stirling數(shù)球則是從 個中選取的，其方案數(shù)應(yīng)為 ；第3個盒子的 個球則是從中選取，其方案數(shù)為 ；依此類推，根據(jù)乘法法則可得2.10 Stirling數(shù)2.10 Stirling數(shù)2.10 Stirling數(shù) n個有區(qū)別的球，放到m個有標志的盒子的問題，也可以考慮把n個有區(qū)別的球進行全排列。對于每一個排列依次取 個放到第1個盒子里，取 個放到第2個盒子里，最后個放到第m個盒子里。然而，放到盒子里的球不考慮球的順序，故得不同的方案數(shù)為2.10 Stirling數(shù)結(jié)果和 式一致。 稱 為多項式系數(shù)。2.10 Stirling數(shù)多項式 的展開式

51、是由 式右端的n項中，每項各取一個元素相乘而得到的。2.10 Stirling數(shù) 表達式 中共有n個因子項，令第i個因子項對應(yīng)于第i個有標志的球，從第i個因子項中取 對應(yīng)于把第i個有標志的球放到第i個盒子。 式展開的一般項表示第一個盒子有 個球，第二個盒子有個球，等等。因此 式中2.10 Stirling數(shù)項的系數(shù)應(yīng)為即2.10 Stirling數(shù) 定理： 展開式的項數(shù)等于 ，而且這些系數(shù)之和等于 證明： 展開式中的 項 和從m個 元素 中取n個作允許重復(fù)的組合一一對應(yīng)。故得 展開式的 2.10 Stirling數(shù)項數(shù)等于 。從m個中取n個作允許重復(fù)的組合的全體，對于每個球都有m個盒子可供選擇

52、，根據(jù)乘法法則有2.10 Stirling數(shù) (2)Stirling數(shù) 只準備討論其中的第二類Stirling數(shù),至于第一類的Stirling數(shù)只準備給出它的定義和遞推關(guān)系. 定義: 2.10 Stirling數(shù)稱 為第一類Stirling數(shù)顯然有2.10 Stirling數(shù) 定義: n個有區(qū)別的球放到m個相同的盒子中,要求無一空盒,其不同的方案數(shù)用 表示,稱為第二類Stirling數(shù). 例如紅,黃,藍,白四種顏色的球,放到兩個無區(qū)別的盒子里,不允許有空盒,其方案有如下七種:2.10 Stirling數(shù) 其中r表紅球,y表黃球,b表藍球,w表白球,2.10 Stirling數(shù) 定理: 第二類S

53、tirling數(shù) 有下列性質(zhì):證明:公式(a),(b),(e)是顯然的,只證(c),(d).2.10 Stirling數(shù)(c)設(shè)有n個不相同的球 從中取出球 ,其余的 個球,每個都有與 同盒,或不與 同盒兩種選擇.但必須排除一種情況,即全體與 同盒,因這時另一盒將是空盒.故實際上只有 種方案, 即2.10 Stirling數(shù) (d)n個球放到 個盒子里,不允許有一空盒,故必有一盒有兩個球,從n個有區(qū)別的球中取2個共有 種組合方案. 定理: 第二類Stirling數(shù)滿足下面的遞推關(guān)系,2.10 Stirling數(shù) 證明: 設(shè)有n個有區(qū)別的球 從中取一個球設(shè)為 .把n個球放到m個盒子無一空盒的方案

54、的全體可分為兩類。 （a） 獨占一盒，其方案數(shù)顯然為 （b） 不獨占一盒，這相當于先將剩下的 個球放到m個盒子，不允許空盒，共 2.10 Stirling數(shù)共有 種不同方案，然后將 球放進其中一盒，從乘法法則得 不獨占一盒的方案數(shù)應(yīng)為 根據(jù)加法法則有 上面證明遞推公式 的過程，也就是給出構(gòu)造所有方案的辦法。例如今將2.10 Stirling數(shù)紅、黃、藍、白、綠五個球放到無區(qū)別的兩個盒子里。故共有15種不同的方案。 先把綠球取走，余下的四個球放到兩個盒子的方案已見前面的例子。和前面一樣用r，y，b，w分別表示紅，黃，藍，白球，綠球用g表示，故得表 2.10 Stirling數(shù)表 2-10-12.

55、10 Stirling數(shù) n個球放到m個盒子里，依球和盒子是否有區(qū)別？是否允許空盒？共有 種狀態(tài)。其方案計數(shù)分別列于下表。 n個球有區(qū)別，m個盒子有區(qū)別，有空盒時方案計數(shù)為 n個球有區(qū)別，m個盒子有區(qū)別，無空盒時方案計數(shù)為2.10 Stirling數(shù) n個球有區(qū)別，m個盒子無區(qū)別，有空盒時方案計數(shù)為2.10 Stirling數(shù) n個球有區(qū)別，m個盒子無區(qū)別，無空盒時方案計數(shù)為 n個球無區(qū)別，m個盒子有區(qū)別，有空盒時方案計數(shù)為2.10 Stirling數(shù) n個球無區(qū)別，m個盒子有區(qū)別，無空盒時方案計數(shù)為2.10 Stirling數(shù) n個球無區(qū)別，m個盒子無區(qū)別，有空盒時方案計數(shù)為 的 項系數(shù)。

56、2.10 Stirling數(shù) n個球無區(qū)別，m個盒子無區(qū)別，無空盒時方案計數(shù)為 的 項系數(shù)。 2.10 Stirling數(shù) 利用 ，還可以如Pascal三角形一樣得到表2-10-3。表 2-10-3見書119頁。2.11 Catalan 數(shù) 2.11 Catalan 數(shù) 這一節(jié)討論Catalan數(shù),其遞推關(guān)系是非線性的,許多有意義的計數(shù)問題都導(dǎo)致這樣的遞推關(guān)系.本節(jié)將舉出一些,后面還將見到. 一個凸n邊形,通過不相交于n邊形的對角線,把n邊形拆分成若干三角形,不同拆分的數(shù)目用 表之. 2.11 Catalan 數(shù)例如五邊形有如下五種拆分方案，故圖 2-11-12.11 Catalan 數(shù)1.遞

57、推關(guān)系定理：2.11 Catalan 數(shù)證明： 的證明：如圖 所示，以 作為一個邊的三角形 ，將凸 邊形分割成兩部分，一部分是 邊形，圖 2-11-22.11 Catalan 數(shù)另一部分是 邊形， 即點可以是 點中任意一點。依據(jù)加法法則有2.11 Catalan 數(shù) 的證明：如圖 所示，從 點向其它 個頂點可引出 條對角線。對角線 把 邊形分割成兩個部分，因此圖 2-11-32.11 Catalan 數(shù)以 對角線作為拆分線的方案數(shù)為 可以是 中任一點，對所有這些點求和得以 取代 點也有類似的結(jié)果。但考慮到對角線有兩個頂點，同一對角線在兩個頂點分別計算了一次，2.11 Catalan 數(shù)作 式并不就給出剖分數(shù)，無疑其中是有重復(fù)的。其重復(fù)度是由于一個凸 邊形的剖分有 條對角線，而對其每一條邊計數(shù)時該剖分都計數(shù)了一次，故重復(fù)了次即 式給出的結(jié)果是 的 倍。2.11 Catalan 數(shù) 式和 式都是非線性的遞推關(guān)系。2.11 Catalan 數(shù)2.Catalan 數(shù)計算公式由 式及 ,故得2.11 Catalan 數(shù)由整理得令2.11 Catalan 數(shù)即2.11 Catalan 數(shù)2.11 Catalan 數(shù)3.母函數(shù)方法設(shè)2.11 Catalan 數(shù)即2.11 Catalan 數(shù)后面將看到只能取 才有意義. 由二項式定理2.11 Catalan 數(shù)2.11 Cata