組合數(shù)學(xué)ch052PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 組合數(shù)學(xué)組合數(shù)學(xué)ch052 2 ), 1( ,., 2 21 kknCk aaaM n 組合數(shù)是的 多重集問(wèn)題 問(wèn)題問(wèn)題3 3 確定多重集確定多重集S=3S=3a,4a,4b,5b,5cc 的的10-10-組合數(shù)。組合數(shù)。 12 , n a aa 問(wèn)題問(wèn)題1 求求的的k組合數(shù)組合數(shù) 第1頁(yè)/共40頁(yè) 3 , 2211nn akakakM n i k j j i xxG 10 )( )(xG k x 第2頁(yè)/共40頁(yè) 足條件 下 )，相應(yīng)的 就對(duì)應(yīng)了M的一個(gè)k-組合 因此合并同類項(xiàng)后， xk的系數(shù)就表示了M的k- 組合數(shù) 。 4 )(xG i k j j x 0 2, 1ji )(xG

2、 n iiik xxxx 21 njkikiii jjn , 2 , 1,0, 21 ),.,( 21n iii njri jj ,2, 1,0 n iii xxx 21 , 2211nn aiaiai 第3頁(yè)/共40頁(yè) 5 , 2211nn akakakM i a )1 (niP i k c k c m iPj j i xxG 1 )()( 第4頁(yè)/共40頁(yè) , 21n aaaM n例例5.2.1 利用生成函數(shù)方法求利用生成函數(shù)方法求 的的k-組合數(shù)。組合數(shù)。 第5頁(yè)/共40頁(yè) 3.3.3 7 , 21n aaaM k b k b n n k x xx xxxxxxbG )1 ( 1 )1

