1、組合數(shù)學(xué)組合數(shù)學(xué) -母函數(shù)與遞推母函數(shù)與遞推長沙市雅禮中學(xué)朱 全 民 母函數(shù)與遞推關(guān)系母函數(shù)與遞推關(guān)系v遞推關(guān)系是計數(shù)的一個強有力的工具，特別是在做算法分析時是必需的。遞推關(guān)系的求解主要是利用母函數(shù)。當(dāng)然母函數(shù)尚有其他用處，但這主要是介紹解遞推關(guān)系上的應(yīng)用。例如nnnnnnnxaaaaxaaaaaaxaaaxaxaxa1212131212121.).().(1)1).(1 ( )1 (母函數(shù)vx2項的系數(shù)項的系數(shù)a1a2+a1a3+ an-1an 中所有的項包括中所有的項包括n個個元素元素a1 , a2 , ,an中取中取兩個兩個組合的全體；同理項系組合的全體；同理項系數(shù)包含了從數(shù)包含了從n個

2、元素個元素a1 , a2 , ,an 中取中取3個元素組合個元素組合的全體。以此類推。的全體。以此類推。v若令若令a1=a2= =an=1 1，在，在 x2項系數(shù)項系數(shù)a1a2+a1a3+ an-1an中每一個組合有中每一個組合有1 1個貢獻，其他各項以此類推。個貢獻，其他各項以此類推。故有：故有：nnxnnCxnCxnCx),()2 ,() 1 ,(1)1 (2母函數(shù)nmnmxxx)1 ()1 ()1 ( nmmnxnmnmCxnmCnmCxmmCxmCmCxnnCxnCnC),( ) 1 ,()0 ,(),() 1 ,()0 ,( ),() 1 ,()0 ,( 比較等號兩端項對應(yīng)系數(shù)，可得

3、一等式比較等號兩端項對應(yīng)系數(shù)，可得一等式)0 ,(),( ) 1,() 1 ,( ),()0 ,(),(nCrmCrnCmCrnCmCrnmC相關(guān)公式12*),(),( ) 1 ,() 1 ,( )0 ,()0 ,(),(nnnnCmmCnCmCnCmCnnmC令令r=n，則，則，對原方程等號的兩端對對原方程等號的兩端對x求導(dǎo)可得：求導(dǎo)可得： 2 ),() 3 ,(3)2 ,(2) 1 ,(1nnnnnCnCnCnC若已知序列 則對應(yīng)的母函數(shù)G(x)便可根據(jù)定義給出。反之，如若以求得序列的母函數(shù)G(x)，則該序列也隨之確定。 ,210aaa 例如 是序列 的母函數(shù)。 ),(,),1 ,(),0

4、 ,(nnCnCnCnx)1 ( 母函數(shù)母函數(shù)稱函數(shù)G(x)是序列 的母函數(shù) 定義：定義：對于序列 構(gòu)造一函數(shù)：,210aaa,)(2210 xaxaaxG,210aaa,210aaana序列可記為遞推關(guān)系遞推關(guān)系v利用遞推關(guān)系進行計數(shù)這個方法在算法分析中經(jīng)常用到，舉例說明如下：v例一.Hanoi問題：這是個組合數(shù)學(xué)中的著名問題。N個圓盤依其半徑大小，從下而上套在A柱上，如下圖示。每次只允許取一個移到柱B或C上，而且不允許大盤放在小盤上方。若要求把柱A上的n個盤移到C柱上請設(shè)計一種方法來，并估計要移動幾個盤次?，F(xiàn)在只有A、B、C三根柱子可用。A B C遞推關(guān)系遞推關(guān)系z 對于一般n個圓盤的問題

5、，v 假定n-1個盤子的轉(zhuǎn)移算法已經(jīng)確定。z 先把上面的n-1個圓盤經(jīng)過C轉(zhuǎn)移到B。z 第二步把A下面一個圓盤移到C上z 最后再把B上的n-1個圓盤經(jīng)過A轉(zhuǎn)移到C上 A B C 遞推關(guān)系遞推關(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是算法是對的。以此類推。于是有 1) 1 ( , 1) 1(2)(hnhnh 例例2. 求求n位十進制數(shù)中出現(xiàn)偶數(shù)個位十進制數(shù)中出現(xiàn)偶數(shù)個5的數(shù)的個數(shù)。的數(shù)的個數(shù)。 先從分析n位十進制數(shù)出現(xiàn)偶數(shù)個5的數(shù)

6、的結(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ù)。121nppp1np121nppp5npnnpppp121 解法解法1： 令 位十進制數(shù)中出現(xiàn)5的數(shù)的個數(shù)， 位十進制數(shù)中出現(xiàn)奇數(shù)個5的數(shù) 的個數(shù)。 故有： nannbn119nnnbaa119nnnabb1 , 811ba遞推關(guān)系遞推關(guān)系 解法二：解法二： n-1位的十進制數(shù)的全體共 從中去掉含有偶數(shù)個5的數(shù)，余下的便是n-1位中含有奇數(shù)個5的數(shù)。故有： 2109n121111099nnnnnnabbaa8 ,1098 12

7、1aaannn 例三：例三：從n個元素 中取r個進行允許重復(fù)的組合。假定允許重復(fù)的組合數(shù)用 表示，其結(jié)果可能有以下兩種情況。 遞推關(guān)系遞推關(guān)系naaa,21),(rnC 1 1）不出現(xiàn)某特定元素設(shè)為）不出現(xiàn)某特定元素設(shè)為 ，其組合數(shù)為，其組合數(shù)為 ，相當(dāng)于排除，相當(dāng)于排除 后從后從 中取中取r r個做允許重個做允許重復(fù)的組合。復(fù)的組合。 1a), 1(rnC1anaa,2 2）至少出現(xiàn)一個 ，取組合數(shù)為 相當(dāng)于從 中取r-1個做允許重復(fù)的組合，然后再加上一個 得從n個元素中取r個允許重復(fù)的組合。1a) 1,(rnC1anaaa,21遞推關(guān)系遞推關(guān)系v依據(jù)加法原理，有), 1() 1,(),(r

8、nCrnCrnC1) 1 , 1(,) 1 ,(nnCnnC1)0 ,(nC整數(shù)的拆分整數(shù)的拆分v所謂整數(shù)拆分即把整數(shù)分解成若干整數(shù)的所謂整數(shù)拆分即把整數(shù)分解成若干整數(shù)的和，相當(dāng)于把和，相當(dāng)于把n n個無區(qū)別的球放到個無區(qū)別的球放到n n個無標個無標志的盒子，盒子允許空著，也允許放多于志的盒子，盒子允許空著，也允許放多于一個球。整數(shù)拆分成若干整數(shù)的和，辦法一個球。整數(shù)拆分成若干整數(shù)的和，辦法不一，不同拆分法的總數(shù)叫做拆分數(shù)。不一，不同拆分法的總數(shù)叫做拆分數(shù)。問題舉例問題舉例 例例1 1：若有：若有1 1克、克、2 2克、克、3 3克、克、4 4克的砝碼各一枚，克的砝碼各一枚，問能稱出那幾種重量

9、？有幾種可能方案？問能稱出那幾種重量？有幾種可能方案？109876543274332432 1)1)(1 ()1)(1)(1)(1 (xxxxxxxxxxxxxxxxxxxx問題舉例問題舉例 從右端的母函數(shù)知可稱出從1克到10克，系數(shù)便是方案數(shù)。例如右端有 項，即稱出5克的方案有241325同樣，432110243216故稱出6克的方案有2，稱出10克的方案有1問題舉例問題舉例 例例2：求用1分、2分、3分的郵票貼出不同數(shù)值的方案數(shù)。因郵票允許重復(fù)，故母函數(shù)為)1 ( )1)(1 ()(63422xxxxxxxG 以其中為例，其系數(shù)為4，即4拆分成1、2、3之和的拆分數(shù)為4，即22312111

10、1114問題舉例問題舉例例例3 3：若有：若有1 1克砝碼克砝碼3 3枚、枚、2 2克砝碼克砝碼4 4枚、枚、4 4克砝碼克砝碼2 2枚的砝碼各一枚，問能枚的砝碼各一枚，問能稱出那幾種重量？各有幾種方案？稱出那幾種重量？各有幾種方案？191817161514131211109876543284111098765432848642322233 445555 4433221 )1)(222 222221 ( )1 ( )1)(1 ()(xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxG問題舉例問題舉例 從母函數(shù)可以得知，用這些砝碼可以稱出從1克到63克的重量，而

11、且辦法都是唯一的。 這問題可以推廣到證明任一十進制數(shù)這問題可以推廣到證明任一十進制數(shù)n，可表示為可表示為0 , 10 ,20kaankkkk而且是唯一的。而且是唯一的。 如果如果 ，則是一般的排列問題。，則是一般的排列問題。 設(shè)有設(shè)有n個元素，其中元素個元素，其中元素 a1 重復(fù)了重復(fù)了n1次，元素次，元素a2 重復(fù)重復(fù)了了n2次，次，ak 重復(fù)了重復(fù)了nk 次，次， 從中取從中取r個排列，求不同的排列數(shù)個排列，求不同的排列數(shù).指數(shù)型母函數(shù)指數(shù)型母函數(shù)knnnn21121knnn 現(xiàn)在由于出現(xiàn)重復(fù)，故不同的排列計數(shù)便比較復(fù)雜。先考現(xiàn)在由于出現(xiàn)重復(fù)，故不同的排列計數(shù)便比較復(fù)雜。先考慮慮 n個元素

12、的全排列，若個元素的全排列，若n 個元素沒有完全一樣的元素，則個元素沒有完全一樣的元素，則應(yīng)有應(yīng)有n! 種排列。若考慮種排列。若考慮ni 個元素個元素ai的全排列數(shù)為的全排列數(shù)為 ni!，則真正，則真正不同的排列數(shù)為不同的排列數(shù)為!21knnnn解的分析解的分析v先討論一個具體問題：若有先討論一個具體問題：若有8 8個元素，其中設(shè)個元素，其中設(shè)a a1 1重復(fù)重復(fù)3 3次，次，a a2 2重復(fù)重復(fù)2 2次，次，a a3 3重復(fù)重復(fù)3 3次。從中取次。從中取r r個組合，其個組合，其組合數(shù)為組合數(shù)為c cr r ，則序列，則序列c c1 1 ,c,c2 2 , , c c3 3 , , c c4

13、 4 , , c c5 5 , , c c6 6 , c, c7 7 , , c c8 8的母函數(shù)為的母函數(shù)為: :876543232543232232369109631 )1 ( )23321 ( )1)(1)(1 ()(xxxxxxxxxxxxxxxxxxxxxxxxxG解的分析解的分析)1 ( )()( )()(1 )1)(1)(1 ( 332332231222123122122131222121213323322231211xxxxxxxxxxxxxxxxxxxxxxxxxxxx 從x4的系數(shù)可知，這8個元素中取4個組合，其組合數(shù)為10。這10個組合可從下面展開式中得到) () ()

14、()1 ( 12221331322132213312322232123213323313323223132232132122122131333231222121321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx解的分析解的分析其中4次方項有 222133132213221331232223212321332331xxxxxxxxxxxxxxxxxxxxxxx表達了從8個元素(a1a3各3個,a22個)中取4個的組合。例如x1x33為一個a1，3個a3的組合，x12x32 兩個a1，兩個a3的組合，以此類推。解的分析解的分析 若研究從中

15、取4個的不同排列總數(shù)，以 對應(yīng)的兩個兩個的不同排列為例，其不同排列數(shù)為2321xx6! 2 ! 2! 4即 六種。同樣，1個 3個 的不同排列數(shù)為 ,3311aaaa,1331aaaa,3131aaaa,1313aaaa,1133aaaa,3113aaaa1a3a4! 3! 4解的分析解的分析 即 以此類推。故可得問題的解，其不同的排列數(shù)為,3331aaaa,1333aaaa,3133aaaa,3313aaaa70361816! 3 ! 2 ! 2! 3! 23! 33! 2! 24! 4)! 23! 2 ! 23! 34( ! 4)! 2 ! 21! 1 ! 31! 1 ! 2 ! 11!

16、1 ! 1 ! 21 ! 1 ! 31! 2 ! 21! 2 ! 1 ! 11! 2 ! 21! 3 ! 11! 3 ! 11( ! 4指數(shù)型母函數(shù)指數(shù)型母函數(shù) 為了便于計算，利用上述特點，形式地引進函數(shù))! 3! 2! 11 ( )! 2! 11)(! 3! 2! 11 ()(32232xxxxxxxxxGe 7217287235 121712353142931 )61211 ( )1211256722(1 8765432325432xxxxxxxxxxxxxxxx指數(shù)型母函數(shù)指數(shù)型母函數(shù)v式計算結(jié)果可以得出：取一個的排列數(shù)為式計算結(jié)果可以得出：取一個的排列數(shù)為3 3，取兩個的排列數(shù)為取兩個

17、的排列數(shù)為2 2* *9/2,9/2,取取3 3個的排列數(shù)為個的排列數(shù)為3!3!* *14/3=28,14/3=28,取取4 4個的排列數(shù)個的排列數(shù)4!4!* *35/12=7035/12=70，如此等等。如此等等。)472( ! 8560! 7560! 6350 ! 5170! 470! 328! 291!31! )(8765432xxxxxxxxxGe指數(shù)型母函數(shù)指數(shù)型母函數(shù) 定義：定義：對于序列 ，函數(shù),210aaakkexkaxaxaxaaxG! ! 3! 21! )(332210稱為是序列 得指數(shù)型母函數(shù),210aaa指數(shù)型母函數(shù)指數(shù)型母函數(shù)v若元素 a1 有 n1 個，元素 a2

18、有 n2 個，元素 ak 有 nk個，由此；組成的n個元素中取r個排列，設(shè)其不同的排列數(shù)為Pr 。則序列P0, P1, Pn, 的指數(shù)型母函數(shù)為:)! 21!1 ( )! 21!1 ( )! 21!1 ( )(2221221knnnenxxxnxxxnxxxxGk應(yīng)用舉例應(yīng)用舉例 例例1 1：由紅球兩個，白球、黃球各一個，：由紅球兩個，白球、黃球各一個，試求有多少種不同的組合方案。試求有多少種不同的組合方案。設(shè)設(shè)r r，w w，y y分別代表紅球，白球，黃球。分別代表紅球，白球，黃球。ywrrywwryrywrwryrwyrywwyrrywrr222222)( )()(1)1)(1 ()1)(

19、1)(1 (應(yīng)用舉例應(yīng)用舉例由此可見，出一個球也不取的情況外，有：由此可見，出一個球也不取的情況外，有： （a）取一個球的組合數(shù)為三，即分別?。┤∫粋€球的組合數(shù)為三，即分別取紅，白，黃，三種。紅，白，黃，三種。 （b）取兩個球的組合數(shù)為四，即兩個紅）取兩個球的組合數(shù)為四，即兩個紅的，一紅一黃，一紅一白，一白一黃。的，一紅一黃，一紅一白，一白一黃。 （c）取三個球的組合數(shù)為三，即兩紅一）取三個球的組合數(shù)為三，即兩紅一黃，兩紅一白，一紅一黃一白。黃，兩紅一白，一紅一黃一白。 （d）取四個球的組合數(shù)為一，即兩紅一）取四個球的組合數(shù)為一，即兩紅一黃一白。黃一白。應(yīng)用舉例應(yīng)用舉例 令取r的組合數(shù)為 ，則

20、序列 的母函數(shù)為rc43210,ccccc432223431 )1)(1 ()(xxxxxxxxG共有共有1+3+4+3+1=121+3+4+3+1=12種組合方式。種組合方式。應(yīng)用舉例應(yīng)用舉例 例2：某單位有8個男同志，5個女同志，現(xiàn)要組織一個有數(shù)目為偶數(shù)的男同志和數(shù)目不少于2的女同志組成的小組，試求有多少種組成方式。 令 為從8位男同志中抽取出n個的允許組合數(shù)。由于要男同志的數(shù)目必須是偶數(shù)，故 。na,28)2 , 8(, 1, 0207531Caaaaaa1,28)6 , 8(,70)4 , 8(864aCaCa2.8 2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例母函數(shù)和遞推關(guān)系應(yīng)用舉例故數(shù)列 對應(yīng)

21、一母函數(shù)8210,aaaa86422870281)(xxxxxA類似的方法可得女同志的允許組合數(shù)對應(yīng)的類似的方法可得女同志的允許組合數(shù)對應(yīng)的母函數(shù)位母函數(shù)位543251010)(xxxxxB應(yīng)用舉例應(yīng)用舉例131211109876543254328642538 150350630728 8402812851010 )51010( )2870281 ( )()()(xxxxxxxxxxxxxxxxxxxxxBxAxC2.8 2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例母函數(shù)和遞推關(guān)系應(yīng)用舉例 中 項的系數(shù) 為符合要求的 個人組成的小組的數(shù)目，總的組成方式數(shù)目為)(xCkxkck33281538150350

22、6307288402812851010應(yīng)用舉例應(yīng)用舉例 例例3 3：1010個數(shù)字（個數(shù)字（0 0到到9 9）和）和4 4個四則運算個四則運算符符 組成的組成的1414個元素。求由其中的個元素。求由其中的n n個元素的排列構(gòu)成一算術(shù)表達式的個數(shù)。個元素的排列構(gòu)成一算術(shù)表達式的個數(shù)。),( 因所求的因所求的n n個元素的排列是算術(shù)表達式，個元素的排列是算術(shù)表達式，故從左向右的最后一個符號必然是數(shù)字。而故從左向右的最后一個符號必然是數(shù)字。而第第n-1n-1位有兩種可能，一是數(shù)字，一是運算位有兩種可能，一是數(shù)字，一是運算符。如若第符。如若第n-1n-1位是十個數(shù)字之一，則前位是十個數(shù)字之一，則前n-

23、n-1 1位必然構(gòu)成一算術(shù)表達式。位必然構(gòu)成一算術(shù)表達式。應(yīng)用舉例應(yīng)用舉例 如若不然，即第 位是4個運算符之一，則前 位必然是算術(shù)表達式。根據(jù)以上分析，令 表n個元素排列成算術(shù)表達式的個數(shù)。則1n2nna.120 ,10 ,40102121aaaaannn指的是從指的是從0到到99的的100個數(shù)，以及個數(shù)，以及1202a, 0. 9, 1 例例4 4：設(shè)有n條封閉的曲線，兩兩相交于兩點，任意三條封閉曲線不相交于一點。求這樣的n條曲線把平面分割成幾個部分？ 設(shè)滿足條件的n條封閉 曲線所分割成的域的數(shù)目為 an ，其中n-1條封閉曲線 所分割成的域的數(shù)目為an-1應(yīng)用舉例應(yīng)用舉例v第n條封閉曲線和

24、這些曲線相交于2(n-1)個點，這2(n-1)個點把第n條封閉曲線截成2(n-1)條弧，每條弧把2(n-1)個域中的每個域一分為二。故新增加的域數(shù)為2(n-1).應(yīng)用舉例應(yīng)用舉例 . 2 ),1(211anaann2)-8-(2 . 20a母函數(shù)和遞推關(guān)系應(yīng)用舉例母函數(shù)和遞推關(guān)系應(yīng)用舉例例例5 5：求n位2進制最后三位出現(xiàn)010圖象的數(shù)的個數(shù)。對于n位2進制數(shù) 從左而右進行掃描，一當(dāng)出現(xiàn)010圖象，便從這圖象后面一位從頭開始掃描，例如對11位2進制數(shù)00101001010從左而右的掃描結(jié)果應(yīng)該是2-4，7-9位出現(xiàn)010圖象，即nbbb2110010100100母函數(shù)和遞推關(guān)系應(yīng)用舉例母函數(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：01001010001na3n2.8 2.8 母函數(shù)和遞推關(guān)系應(yīng)用舉例母函數(shù)和遞推關(guān)系應(yīng)用舉例故最后3位是010的n位2進制數(shù)的個數(shù)是 。其中包