遞歸與母函數

1、遞歸與母函數第1頁，共53頁，2022年，5月20日，19點37分，星期三母函數與遞推關系遞推關系是計數的一個強有力的工具，特別是在做算法分析時是必需的。遞推關系的求解主要是利用母函數。當然母函數尚有其他用處，但這主要是介紹解遞推關系上的應用。例如第2頁，共53頁，2022年，5月20日，19點37分，星期三母函數x2項的系數a1a2+a1a3+ an-1an 中所有的項包括n個元素a1 , a2 , ,an中取兩個組合的全體；同理項系數包含了從n個元素a1 , a2 , ,an 中取3個元素組合的全體。以此類推。若令a1=a2= =an=1，在 x2項系數a1a2+a1a3+ an-1an中

2、每一個組合有1個貢獻，其他各項以此類推。故有：第3頁，共53頁，2022年，5月20日，19點37分，星期三母函數比較等號兩端項對應系數，可得一等式第4頁，共53頁，2022年，5月20日，19點37分，星期三相關公式令r=n，則，對原方程等號的兩端對x求導可得：第5頁，共53頁，2022年，5月20日，19點37分，星期三若已知序列 則對應的母函數G(x)便可根據定義給出。反之，如若以求得序列的母函數G(x)，則該序列也隨之確定。 例如 是序列 的母函數。 母函數稱函數G(x)是序列 的母函數 定義：對于序列 構造一函數：序列可記為第6頁，共53頁，2022年，5月20日，19點37分，星期

3、三遞推關系利用遞推關系進行計數這個方法在算法分析中經常用到，舉例說明如下：例一.Hanoi問題：這是個組合數學中的著名問題。N個圓盤依其半徑大小，從下而上套在A柱上，如下圖示。每次只允許取一個移到柱B或C上，而且不允許大盤放在小盤上方。若要求把柱A上的n個盤移到C柱上請設計一種方法來，并估計要移動幾個盤次?，F在只有A、B、C三根柱子可用。A B C第7頁，共53頁，2022年，5月20日，19點37分，星期三遞推關系 對于一般n個圓盤的問題， 假定n-1個盤子的轉移算法已經確定。 先把上面的n-1個圓盤經過C轉移到B。 第二步把A下面一個圓盤移到C上 最后再把B上的n-1個圓盤經過A轉移到C上

4、A B C第8頁，共53頁，2022年，5月20日，19點37分，星期三遞推關系算法分析：令h(n)表示n個圓盤所需要的轉移盤次。根據算法先把前面n-1個盤子轉移到B上；然后把第n個盤子轉到C上；最后再一次將B上的n-1個盤子轉移到C上。 n=2時，算法是對的，因此，n=3是算法是對的。以此類推。于是有第9頁，共53頁，2022年，5月20日，19點37分，星期三 例2. 求n位十進制數中出現偶數個5的數的個數。 先從分析n位十進制數出現偶數個5的數的結構入手 是n-1位十進制數，若含有偶數個5，則 取5以外的0，1，2，3，4，6，7，8，9九個數中的一個，若 只有奇數個5，則取 ，使 成為

5、出現偶數個5的十進制數。第10頁，共53頁，2022年，5月20日，19點37分，星期三 解法1： 令 位十進制數中出現5的數的個數， 位十進制數中出現奇數個5的數 的個數。 故有： 第11頁，共53頁，2022年，5月20日，19點37分，星期三遞推關系 解法二： n-1位的十進制數的全體共 從中去掉含有偶數個5的數，余下的便是n-1位中含有奇數個5的數。故有： 第12頁，共53頁，2022年，5月20日，19點37分，星期三 例三：從n個元素 中取r個進行允許重復的組合。假定允許重復的組合數用 表示，其結果可能有以下兩種情況。 遞推關系 1）不出現某特定元素設為 ，其組合數為 ，相當于排除

6、 后從 中取r個做允許重復的組合。 2）至少出現一個 ，取組合數為 相當于從 中取r-1個做允許重復的組合，然后再加上一個 得從n個元素中取r個允許重復的組合。第13頁，共53頁，2022年，5月20日，19點37分，星期三遞推關系依據加法原理，有第14頁，共53頁，2022年，5月20日，19點37分，星期三整數的拆分所謂整數拆分即把整數分解成若干整數的和，相當于把n個無區(qū)別的球放到n個無標志的盒子，盒子允許空著，也允許放多于一個球。整數拆分成若干整數的和，辦法不一，不同拆分法的總數叫做拆分數。第15頁，共53頁，2022年，5月20日，19點37分，星期三問題舉例 例1：若有1克、2克、3

