遞歸與母函數(shù)

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

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

3、三遞推關(guān)系利用遞推關(guān)系進(jìn)行計(jì)數(shù)這個(gè)方法在算法分析中經(jīng)常用到，舉例說(shuō)明如下：例一.Hanoi問(wèn)題：這是個(gè)組合數(shù)學(xué)中的著名問(wèn)題。N個(gè)圓盤(pán)依其半徑大小，從下而上套在A柱上，如下圖示。每次只允許取一個(gè)移到柱B或C上，而且不允許大盤(pán)放在小盤(pán)上方。若要求把柱A上的n個(gè)盤(pán)移到C柱上請(qǐng)?jiān)O(shè)計(jì)一種方法來(lái)，并估計(jì)要移動(dòng)幾個(gè)盤(pán)次?，F(xiàn)在只有A、B、C三根柱子可用。A B C第7頁(yè)，共53頁(yè)，2022年，5月20日，19點(diǎn)37分，星期三遞推關(guān)系 對(duì)于一般n個(gè)圓盤(pán)的問(wèn)題， 假定n-1個(gè)盤(pán)子的轉(zhuǎn)移算法已經(jīng)確定。 先把上面的n-1個(gè)圓盤(pán)經(jīng)過(guò)C轉(zhuǎn)移到B。 第二步把A下面一個(gè)圓盤(pán)移到C上 最后再把B上的n-1個(gè)圓盤(pán)經(jīng)過(guò)A轉(zhuǎn)移到C上

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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