3、( )1 ()1)(1 ( 2 222 . 1 k kn bk k b k x 第6頁(yè)/共40頁(yè) 5 ,4 ,3cbaM 問(wèn)題問(wèn)題3 第7頁(yè)/共40頁(yè) 與第4章中用容斥原理得到的結(jié) 果相同。 9 5 ,4 ,3cbaM k b )1)(1)(1 ( 543243232 xxxxxxxxxxxx 0 1511109654 3 654 , 2 )1 ( )1 ( 1 )1 ()1 ()1 ( n n x n n xxxxxxx x xxx k b 10 x10 b 6 0 20 1 21 4 24 5 25 6 26 10 210 10 b 第8頁(yè)/共40頁(yè) 10 問(wèn)題問(wèn)題1 12 , n a a

4、a 問(wèn)題問(wèn)題1 求求的的k組合數(shù)組合數(shù) 解：解：在普通集合在普通集合 的的k -組合中，組合中， 或出現(xiàn)或不出現(xiàn)，故其或出現(xiàn)或不出現(xiàn)，故其k -組合數(shù)數(shù)列組合數(shù)數(shù)列 的生成函數(shù)的生成函數(shù) 為為 從而從而 , 21n aaa )1 (niai k b n k kn k x k n xbG 0 ,)1 (. k n bk 第9頁(yè)/共40頁(yè) 11 , 21n aaaM 例例5.2.3 求求 的每個(gè)元素的每個(gè)元素 至少取一次的至少取一次的k-組合數(shù)。組合數(shù)。 第10頁(yè)/共40頁(yè) 為的系數(shù)。 12 , 21n aaaM )(nkck k c k nk kn k k k n n n n j j x nk

5、k x k kn x k kn x x x xxG 1 11 )1 ( )( 00 1 k c k x ) 1, 1(nkC 第11頁(yè)/共40頁(yè) 13 13 321 xxx )72, 51, 30( 321 xxx kxxx 321 )72, 51, 30( 321 xxx k c k c )()(1 ()( 765432543232 xxxxxxxxxxxxxxxG 13 c)(xG 13 x6 13 c 解：解：設(shè)方程設(shè)方程 的整數(shù)解數(shù)為的整數(shù)解數(shù)為 ，數(shù)列，數(shù)列 對(duì)應(yīng)的生成函數(shù)為對(duì)應(yīng)的生成函數(shù)為 我們所求的是我們所求的是 為為 展開(kāi)式中展開(kāi)式中 的系數(shù)的系數(shù) 第12頁(yè)/共40頁(yè) 因此，

6、a15=8. 14 000 22 422 ) 1( 4 1 4 1 ) 1( 2 1 )1 (4 1 )1 (4 1 )1 (2 1 1 1 1 1 )1)(1 ()( k kk k k k k yyxk xxxxx xxxxxG k k ka) 1( 4 1 4 1 ) 1( 2 1 第13頁(yè)/共40頁(yè) 15 第14頁(yè)/共40頁(yè) 16 0 2 5 52 43210542 ) 1( )1 ( 1 )1 ( 1 1 1 1 1 1 )1)(1)(1)(1 ( k k k xk x x x x xx xxxxxxxxxcG 第15頁(yè)/共40頁(yè) 17 , 210 aaa . ! 0 k x a k

7、k k ! 0 k x aaG k k kke ! 0 k x axG k k ke ）（ 第16頁(yè)/共40頁(yè) 18 , 21n aaaM i a i A k p k p nn n Ak n k Ak k Ak k k k ke k x k x k x k x pxG ! )( 22 2 11 1 21 0 第17頁(yè)/共40頁(yè) 19 ! ! 0 21 , 2, 1, 21 k x kkk k k ii n k n niAk kkkk ! ! 21n kkk k 1 a 1 k 2 a 2 k n a n kkkkk n 21 k p 第18頁(yè)/共40頁(yè) 20 ),(knP nk, 2 , 1

8、, 0 n nk nk nk e x x n n x k n x n x nn x nnn n x knk n x n n nx xnnPxknPxnPxnPnPxG )1 ( 210 )!( ! ! )!( ! ! )!2( ! 2 ! 1 ),(),()2 ,() 1 ,()0 ,()( 2 2 2 解：解：設(shè)要求的生成函數(shù)為設(shè)要求的生成函數(shù)為Ge(x)，根據(jù)定義，根據(jù)定義5.1.1 第19頁(yè)/共40頁(yè) 21 , 21n aaaM 01 2 ! )( ! 2! 1 1 k k knx n i nx ke k x nee xx bG k k nb 解解 設(shè)數(shù)列設(shè)數(shù)列bk 的指數(shù)型生成函數(shù)為的

9、指數(shù)型生成函數(shù)為Gebk，根據(jù)定理，根據(jù)定理 5.3.1有，有， 從而從而 ，與第，與第3章中的結(jié)果是一致的。章中的結(jié)果是一致的。 第20頁(yè)/共40頁(yè) 22 第21頁(yè)/共40頁(yè) 23 ! 6! 5! 4! 3! 2 1 ! 5! 3! 3 65432533 xxxxx x xx x x xbG ke 10 b !10 10 x 第22頁(yè)/共40頁(yè) 24 ! 3! 2 1 ! 3! 2! 4! 2 1 323242 xx x xx x xx bG ke ) 1( 2 xx xx ee ee !2 123 2 1 2 1 0 23 k xeee k k kkxxx ), 3 , 2 , 1( 2

10、123 nb kk k 解解 設(shè)數(shù)列設(shè)數(shù)列bk 的指數(shù)型生成函數(shù)為的指數(shù)型生成函數(shù)為Gebk，則有，則有 因此，因此， 第23頁(yè)/共40頁(yè) 25 !8 560 !7 350 !6 350 !5 170 !4 70 ! 3 28 !2 9 ! 1 31 72 1 72 5 72 35 12 17 12 35 3 14 2 9 31 ! 3!2! 1 1 !2! 1 1 ! 3!2! 1 1 87 65432 8765432 32232 xx xxxxxx xxxxxxxx xxxxxxxx bG ke 4 b ! 4 4 x 解解 設(shè)每次取出設(shè)每次取出k個(gè)球的排列數(shù)為個(gè)球的排列數(shù)為bk，數(shù)列，數(shù)

11、列bk的指數(shù)型生成的指數(shù)型生成 函數(shù)為函數(shù)為Gebk，則有，則有 而我們所求的即為而我們所求的即為 為為 的系數(shù)，則取出的系數(shù)，則取出4個(gè)球的排列個(gè)球的排列 方案有方案有70種。種。 第24頁(yè)/共40頁(yè) 26 一、一、 Catalan數(shù)列的通項(xiàng)公式數(shù)列的通項(xiàng)公式 二、二、 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù) 三、三、 Catalan數(shù)列的應(yīng)用數(shù)列的應(yīng)用 第25頁(yè)/共40頁(yè) 27 例例5.4.1 在一個(gè)凸在一個(gè)凸n+1邊形中，可以邊形中，可以 用用(n-2)條不在內(nèi)部相交的對(duì)角線將條不在內(nèi)部相交的對(duì)角線將 其剖分成其剖分成(n-1)個(gè)三角形，問(wèn)有多少個(gè)三角形，問(wèn)有多少 種不同的分法？種不

12、同的分法？ 一、一、 Catalan數(shù)列的通項(xiàng)公式數(shù)列的通項(xiàng)公式 第26頁(yè)/共40頁(yè) 28 T R2 R1 A1 An+1 Ak+2 Ak Ak+1 第27頁(yè)/共40頁(yè) 將分別與之間連線， 得三角形T，三角形T將凸(n+1)邊 形分成 T，R 1和R 2三部分，其中， R 1為(k+1)邊形， R 2為(n-k+1)邊 形。因此，R 1可以用種方 法剖分，R 2可以用種 方法剖分，所以 這正是Catalan數(shù)列的通項(xiàng)公式。 29 1 1 ).()()( n k knhkhnh 1) 1 (, 0)0(hh 1)2(h 121 , n AAA 3n )(nh 11n AA) 1, 2 , 1(

13、1 nkAk 1k A 11,n AA )(kh )(knh 第28頁(yè)/共40頁(yè) 解得 30 )(nh n h)(xG 1 2 21 k k kx hxhxhxG 1 2 1 12 1111 2 k k k k k ik k kiki k ij ji ji ii i i i i xxGxxh xhhhx xhhxhxhxG 0 2 xxGxG 2 411x xG 二、二、 Catalan數(shù)列的生成函數(shù)數(shù)列的生成函數(shù) 第29頁(yè)/共40頁(yè) 顯然一個(gè)凸n+1邊形中有 種不同的剖分方法。 31 1 1 . 1 22 2 1 )4( ! 1 2 1 1 2 1 2 1 141 k k kk k x k

14、k k x k k x 0 0 h 2 411x xG 11 1 22 1 1 22 1 2 1 2 1 2 411 kk kk x k k k x k k k x xG 1 22 1 n n n 第30頁(yè)/共40頁(yè) 32 三、三、 Catalan數(shù)列的應(yīng)用數(shù)列的應(yīng)用 1.括號(hào)化問(wèn)題。括號(hào)化問(wèn)題。 矩陣鏈乘： P=a1a2a3an ，依據(jù)乘法結(jié)合律，不改變其順序，只 用括號(hào)表示成對(duì)的乘積，試問(wèn)有幾種括 號(hào)化的方案？(h(n)種) 2.出棧次序問(wèn)題。出棧次序問(wèn)題。 一個(gè)棧(無(wú)窮大)的進(jìn)棧序列為 1,2,3,.n,有多少個(gè)不同的出棧序列? 第31頁(yè)/共40頁(yè) 第32頁(yè)/共40頁(yè) 系數(shù)就是第一類St

15、irling數(shù) ，上面的式子變成： 我們稱這些數(shù)為 第一類Stirling數(shù)。 根據(jù)3.5節(jié)有，第一類Stirling數(shù)具有下 面的性質(zhì)，我們給出不同的證明方 法。 34 ) 1() 2)(1(nxxxx n x 1n x 2n x k n 021 21 n x n n x n n x n n nnn 0 , 1 , n n n n n k x 第33頁(yè)/共40頁(yè) 是項(xiàng)的系數(shù)，為了得 到，n個(gè)因式中只能有一個(gè) 因式貢獻(xiàn)常數(shù)，由加法原理得出 提供常數(shù)的總和為 所以。 35 21 , 1,)!1( 1 , 0 0 . 1 n n n n n n nn 0 n 0 x 1 n ) 1( ,),2()

16、,1(nxxx )!1( 1 n n n n n x 1n n 1n x 1n x 2 ) 1( )1()2() 1( nn n 22 ) 1( 1 n nn n n 第34頁(yè)/共40頁(yè) 比較上式兩邊的系數(shù)得 36 21 2 1 1 1 )2() 1( nn x n n x n n nxxx ) 1( nx ) 1( 2 1 1 1 ) 1() 1( 21 nxx n n x n n nxxx nn 2111 2 1 ) 1( 1 1 ) 1( 2 1 1 1 1 nnnnnn x n n nx n n nx n n x n n x n n x n n k n n k n k n1 ) 1(

17、1 1 k x 第35頁(yè)/共40頁(yè) 令則有 37 k n )1 ()21)(1 ( )( kxxx x xG k k k k nnn knnnn k k n 21 21 21 k n k k n k n 1 1 1n x 00 11 0 1 1 1 nn nn n n x k n kx k n x k n 000 1 nn nn n n x k n kxx k n xx k n 0 )( n n k x k n xG )()()( 1 00 0 )( 1 1 0 xkxGxxGxG x n xG kkk n n 第36頁(yè)/共40頁(yè) 等式右端展開(kāi)后，各項(xiàng)的一 般形式為 38 )1 ()21)(1 ( )( 1) 1(1211 )( 1) 1(1 )( 1 1 )( 0 21 kxxx x xG kx x xk x x x x x xG kx x xk x tG kx xG k kkk 0000 )()2( 1 1