7、克、4克的砝碼各一枚，問能稱出那幾種重量？有幾種可能方案？第16頁，共53頁，2022年，5月20日，19點37分，星期三問題舉例 從右端的母函數知可稱出從1克到10克，系數便是方案數。例如右端有 項，即稱出5克的方案有2同樣，故稱出6克的方案有2，稱出10克的方案有1第17頁，共53頁，2022年，5月20日，19點37分，星期三問題舉例 例2：求用1分、2分、3分的郵票貼出不同數值的方案數。因郵票允許重復，故母函數為 以其中為例，其系數為4，即4拆分成1、2、3之和的拆分數為4，即第18頁，共53頁，2022年，5月20日，19點37分，星期三問題舉例例3：若有1克砝碼3枚、2克砝碼4枚、

8、4克砝碼2枚的砝碼各一枚，問能稱出那幾種重量？各有幾種方案？第19頁，共53頁，2022年，5月20日，19點37分，星期三問題舉例 從母函數可以得知，用這些砝碼可以稱出從1克到63克的重量，而且辦法都是唯一的。 這問題可以推廣到證明任一十進制數n，可表示為而且是唯一的。第20頁，共53頁，2022年，5月20日，19點37分，星期三 如果 ，則是一般的排列問題。 設有n個元素，其中元素 a1 重復了n1次，元素a2 重復了n2次，ak 重復了nk 次， 從中取r個排列，求不同的排列數.指數型母函數 現在由于出現重復，故不同的排列計數便比較復雜。先考慮 n個元素的全排列，若n 個元素沒有完全一

9、樣的元素，則應有n! 種排列。若考慮ni 個元素ai的全排列數為 ni!，則真正不同的排列數為第21頁，共53頁，2022年，5月20日，19點37分，星期三解的分析先討論一個具體問題：若有8個元素，其中設a1重復3次，a2重復2次，a3重復3次。從中取r個組合，其組合數為cr ，則序列c1 ,c2 , c3 , c4 , c5 , c6 , c7 , c8的母函數為:第22頁，共53頁，2022年，5月20日，19點37分，星期三解的分析 從x4的系數可知，這8個元素中取4個組合，其組合數為10。這10個組合可從下面展開式中得到第23頁，共53頁，2022年，5月20日，19點37分，星期三

10、解的分析其中4次方項有表達了從8個元素(a1a3各3個,a22個)中取4個的組合。例如x1x33為一個a1，3個a3的組合，x12x32 兩個a1，兩個a3的組合，以此類推。第24頁，共53頁，2022年，5月20日，19點37分，星期三解的分析 若研究從中取4個的不同排列總數，以 對應的兩個兩個的不同排列為例，其不同排列數為即 六種。同樣，1個 3個 的不同排列數為 第25頁，共53頁，2022年，5月20日，19點37分，星期三解的分析 即 以此類推。故可得問題的解，其不同的排列數為第26頁，共53頁，2022年，5月20日，19點37分，星期三指數型母函數 為了便于計算，利用上述特點，形

11、式地引進函數第27頁，共53頁，2022年，5月20日，19點37分，星期三指數型母函數式計算結果可以得出：取一個的排列數為3，取兩個的排列數為2*9/2,取3個的排列數為3!*14/3=28,取4個的排列數4!*35/12=70，如此等等。第28頁，共53頁，2022年，5月20日，19點37分，星期三指數型母函數 定義：對于序列 ，函數稱為是序列 得指數型母函數第29頁，共53頁，2022年，5月20日，19點37分，星期三指數型母函數若元素 a1 有 n1 個，元素 a2 有 n2 個，元素 ak 有 nk個，由此；組成的n個元素中取r個排列，設其不同的排列數為Pr 。則序列P0, P1

12、, Pn, 的指數型母函數為:第30頁，共53頁，2022年，5月20日，19點37分，星期三應用舉例 例1：由紅球兩個，白球、黃球各一個，試求有多少種不同的組合方案。設r，w，y分別代表紅球，白球，黃球。第31頁，共53頁，2022年，5月20日，19點37分，星期三應用舉例由此可見，出一個球也不取的情況外，有： （a）取一個球的組合數為三，即分別取紅，白，黃，三種。 （b）取兩個球的組合數為四，即兩個紅的，一紅一黃，一紅一白，一白一黃。 （c）取三個球的組合數為三，即兩紅一黃，兩紅一白，一紅一黃一白。 （d）取四個球的組合數為一，即兩紅一黃一白。第32頁，共53頁，2022年，5月20日，

