離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用

1、離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用110.2 生成函數(shù)及其應(yīng)用生成函數(shù)及其應(yīng)用 10.2.1牛頓二項(xiàng)式定理與牛頓二項(xiàng)式系數(shù)牛頓二項(xiàng)式定理與牛頓二項(xiàng)式系數(shù) 10.2.2 生成函數(shù)的定義及其性質(zhì)生成函數(shù)的定義及其性質(zhì) 10.2.3 生成函數(shù)的應(yīng)用生成函數(shù)的應(yīng)用離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用2牛頓二項(xiàng)式系數(shù)牛頓二項(xiàng)式系數(shù) 0!)1).(1(0100nnnrrrnnnr定義定義10.5 設(shè)設(shè) r 為實(shí)數(shù)，為實(shí)數(shù)，n為整數(shù)，引入形式符號為整數(shù)，引入形式符號65!6)5)(4)(3)(2)(52 1285! 42)5)(3(1)1(! 4)321)(221)(121(2142/14 4! 323434 稱為稱為牛頓二

2、項(xiàng)式系數(shù)牛頓二項(xiàng)式系數(shù). . 例如例如離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用3牛頓二項(xiàng)式定理牛頓二項(xiàng)式定理定理定理10.6 （牛頓二項(xiàng)式定理）（牛頓二項(xiàng)式定理）設(shè)設(shè) 為實(shí)數(shù)，則對一切實(shí)數(shù)為實(shí)數(shù)，則對一切實(shí)數(shù)x, y，|x/y|1，有，有!)1).(1(,)(0nnnyxnyxnnn 其其中中!) 1.(1)(nnmmmnmn ） nnmnnmmmnn1) 1(!) 1).(1() 1(若若 = m，其中，其中m為正整數(shù)，那么為正整數(shù)，那么離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用4重要展開式重要展開式1|1)1()1(1)1(0 zznnmzznnnmm1|1)1(1)1(0 zznnmzznnmm 022)1()1(1

3、, 2.111, 1nnxnxmxxxm令令x=z，y=1，那么牛頓二項(xiàng)式定理就變成，那么牛頓二項(xiàng)式定理就變成 在上面式子中用在上面式子中用 z代替代替 z ，則有，則有 離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用5生成函數(shù)的定義生成函數(shù)的定義定義定義10.6 設(shè)序列設(shè)序列an，構(gòu)造形式冪級數(shù)，構(gòu)造形式冪級數(shù) G(x) = a0 + a1x + a2x2 + + an xn + 稱稱G(x)為序列為序列an的的生成函數(shù)生成函數(shù). 例如，例如，C(m,n)的生成函數(shù)為的生成函數(shù)為 (1+x)m給定正整數(shù)給定正整數(shù)k, kn的生成函數(shù)為的生成函數(shù)為 G(x) =1+ kx + k2x2 + k3x3 + = kx

4、 11離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用6生成函數(shù)的性質(zhì)生成函數(shù)的性質(zhì))()()(,. 30 xBxAxCbacniinin 則則)()(,0. 4xAxxBlnalnbllnn 則則1. bn= an, 為常數(shù)，則為常數(shù)，則B(x)= A(x)2. cn=an+bn, 則則C(x)=A(x)+B(x) llnnnxxaxAxB 10)()(5bn= an+l , 則則 離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用7xxAxBabniin 1)()(,. 60則則生成函數(shù)的性質(zhì)生成函數(shù)的性質(zhì)(續(xù)續(xù))xxxAAxBaAabniniin 1)()1()()1(,. 70則則收收斂斂，且且 xnndxxAxxBnab0)(1

5、)(,1.108bn= nan, 為常數(shù)，為常數(shù)，則則B(x)=A( x)9bn= nan, 則則B(x)=xA (x)離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用8證明證明xxAxxaxxaxaxBxaxaxaxbxaxaxbabnnnnnnnn 1)(.11.1111)(.101010100 xxAxBabniin 1)()(,. 60則則證證離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用9有關(guān)級數(shù)的結(jié)果有關(guān)級數(shù)的結(jié)果 112111111121212102121001222)1(1)!1(2!2)!22()1(1!2)32.(531)1(1!)1).(1(1)1()1(1111kkkkkkkkkkkkkkkkknnnnnxkk

6、kxkkkxkkxkkxkxxxxx 離散數(shù)學(xué)-生成函數(shù)及其應(yīng)1(2)1()(,)1()()1(1)(,1)()(),()()2(xxxxxGxxdxxGxxHxxxdxxHnxxHxHxnxdxxGxnnxnnnnx 由序列求生成函數(shù)由序列求生成函數(shù)例例1 求序列求序列an的生成函數(shù)的生成函數(shù) (1) an = 7 3n (2) an = n(n+1)xxxxGnnnnn317)3(737)()1(00 解解離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用11由生成函數(shù)求序列通項(xiàng)由生成函數(shù)求序列通項(xiàng)xxxxG21632(2 ）xxxxxxxxxxGnnnnn323)2(23

7、21221632(0102 ） 1, 7321,221nnann例例2 已知已知 an 的生成函數(shù)為的生成函數(shù)為求求an解解 . 離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用12生成函數(shù)的應(yīng)用生成函數(shù)的應(yīng)用 求解遞推方程求解遞推方程 計(jì)數(shù)多重集的計(jì)數(shù)多重集的r組合數(shù)組合數(shù) 不定方程的解不定方程的解 整數(shù)拆分整數(shù)拆分 離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用13求解遞推方程求解遞推方程例例1 an 5an 1 + 6an 2 = 0 a0 = 1, a1 = 2 nnnnnnnnnaxxxxxxxxG3425342531421565171)(002 G(x) = a0 + a1x + a2x2 + a3x3 + 5x G(x)

8、 = 5a0 x 5a1x2 5a2x3 - 6x2 G(x) = +6a0 x2 +6a1x3 + (1 5x+6x2)G(x) = a0 + (a1 5a0)x 離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用14求解遞推方程求解遞推方程(續(xù)續(xù)) 12,111hnhhhnkknkn例例2 xxHxhxHxhhhxxhxhxHnnnnnkknknlllkkk )()()(12211112 1)(nnnxhxH解：設(shè)解：設(shè) hn 的生成函數(shù)為的生成函數(shù)為 離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用15 122112212)1(1222)1()4(1222)1(1 212141(21212)41(1)( 0,)()(11221121

9、2121nnnhxnnnxnnnxnnnxxxHxxHxHnnnnnnnnnnnnn）求解遞推方程求解遞推方程(續(xù)續(xù))離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用16多重集的多重集的r-組合數(shù)組合數(shù)S = n1 a1, n2 a2, , nk ak 的的 r 組合數(shù)就是不定方程組合數(shù)就是不定方程 x1 + x2 + + xk = r xi ni i = 1,2,k的非負(fù)整數(shù)解的個(gè)數(shù)的非負(fù)整數(shù)解的個(gè)數(shù) 的展開式中的展開式中 yr 的系數(shù)的系數(shù) ).1).(.1)(.1()(21knnnyyyyyyyG 生成函數(shù)生成函數(shù)離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用17多重集的多重集的r-組合數(shù)組合數(shù)(續(xù)續(xù)) 例例3 S = 3 a,

10、 4 b, 5 c 的的10 組合數(shù)組合數(shù)解：生成函數(shù)解：生成函數(shù)G(y) = (1+y+y2+y3)(1+y+y2+y3+y4)(1+y+y2+y3+y4+y5) = (1+2y+3y2+4y3+4y4+3y5+2y6+y7)(1+y+y2+y3+y4+y5) = (1 + +3y10+2y10+y10 + ) N = 6 組合方案組合方案 a, a, a, b, b, b, b, c, c, c , a, a, a, b, b, b, c, c, c, c , a, a, a, b, b, c, c, c, c, c , a, a, b, b, b, b, c, c, c, c , a,

11、a, b, b, b, c, c, c, c, c , a, b, b, b, b, c, c, c, c, c 離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用18不定方程解的個(gè)數(shù)不定方程解的個(gè)數(shù) 0001)1(!)1).(1)()1()(!)1).(1)()1(1.)1()(rrrrrrrrkkyrrkyrrkkkyrrkkkyyyG rrkN1 基本的不定方程基本的不定方程 x1 + x2 + + xk = r ， xi為自然數(shù)為自然數(shù) 離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用19不定方程解的個(gè)數(shù)不定方程解的個(gè)數(shù)(續(xù)續(xù)).(.).)(.()(111222111knnnllnllnllyyyyyyyyyyG .)1(.)1.

12、)(1()(2222211 kkppppppyyyyyyyG帶限制條件的不定方程帶限制條件的不定方程 x1 + x2 + + xk = r，li xi ni帶系數(shù)的不定方程帶系數(shù)的不定方程 p1x1 + p2x2 + + pkxk = r，xi N生成函數(shù)生成函數(shù)生成函數(shù)生成函數(shù)離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用20重量重量012345678910 11 12方案方案1121212121211實(shí)例實(shí)例例例4 4 1克砝碼克砝碼2個(gè)，個(gè)，2克砝碼克砝碼1個(gè)，個(gè)，4克砝碼克砝碼2個(gè)，問能稱出個(gè)，問能稱出哪些重量，方案有多少？哪些重量，方案有多少？解：解： x1 + 2 x2 + 4 x3 = r 0 x1

13、 2, 0 x2 1, 0 x3 2 G(y) = (1+y+y2)(1+y2)(1+y4+y8) = 1+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y12離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用21有序有序無序無序不重復(fù)不重復(fù) 4 = 4 4 = 1+3 4 = 3+1 4 = 4 4 = 1+3重復(fù)重復(fù) 4 = 4 4 = 1+3 4 = 3+1 4 = 2+2 4 = 2+1+1 4 = 1+2+1 4 = 1+1+2 4 = 1+1+1+1 4 = 4 4 = 1+3 4 = 2+2 4 = 2+1+1 4 = 1+1+1+1正整數(shù)拆分正整數(shù)拆分拆分拆分的定義：將

14、給定正整數(shù)的定義：將給定正整數(shù)N表示成若干個(gè)正整數(shù)之和表示成若干個(gè)正整數(shù)之和. 拆分的分類拆分的分類離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用22無序拆分無序拆分)1).(1)(1()(21naaayyyyG 基本模型：將基本模型：將N無序拆分成正整數(shù)無序拆分成正整數(shù) a1, a2, , an a1x1 + a2x2 + + anxn = N 不允許重復(fù)不允許重復(fù) )1).(1)(1(1.)1(.)1.)(1()(212211222nnnaaaaaaaaayyyyyyyyyyG 允許重復(fù)允許重復(fù)離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用23實(shí)例實(shí)例例例5 證明任何正整數(shù)都可以唯一表示成證明任何正整數(shù)都可以唯一表示成 2 進(jìn)制

15、數(shù)進(jìn)制數(shù).對應(yīng)于將任何正整數(shù)對應(yīng)于將任何正整數(shù)N拆分成拆分成 2 的冪，的冪， 20, 21, 22, 23, , 且不允許重復(fù)且不允許重復(fù). 生成函數(shù)生成函數(shù) 04824284211.111111).1)(1)(1)(1()(nnyyyyyyyyyyyyyG對于所有的對于所有的 n, 系數(shù)是系數(shù)是1，這就證明唯一的表法，這就證明唯一的表法.離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用24無序拆分無序拆分個(gè)數(shù)限制個(gè)數(shù)限制 例例6 給定給定r,求求N允許重復(fù)無序拆分成允許重復(fù)無序拆分成 k個(gè)數(shù)個(gè)數(shù) (k r)的方法數(shù)的方法數(shù)解解 N允許重復(fù)無序拆分成允許重復(fù)無序拆分成 k個(gè)數(shù)（個(gè)數(shù)（k r）的方案）的方案 N允許重復(fù)無序拆分成正整數(shù)允許重復(fù)無序拆分成正整數(shù) k（k r）的方案）的方案做下述做下述 Ferrers圖圖 將圖以將圖以 y =x對角線翻轉(zhuǎn)對角線翻轉(zhuǎn)180度，度，得到得到 共軛的共軛的Ferrers圖圖. 16 = 6+5+3+2 （k 4）對應(yīng)每個(gè)數(shù)不超過對應(yīng)每個(gè)數(shù)不超過4的拆分的拆分: 16 = 4+4+3+2+2+1 這種拆分?jǐn)?shù)的生成函數(shù)為這種拆分?jǐn)?shù)的生成函數(shù)為 )1).(1)(1(1)(2ryyyyG 離散數(shù)學(xué)-生成函數(shù)及其應(yīng)用25有序拆分有序拆分NSSSriaSrikii .0,., 2,