遞歸與母函數(shù)

組合數(shù)學(xué)

---母函數(shù)與遞推

長沙市雅禮中學(xué)朱全民母函數(shù)與遞推關(guān)系遞推關(guān)系是計數(shù)的一個強(qiáng)有力的工具，特別是在做算法分析時是必需的。遞推關(guān)系的求解主要是利用母函數(shù)。當(dāng)然母函數(shù)尚有其他用處，但這主要是介紹解遞推關(guān)系上的應(yīng)用。例如母函數(shù)x2項的系數(shù)a1a2+a1a3+…+an-1an

中所有的項包括n個元素a1,a2,…,an中取兩個組合的全體；同理項系數(shù)包含了從n個元素a1,a2,…,an

中取3個元素組合的全體。以此類推。若令a1=a2=

…=an=1，在x2項系數(shù)a1a2+a1a3+…+an-1an中每一個組合有1個貢獻(xiàn)，其他各項以此類推。故有：母函數(shù)比較等號兩端項對應(yīng)系數(shù)，可得一等式相關(guān)公式令r=n，則，對原方程等號的兩端對x求導(dǎo)可得：若已知序列則對應(yīng)的母函數(shù)G(x)便可根據(jù)定義給出。反之，如若以求得序列的母函數(shù)G(x)，則該序列也隨之確定。

例如是序列的母函數(shù)。

母函數(shù)稱函數(shù)G(x)是序列的母函數(shù)

定義：對于序列構(gòu)造一函數(shù)：序列可記為遞推關(guān)系利用遞推關(guān)系進(jìn)行計數(shù)這個方法在算法分析中經(jīng)常用到，舉例說明如下：例一.Hanoi問題：這是個組合數(shù)學(xué)中的著名問題。N個圓盤依其半徑大小，從下而上套在A柱上，如下圖示。每次只允許取一個移到柱B或C上，而且不允許大盤放在小盤上方。若要求把柱A上的n個盤移到C柱上請設(shè)計一種方法來，并估計要移動幾個盤次?，F(xiàn)在只有A、B、C三根柱子可用。ABC遞推關(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上ABC遞推關(guān)系算法分析：令h(n)表示n個圓盤所需要的轉(zhuǎn)移盤次。根據(jù)算法先把前面n-1個盤子轉(zhuǎn)移到B上；然后把第n個盤子轉(zhuǎn)到C上；最后再一次將B上的n-1個盤子轉(zhuǎn)移到C上。

n=2時，算法是對的，因此，n=3是算法是對的。以此類推。于是有

例2.求n位十進(jìn)制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)。

先從分析n位十進(jìn)制數(shù)出現(xiàn)偶數(shù)個5的數(shù)的結(jié)構(gòu)入手是n-1位十進(jìn)制數(shù)，若含有偶數(shù)個5，則取5以外的0，1，2，3，4，6，7，8，9九個數(shù)中的一個，若只有奇數(shù)個5，則取，使成為出現(xiàn)偶數(shù)個5的十進(jìn)制數(shù)。

解法1：

令位十進(jìn)制數(shù)中出現(xiàn)5的數(shù)的個數(shù)，位十進(jìn)制數(shù)中出現(xiàn)奇數(shù)個5的數(shù)

的個數(shù)。故有：

遞推關(guān)系

解法二：

n-1位的十進(jìn)制數(shù)的全體共從中去掉含有偶數(shù)個5的數(shù)，余下的便是n-1位中含有奇數(shù)個5的數(shù)。故有：

例三：從n個元素中取r個進(jìn)行允許重復(fù)的組合。假定允許重復(fù)的組合數(shù)用表示，其結(jié)果可能有以下兩種情況。

遞推關(guān)系1）不出現(xiàn)某特定元素設(shè)為，其組合數(shù)為，相當(dāng)于排除后從中取r個做允許重復(fù)的組合。