13、19點37分，星期三應用舉例 令取r的組合數為 ，則序列 的母函數為共有1+3+4+3+1=12種組合方式。第33頁，共53頁，2022年，5月20日，19點37分，星期三應用舉例 例2：某單位有8個男同志，5個女同志，現要組織一個有數目為偶數的男同志和數目不少于2的女同志組成的小組，試求有多少種組成方式。 令 為從8位男同志中抽取出n個的允許組合數。由于要男同志的數目必須是偶數，故 。第34頁，共53頁，2022年，5月20日，19點37分，星期三2.8 母函數和遞推關系應用舉例故數列 對應一母函數類似的方法可得女同志的允許組合數對應的母函數位第35頁，共53頁，2022年，5月20日，19

14、點37分，星期三應用舉例第36頁，共53頁，2022年，5月20日，19點37分，星期三2.8 母函數和遞推關系應用舉例 中 項的系數 為符合要求的 個人組成的小組的數目，總的組成方式數目為第37頁，共53頁，2022年，5月20日，19點37分，星期三應用舉例 例3：10個數字（0到9）和4個四則運算符 組成的14個元素。求由其中的n個元素的排列構成一算術表達式的個數。 因所求的n個元素的排列是算術表達式，故從左向右的最后一個符號必然是數字。而第n-1位有兩種可能，一是數字，一是運算符。如若第n-1位是十個數字之一，則前n-1位必然構成一算術表達式。第38頁，共53頁，2022年，5月20日

15、，19點37分，星期三應用舉例 如若不然，即第 位是4個運算符之一，則前 位必然是算術表達式。根據以上分析，令 表n個元素排列成算術表達式的個數。則指的是從0到99的100個數，以及第39頁，共53頁，2022年，5月20日，19點37分，星期三例4：設有n條封閉的曲線，兩兩相交于兩點，任意三條封閉曲線不相交于一點。求這樣的n條曲線把平面分割成幾個部分？ 設滿足條件的n條封閉 曲線所分割成的域的數目為 an ，其中n-1條封閉曲線 所分割成的域的數目為an-1應用舉例第40頁，共53頁，2022年，5月20日，19點37分，星期三第n條封閉曲線和這些曲線相交于2(n-1)個點，這2(n-1)個

16、點把第n條封閉曲線截成2(n-1)條弧，每條弧把2(n-1)個域中的每個域一分為二。故新增加的域數為2(n-1).應用舉例第41頁，共53頁，2022年，5月20日，19點37分，星期三母函數和遞推關系應用舉例例5：求n位2進制最后三位出現010圖象的數的個數。對于n位2進制數 從左而右進行掃描，一當出現010圖象，便從這圖象后面一位從頭開始掃描，例如對11位2進制數從左而右的掃描結果應該是2-4，7-9位出現010圖象，即第42頁，共53頁，2022年，5月20日，19點37分，星期三母函數和遞推關系應用舉例而不是4-6，7-9位出現的010圖象，即不是 為了區(qū)別于前者起見，我們說4-6，9

17、-11位是010，但不是“出現010圖象”，這作為約定。 為了找出關于數列 的第推關系，需對滿足條件的數的結構進行分析。由于n位中除了最后三位是010已確定，其余 位可取0或1：第43頁，共53頁，2022年，5月20日，19點37分，星期三2.8 母函數和遞推關系應用舉例故最后3位是010的n位2進制數的個數是 。其中包含最后3位出現010圖象的以及在 位到第 位出現010圖象，而在最后3位并不出現010圖象的兩類數，后一種數為第44頁，共53頁，2022年，5月20日，19點37分，星期三母函數和遞推關系應用舉例故有第45頁，共53頁，2022年，5月20日，19點37分，星期三錯排問題

18、n個有序的元素應有 個不同的排列，如若一個排列使得所有的元素在原來的位置上，則稱這個排列為錯排；有的叫重排。 以1，2，3，4四個數的錯排為例，分析其結構，找出規(guī)律性的東西來。第46頁，共53頁，2022年，5月20日，19點37分，星期三錯排問題即 1 2的錯排是唯一的，即2 1。 1 2 3的錯排有3 1 2，2 3 1。這二者可以看作是1 2錯排，3分別與1，2換位而得的。第47頁，共53頁，2022年，5月20日，19點37分，星期三錯排問題 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分別與1，2，3互換位置，其余兩個元素錯排，由此生成的。第48頁，共53頁，2022年，5月20日，19點37分，星期三錯排問題 第2列是4分別與3，1，2（123的一個錯排）的每一個數互換而得到的。即第49頁，共53頁，2022年，5月20日，19點37分，星期三錯排問題 第三列則是由另