2）至少出現(xiàn)一個，取組合數(shù)為相當(dāng)于從中取r-1個做允許重復(fù)的組合，然后再加上一個得從n個元素中取r個允許重復(fù)的組合。遞推關(guān)系依據(jù)加法原理，有整數(shù)的拆分所謂整數(shù)拆分即把整數(shù)分解成若干整數(shù)的和，相當(dāng)于把n個無區(qū)別的球放到n個無標(biāo)志的盒子，盒子允許空著，也允許放多于一個球。整數(shù)拆分成若干整數(shù)的和，辦法不一，不同拆分法的總數(shù)叫做拆分?jǐn)?shù)。問題舉例

例1：若有1克、2克、3克、4克的砝碼各一枚，問能稱出那幾種重量？有幾種可能方案？問題舉例

從右端的母函數(shù)知可稱出從1克到10克，系數(shù)便是方案數(shù)。例如右端有項，即稱出5克的方案有2同樣，故稱出6克的方案有2，稱出10克的方案有1問題舉例

例2：求用1分、2分、3分的郵票貼出不同數(shù)值的方案數(shù)。因郵票允許重復(fù)，故母函數(shù)為

以其中為例，其系數(shù)為4，即4拆分成1、2、3之和的拆分?jǐn)?shù)為4，即問題舉例例3：若有1克砝碼3枚、2克砝碼4枚、4克砝碼2枚的砝碼各一枚，問能稱出那幾種重量？各有幾種方案？問題舉例

從母函數(shù)可以得知，用這些砝碼可以稱出從1克到63克的重量，而且辦法都是唯一的。

這問題可以推廣到證明任一十進(jìn)制數(shù)n，可表示為而且是唯一的。

如果，則是一般的排列問題。

設(shè)有n個元素，其中元素a1

重復(fù)了n1次，元素a2

重復(fù)了n2次，…，ak重復(fù)了nk

次，從中取r個排列，求不同的排列數(shù).指數(shù)型母函數(shù)

現(xiàn)在由于出現(xiàn)重復(fù)，故不同的排列計數(shù)便比較復(fù)雜。先考慮

n個元素的全排列，若n

個元素沒有完全一樣的元素，則應(yīng)有n!種排列。若考慮ni

個元素ai的全排列數(shù)為ni!，則真正不同的排列數(shù)為解的分析先討論一個具體問題：若有8個元素，其中設(shè)a1重復(fù)3次，a2重復(fù)2次，a3重復(fù)3次。從中取r個組合，其組合數(shù)為cr

，則序列c1,c2,

c3,

c4,

c5,

c6,c7,

c8的母函數(shù)為:解的分析

從x4的系數(shù)可知，這8個元素中取4個組合，其組合數(shù)為10。這10個組合可從下面展開式中得到解的分析其中4次方項有表達(dá)了從8個元素(a1a3各3個,a22個)中取4個的組合。例如x1x33為一個a1，3個a3的組合，x12x32

兩個a1，兩個a3的組合，以此類推。解的分析

若研究從中取4個的不同排列總數(shù)，以對應(yīng)的兩個兩個的不同排列為例，其不同排列數(shù)為即六種。同樣，1個3個的不同排列數(shù)為解的分析

即以此類推。故可得問題的解，其不同的排列數(shù)為指數(shù)型母函數(shù)

為了便于計算，利用上述特點，形式地引進(jìn)函數(shù)指數(shù)型母函數(shù)式計算結(jié)果可以得出：取一個的排列數(shù)為3，取兩個的排列數(shù)為2*9/2,取3個的排列數(shù)為3!*14/3=28,取4個的排列數(shù)4!*35/12=70，如此等等。指數(shù)型母函數(shù)

定義：對于序列，函數(shù)稱為是序列得指數(shù)型母函數(shù)指數(shù)型母函數(shù)若元素a1

有n1

個，元素a2

有n2

個，……，元素ak

有nk個，由此；組成的n個元素中取r個排列，設(shè)其不同的排列數(shù)為Pr

。則序列P0,P1,…Pn,的指數(shù)型母函數(shù)為:應(yīng)用舉例

例1：由紅球兩個，白球、黃球各一個，試求有多少種不同的組合方案。設(shè)r，w，y分別代表紅球，白球，黃球。應(yīng)用舉例由此可見，出一個球也不取的情況外，有：

（a）取一個球的組合數(shù)為三，即分別取紅，白，黃，三種。

（b）取兩個球的組合數(shù)為四，即兩個紅的，一紅一黃，一紅一白，一白一黃。

（c）取三個球的組合數(shù)為三，即兩紅一黃，兩紅一白，一紅一黃一白。

（d）取四個球的組合數(shù)為一，即兩紅一黃一白。應(yīng)用舉例

令取r的組合數(shù)為，則序列的母函數(shù)為共有1+3+4+3+1=12種組合方式。應(yīng)用舉例

例2：某單位有8個男同志，5個女同志，現(xiàn)要組織一個有數(shù)目為偶數(shù)的男同志和數(shù)目不少于2的女同志組成的小組，試求有多少種組成方式。

令為從8位男同志中抽取出n個的允許組合數(shù)。由于要男同志的數(shù)目必須是偶數(shù)，故?！?.8母函數(shù)和遞推關(guān)系應(yīng)用舉例故數(shù)列對應(yīng)一母函數(shù)類似的方法可得女同志的允許組合數(shù)對應(yīng)的母函數(shù)位應(yīng)用舉例§2.8母函數(shù)和遞推關(guān)系應(yīng)用舉例

中項的系數(shù)為符合要求的個人組成的小組的數(shù)目，總的組成方式數(shù)目為應(yīng)用舉例

例3：10個數(shù)字（0到9）和4個四則運算符組成的14個元素。求由其中的n個元素的排列構(gòu)成一算術(shù)表達(dá)式的個數(shù)。

因所求的n個元素的排列是算術(shù)表達(dá)式，故從左向右的最后一個符號必然是數(shù)字。而第n-1位有兩種可能，一是數(shù)字，一是運算符。如若第n-1位是十個數(shù)字之一，則前n-1位必然構(gòu)成一算術(shù)表達(dá)式。應(yīng)用舉例

如若不然，即第位是4個運算符之一，則前位必然是算術(shù)表達(dá)式。根據(jù)以上分析，令表n個元素排列成算術(shù)表達(dá)式的個數(shù)。則指的是從0到99的100個數(shù)，以及

例4：設(shè)有n條封閉的曲線，兩兩相交于兩點，任意三條封閉曲線不相交于一點。求這樣的n條曲線把平面分割成幾個部分？ 設(shè)滿足條件的n條封閉曲線所分割成的域的數(shù)目為

an

，其中n-1條封閉曲線

所分割成的域的數(shù)目為an-1應(yīng)用舉例第n條封閉曲線和這些曲線相交于2(n-1)個點，這2(n-1)個點把第n條封閉曲線截成2(n-1)條弧，每條弧把2(n-1)個域中的每個域一分為二。故新增加的域數(shù)為2(n-1).應(yīng)用舉例母函數(shù)和遞推關(guān)系應(yīng)用舉例例5：求n位2進(jìn)制最后三位出現(xiàn)010圖象的數(shù)的個數(shù)。 對于n位2進(jìn)制數(shù)從左而右進(jìn)行掃描，一當(dāng)出現(xiàn)010圖象，便從這圖象后面一位從頭開始掃描，例如對11位2進(jìn)制數(shù)00101001010從左而右的掃描結(jié)果應(yīng)該是2-4，7-9位出現(xiàn)010圖象，即母函數(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)進(jìn)行分析。由于n位中除了最后三位是010已確定，其余位可取0或1：§2.8母函數(shù)和遞推關(guān)系應(yīng)用舉例故最后3位是010的n位2進(jìn)制數(shù)的個數(shù)是。其中包含最后3位出現(xiàn)010圖象的以及在位到第位出現(xiàn)010圖象，而在最后3位并不出現(xiàn)010圖象的兩類數(shù)，后一種數(shù)為母函數(shù)和遞推關(guān)系應(yīng)用舉例故有錯排問題

n個有序的元素應(yīng)有個不同的排列，如若一個排列使得所有的元素在原來的位置上，則稱這個排列為錯排；有的叫重排。 以1，2，3，4四個數(shù)的錯排為例，分析其結(jié)構(gòu)，找