離散數(shù)學(xué)高教版第13章

1、1,主要內(nèi)容遞推方程的定義及實例遞推方程的公式解法遞推方程的其他解法生成函數(shù)及其應(yīng)用指數(shù)生成函數(shù)及其應(yīng)用Catalan數(shù)與Stirling數(shù),第十三章 遞推方程與生成函數(shù),2,13.1遞推方程的定義及實例,定義13.1 設(shè)序列 a0, a1, …, an, …, 簡記為{ an }. 一個把 an 與某些個ai (i<n) 聯(lián)系起來的等式叫做關(guān)于序列 { an } 的遞推方程. 當(dāng)給定遞推方程和適當(dāng)?shù)某踔稻臀ㄒ淮_

2、定了序列.,Fibonacci數(shù)列：1，1，2，3，5，8，… ，記作{ fn }. 遞推方程 fn = fn?1 + fn?2 初值 f0 = 1，f1 = 1 階乘計算數(shù)列： 1，2，6，24，5！，…, 記作{ F(n)} 遞推方程 F(n) = nF(n?1) 初值 F(1)

3、= 1,3,例1 從A柱將這些圓盤移到C柱上去. 如果把一個圓盤從一個柱子移到另一個柱子稱作一次移動，在移動和放置時允許使用B柱，但不允許大圓盤放到小圓盤的上面. 問把所有的圓盤的從A移到C總計需要多少次移動？,初值是 T(1)=1 可證明解是 T(n)=2n?1,移動n個盤子的總次數(shù)為T(n). 因此得到遞推方程 T(n) = 2T(n?1) +1.,,,,,,,,遞

4、推方程的實例:Hanoi塔,4,兩個排序算法,歸并算法 Mergesort (A,p,r) // 對A的下標p到r之間數(shù)排序1. if p<r 2. then q??(p+r)/2? //q為p到r的中點，3. Mergesort(A,p,q) 4. Mergesort(A,q+1,r) 5. Merge(A,p,q,r) // 歸并排好序數(shù)組A[p..q

5、]與A[q+1..r],插入排序算法 INSERTION-SORT(A,n) 1. for j ? 2 to n key ? A[j] i ? j–14 while i > 0 and A[i] > key5. do A[i+1] ? A[i]; i ? i –17. A[i+1] ? key,5,遞推方程的實例:算法分析,

6、例2 哪種排序算法在最壞情況下復(fù)雜度比較低？ 插入排序，歸并排序 插入排序 W(n) = W(n ?1) + n ?1 W(1) = 0解得 W(n) = O(n2). 歸并排序，不妨設(shè) n = 2k. W(n) = 2W(n/2) + n－1 W(1) = 0解得 W(n) = O(nlogn),6,13.2 遞推方程的公式解法

7、,特征方程、特征根遞推方程的解與特征根的關(guān)系無重根下通解的結(jié)構(gòu)求解實例有重根下通解的結(jié)構(gòu)求解實例,7,其中 a1, a2, … , ak為常數(shù)，ak ? 0 稱為 k 階常系數(shù)線性齊次遞推方程 b0, b1, …, bk?1 為 k 個初值,定義13.2 常系數(shù)線性齊次遞推方程的標準形：,常系數(shù)線性齊次遞推方程,實例：Fibonacci 數(shù)列的遞推方程,8,特征方程與特征根,,,9,遞推方程解與特征根的關(guān)系,定理13.1

8、 設(shè) q 是非零復(fù)數(shù)，則 qn 是遞推方程的解當(dāng)且僅當(dāng)q 是它的特征根.,qn是遞推方程的解? qn ? a1qn?1 ? a2qn?2 ? … ? akqn?k = 0? qn?k (qk ? a1qk?1 ? a2qk?2 ? … ? ak) = 0? qk ? a1qk?1 ? a2qk?2 ? … ? ak = 0 （因為q?0）? q 是它的特征根,定理13.2 設(shè) h1(n) 和 h2(n) 是遞推方程

9、的解，c1,c2為任意常數(shù),則 c1h1(n)+c2h2(n) 也是這個遞推方程的解.推論 若 q1, q2, …, qk 是遞推方程的特征根，則 c1q1n + c2q2n + … + ckqkn 是該遞推方程的解，其中c1, c2, …, ck 是任意常數(shù).,10,無重根下通解的結(jié)構(gòu),定義13.4 若對常系數(shù)線性齊次遞推方程的每個解 h(n) 都存在一組常數(shù)c1?,c2?,…, ck? 使得

10、 h(n) = c1?q1n+c2?q2n+…+ck?qkn 成立，則稱 c1q1n + c2q2n + …+ ckqkn 為該遞推方程的通解,定理13.3 設(shè)q1, q2, …, qk 是常系數(shù)線性齊次遞推方程不等的特征根，則 H(n)= c1q1n + c2q2n + … + ckqkn為該遞推方程的通解.,11,例3 Fibonacci 數(shù)列：

11、 fn=fn?1+fn?2 ，特征根為,通解為,代入初值 f0 =1, f1=1, 得,解得,,,解是,實例,12,有重根下求解中的問題,,例4,,解 特征方程 x2?4x+4 = 0 通解 H(n) = c12n + c22n = c2n 代入初值得： c 無解. 問題：兩個解線性相關(guān),13,有重根下的通解結(jié)構(gòu),定理13.4 設(shè) q1, q2, … , qt 是遞推方

12、程的不相等的特征根，且 qi 的重數(shù)為 ei，i=1, 2, … , t，令,那么通解,14,例5 求解以下遞推方程,其中待定常數(shù)滿足以下方程組,原方程的解為,,解 特征方程 x4+x3?3x2?5x?2 = 0 , 特征根?1,?1,?1,2,通解為,求解實例,15,遞推方程的標準型通解結(jié)構(gòu)特解的求法 多項式函數(shù) 指數(shù)函數(shù) 組合形式,常系數(shù)線性非齊次遞推方程求解,16,,遞推方程的標準型及通解,17

13、,,例6 找出遞推方程 an ?2an?1 = 2n2 的通解,如果 f(n)為n次多項式，則特解一般也是 n 次多項式,特解的形式：多項式,18,例7 Hanoi塔 T(n) = 2T(n?1)+1 T(1)=1,實例,解 令 T*(n) = P代入方程 P = 2P + 1解得 P = –1 T(n) = c 2n–1, 代入初值得 c=1, 解為 T

14、(n) = 2n –1.,19,例8 求解關(guān)于順序插入排序算法的遞推方程,解 設(shè)特解為W*(n)=P1n+P2，代入遞推方程，得 P1n+P2 ?( P1(n?1)+P2) = n?1無解. 設(shè)特解W*(n) = P1n2+P2n, 代入遞推方程得 (P1n2+P2n)?(P1(n?1)2+P2(n?1))= n?1 解得 P1=1/2, P2= ?1/2. 通解為 W(n) =

15、c 1n + n(n?1)/2 = c + n(n?1)/2代入初值W(1)=0，得到W(n)= n(n?1)/2=O(n2).,實 例(續(xù)),20,特解的形式:指數(shù),f(n)為指數(shù)函數(shù) ? n，若? 是 e 重特征根(e可以等于0)，則特解為Pne? n , 其中P為待定常數(shù).,例9 通信編碼問題 解 an = 6an?1 + 8n?1, a1=7 設(shè) a*n = P 8n?1 , 代入得 P = 4

16、 通解 an = c?6n + 4?8n?1 代入初值得 an = (6n+8n)/2,例10 H(n)–5H(n–1)+6H(n–2) = 2n， 解 令 H*(n)=Pn2n 代入得 Pn2n– 5P(n–1)2n–1 + 6P(n–2)2n–2 = 2n 解得 P = – 2, 特解 H*(n) = – n2n+1,21,換元法迭代歸納法應(yīng)用實例,13.3 遞推方程的其他解法,2

17、2,思想：通過換元轉(zhuǎn)化成常系數(shù)線性遞推方程,解 令,代入得 bn = 2 bn–1 + 1， b0 = 4解得,例11,an>0,換元法,23,解 H(k) = 2 H(k–1) + 2k–1 H(1) = 1 令 H*(k) = P1k2k + P2 , 解得 P1=P2=1 H*(k) = k2k + 1通解 H(k) =

18、 c 2k + k2k + 1 代入初值得 c = –1 H(k) = –2k + k2k +1 W(n) = n log n– n + 1,,例12 歸并排序,換元法:實例,24,迭代歸納法：歸并排序,,例13,25,迭代歸納法：錯位排列,例14 Dn = (n–1)(Dn–1 + Dn–2),解：,,26,快速排序算法,算法 Quicksort (A,p,r) // p 和 r

19、分別表示A首和末元素下標 1. if p < r 2. then q?Partition(A, p, r) // 劃分為A[p..q?1]和A[q+1..r] 3. A[p]?A[q] 4. Quicksort(A,p,q?1) 5. Quicksort(A,q+1,r),27,劃分過程,算法 Partition(A,p

20、,r) 1. x ? A[p] //選首元素作為劃分標準x2. i ? p?1 3. j ? r+14. while true 5. do repeat j ? j ?1 6. until A[ j ] x //A[i]是從前找的第一個比x大的元素9. if i < j // 繼續(xù)搜索A[i]到A[j]之間的范圍10

21、 then A[ i ] ? A[ j ] // A[ i ]與A[ j ]交換，回到行411. else return j //結(jié)束While循環(huán),28,實例,27 99 0 8 13 64 86 16 7 10 88 25 90 i

22、 j 27 25 0 8 13 64 86 16 7 10 88 99 90 i j 27 25 0

23、 8 13 10 86 16 7 64 88 99 90 i j 27 25 0 8 13 10 7 16 86 64 88 99 90

24、 j i 16 25 0 8 13 10 7 27 86 64 88 99 90,29,平均情況時間復(fù)雜度分析,,,遞推方程,差消法化簡,,30,迭代求解,,,,31,遞歸樹,,W(n)= n k –(1+2+…+2k?1) = nk – (2k

25、 –1) = n log n – n + 1,32,13.4 生成函數(shù)及其應(yīng)用,牛頓二項式系數(shù)與牛頓二項式定理生成函數(shù)的定義生成函數(shù)的應(yīng)用,33,牛頓二項式系數(shù),定義13.5 設(shè) r 為實數(shù)，n為整數(shù)，引入形式符號,稱為牛頓二項式系數(shù).,,實例,34,牛頓二項式定理,定理13.6 （牛頓二項式定理）設(shè)?為實數(shù)，則對一切實數(shù)x, y，|x/y|<1，有,若?= ?m，其中m為正整數(shù)，那么,35,重要展開式,令x=z，y=1，

26、那么牛頓二項式定理就變成,在上面式子中用?z代替 z ，則有,36,生成函數(shù)定義,定義13.6 設(shè)序列{an}，構(gòu)造形式冪級數(shù) G(x) = a0 + a1x + a2x2 +… + an xn + …稱G(x)為序列{an}的生成函數(shù).,例如，{ C(m,n) }的生成函數(shù)為 (1+x)m給定正整數(shù)k, { kn }的生成函數(shù)為 G(x) =1+ kx + k2x2 + k3x3 +

27、 … =,37,例14 求序列{an}的生成函數(shù) (1) an = 7· 3n (2) an = n(n+1),解,由序列求生成函數(shù),38,由生成函數(shù)求序列通項,,.,解,39,生成函數(shù)的應(yīng)用,求解遞推方程計數(shù)多重集的 r 組合數(shù)不定方程的解整數(shù)拆分,40,求解遞推方程,例16 an– 5an?1 + 6an?2 = 0，a0 = 1, a1 = ? 2,41,例17,解：設(shè)

28、 { hn} 的生成函數(shù)為,求解遞推方程,42,,求解遞推方程,43,多重集的 r 組合數(shù),S = { n1?a1, n2?a2, …, nk?ak} 的 r 組合數(shù)就是不定方程 x1 + x2 + …+ xk = r xi ? ni i = 1,2,…,k的非負整數(shù)解的個數(shù),的展開式中 yr 的系數(shù),生成函數(shù),44,實例,例18 S ={ 3?a, 4?b, 5?c } 的10

29、組合數(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,

30、 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, a, b, b, b, c, c, c, c, c }, { a, b, b, b, b, c, c, c, c, c },45,不定方程解的個數(shù),基本的不定方程 x1 + x2 + …+ xk = r ， xi 為自然數(shù),46,推廣的不定

31、方程,帶限制條件的不定方程 x1 + x2 + … + xk = r，li ? xi ? ni,帶系數(shù)的不定方程 p1x1 + p2x2 + … + pkxk = r，xi?N生成函數(shù),生成函數(shù),47,實例,例19 1克砝碼2個，2克砝碼1個，4克砝碼2個，問能稱出哪些重量，方案有多少？,解： x1 + 2 x2 + 4 x3 = r 0 ? x1 ? 2, 0 ? x2 ? 1,

32、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,48,拆分的定義：將給定正整數(shù)N表示成若干個正整數(shù)之和.,正整數(shù)拆分,49,無序拆分,基本模型：將N無序拆分成正整數(shù) a1, a2, …, an a1x1 + a2x2 + … + anxn = N

33、 不允許重復(fù),允許重復(fù),50,實例,例20 證明任何正整數(shù)都可以唯一表示成 2 進制數(shù).對應(yīng)于將任何正整數(shù)N拆分成 2 的冪， 20, 21, 22, 23, …, 且不允許重復(fù).,對于所有的 n, 系數(shù)是1，這就證明唯一的表法.,生成函數(shù),51,解 N允許重復(fù)無序拆分成 k個數(shù)（k?r）的方案? N允許重復(fù)無序拆分成正整數(shù) k（k?r）的方案做下述 Ferrers圖 將圖以 y =x 對角線翻

34、轉(zhuǎn)180度，得到 共軛的Ferrers圖. 16 = 6+5+3+2 （k ? 4）對應(yīng)每個數(shù)不超過4的拆分: 16 = 4+4+3+2+2+1 這種拆分數(shù)的生成函數(shù)為,,無序拆分：個數(shù)限制,例21 給定r, 求N允許重復(fù)無序拆分成 k個數(shù) (k?r)的方法數(shù),52,定理13.7 將N允許重復(fù)地有序拆分成 r 個部分的方案數(shù)為 C(N?1,r

35、?1). 證 設(shè) N= a1+a2+…+ar 是滿足條件的拆分，則令,r?1個Si 取值為1,2,…,N?1，方法數(shù)為 C(N?1,r?1).,不允許重復(fù)有序拆分：不允許重復(fù)無序拆分 + 全排列,有序拆分,推論 對N 做任意重復(fù)的有序拆分，方案數(shù)為,53,指數(shù)生成函數(shù)的定義與實例指數(shù)生成函數(shù)的應(yīng)用,13.5 指數(shù)生成函數(shù)及其應(yīng)用,54,例22 給定正整數(shù)m, an = P(m,n), {an}的指數(shù)生成函數(shù)為,例23 bn=

36、1, 則{bn}的指數(shù)生成函數(shù)為,定義13.7 設(shè){an}為序列，稱,為{an}的指數(shù)生成函數(shù).,指數(shù)生成函數(shù)的定義與實例,55,應(yīng)用：多重集排列計數(shù),定理13.8 設(shè) S = {n1?a1, n2?a2, … , nk?ak}為多重集，則 S 的 r 排列數(shù)的指數(shù)生成函數(shù)為,56,實例,例24 由1, 2, 3, 4 組成的五位數(shù)中，要求1出現(xiàn)不超過2次，但不能不出現(xiàn)，2出現(xiàn)不超過1次，3出現(xiàn)可達3次，4出現(xiàn)偶數(shù)次. 求

37、這樣的五位數(shù)個數(shù).,N = 215,解,57,實例,解 設(shè)方案數(shù)為an,例25 紅、白、蘭涂色 1?n 的方格，要求偶數(shù)個為白色，問有多少方案？,58,13.6 Catalan數(shù)與Stirling數(shù),Catalan數(shù)第一類 Stirling數(shù)第二類 Stirling數(shù),59,Catalan數(shù)定義,定義13.8 一個凸 n+1邊形，通過不相交于n+1 邊形內(nèi)部的對角線把 n+1 邊形劃分成三角形，劃分方案個數(shù)記作hn，稱

38、為Catalan數(shù).,實例：h4=5,初值 h2=1,60,,考慮n+1條邊的多邊形，端點A1, An+1的邊記為a, 對于任意的 k=1, 2,…, n?1，以Ak+1A1為邊，An+1Ak+1為另一邊，與a構(gòu)成三角形T, T 將多邊形劃分成 R1和 R2兩個部分，分別為 k+1 邊形和 n?k+1邊形.,遞推方程,Catalan數(shù)的遞推方程,解：,61,,實例：計數(shù)堆棧的輸出個數(shù),例26 1, 2, … , n放入堆棧后

39、的不同的輸出個數(shù),解 在 1 進棧到出棧之間作為一個子問題，1出棧后作為一個子問題. 過程如下：,步2：子問題規(guī)模 k，步4：子問題規(guī)模 n?k?1,1．1 進棧； 2．處理 k個數(shù)（2, … , k+1）的進棧問題； 3．1 出棧； 4．處理 k+2, … , n 的進棧問題；,62,,求解遞推方程,63,第一類Stirling數(shù),將 xr 系數(shù)的絕對值 Sr 記作 ，稱為第一類 Stirling數(shù),定義13.

40、9 多項式 x(x?1)(x?2)…(x?n+1) 的展開式為 Snxn? Sn?1xn?1+ Sn?2xn?2? … + (?1)n?1S1x,實例 x(x?1) = x2?x x(x?1)(x?2) = x3?3x2+2x,64,第一類Stirling數(shù)的遞推方程,65,第一類Stirling數(shù)的恒等式,66,第二類Stirling數(shù)定義,定義13.10 n 個不同的球恰好

41、放到 r 個相同的盒子里的方法數(shù)稱為第二類Stirling數(shù)，記作實例具體方案如下：a,b,c | d a,c,d | b a,b,d | c b,c,d | a a,b | c,d a,c | b,d a,d | b,c,,67,第二類Stirling數(shù)遞推方程,證明：取球a1，a1單獨放一個盒子， a1不單獨放一個盒子，先放n?1個球到 r 個盒子，插入a1有 r 種方法，,

42、遞推方程,68,第二類Stirling數(shù)恒等式,69,恒等式證明,1.,a1 先放在一個盒子里，剩下的 n?1 個球每個有 2 種選擇，但是全落入a1的盒子的方法不符合要求.,,n 個球放到 n?1個盒子，必有一個盒子含 2 個球，其余每個盒子 1 個球. 選擇兩個球有 C(n,2) 種方法.,,70,恒等式證明,對應(yīng) n 個不同的球恰好放到 m 個不同盒子的方法數(shù)（無空盒）,按照含球的盒子數(shù) k 分類，對應(yīng)了允許存在空盒的方法,

43、至多 n 個不同的球放到 r?1 個相同的盒子不存在空盒的方法按照球數(shù)分類,71,,,,,,放球問題的計數(shù),,,,,,,,72,第十三章 習(xí)題課,主要內(nèi)容遞推方程的求解方法：公式法、換元法、迭代歸納法、生成函數(shù)法遞推方程與遞歸算法生成函數(shù)的應(yīng)用：計算多重集的 r 組合數(shù)、確定不定方程的整數(shù)解個數(shù)、計算拆分方案數(shù)、求解遞推方程指數(shù)生成函數(shù)的應(yīng)用：計算多重集的 r 排列數(shù)常用的計數(shù)符號：組合數(shù)、排列數(shù)、多項式系數(shù)、錯位排列數(shù)、F

44、ibonacci數(shù)、Catalan數(shù)、兩類Stirling數(shù)基本計數(shù)模型：選取問題、不定方程的解、非降路徑、正整數(shù)拆分、放球等,73,基本要求,能夠使用遞推方程求解計數(shù)問題能夠使用生成函數(shù)或指數(shù)生成函數(shù)求解計數(shù)問題掌握 Fibonacci數(shù)、Catalan 數(shù)、兩類 Stirling數(shù)的定義、組合意義以及相關(guān)的公式.,74,練習(xí)1,已知 a0=0, a1=1, a2=4, a3=12 滿足遞推方程 an + c1an?1

45、 + c2an?2 = 0，求 c1 和 c2 .,解得 c1=?4, c2=4.,代入a0,a1,a2,a3的值得到,根據(jù)已知條件得到,75,練習(xí)2,2．求解遞推方程,.,用換元法. 令bn=nan, 代入原遞推方程得,用公式法解得,從而得到,76,練習(xí)3,3．確定序列{an}的生成函數(shù)，其中an=,,,77,練習(xí)3,,,78,,練習(xí)4,4．已知,是序列{an}的生成函數(shù)，求an.,,解得A= ?1/4, B=3/4, C=1/4,

46、從而得到,,79,練習(xí)4,,80,練習(xí)5,5．求下列 n 階行列式的值 dn,.,,解得 dn=n+1.,方程,81,設(shè)平面上已經(jīng)有n?1條直線. 當(dāng)加入第n條直線時，它與平面上的前n?1條直線交于n?1個點. 這些點將第n條直線分割成n段，每段都增加一個區(qū)域，共增加n個區(qū)域，因此得到遞推方程,練習(xí)5,5. 平面上有 n 條直線，它們兩兩相交且沒有三線交于一點，問這 n 條直線把平面分成多少個區(qū)域？,,,82,6．在經(jīng)濟中，商品

47、價格隨需求量增長而上漲，隨供給量增長而下降，可以簡單地用一個線性方程表示這種依賴關(guān)系. 需求關(guān)系：p=a?bq，其中p為價格，q 為需求量，a,b>0為常數(shù). 當(dāng) p 上漲時 q 將減少. 供給關(guān)系：p=kr，其中p為價格，r 為供給量，k>0為常數(shù). 當(dāng)p上漲時，r 將增加. 假設(shè)價格隨需求量能做到即時變化，而商品生產(chǎn)和流通需要時間，因此供給量隨價格的變化需要1個單位時間的延遲. 假定每個時間的需求量都和供

48、給量相等，考慮一個時間序列0,1,…,n,…，設(shè)時間0的價格是 p0，求時間 n 的價格 pn.,練習(xí)6,83,設(shè)第 n 時間的價格為 pn, 需求量為 qn，供給量為 rn，那么有,練習(xí)6,代入得到,解得,84,7．用三個1、兩個2、五個3可以組成多少個不同的四位數(shù)？如果這個四位數(shù)是偶數(shù)，那么又有多少個？,練習(xí)7,,其中x4的系數(shù)為,因此 a4=71.,85,練習(xí)8,方法一. n 個編號球恰放入 k 個相同盒子且不允許相鄰編號

49、在同一盒的方法數(shù). 選定球a1, 進行變換：如果a1自己在一個盒子，將盒子拿走，得到 n?1個不同球恰放入k?1個相同盒且相鄰編號不落入同一盒子的方法. 如果與a1在同一盒子的球有 將球 放入 所在的盒子， 然后拿走含a1的盒子，從而得到n?1個不同球恰好放到 k?1個盒子且至少兩個相鄰標號球落入同一盒的方法. 所求方法數(shù)等于n?1個不同球恰好放入k

50、?1個相同盒子的方法數(shù)，即 . 再考慮盒子編號為,8．用恰好k 種可能的顏色做旗子，使得每面旗子由 n 條彩帶構(gòu)成（n?k），且相鄰兩彩帶的顏色都不相同，證明不同的旗子數(shù)是,,,86,方法二,數(shù)學(xué)歸納法. 當(dāng) n=1, 必有 k=1, 這時有 ，命題為真. 假設(shè)對一切 n, k 命題為真，考慮 n+1條使用 k 種顏色的涂色方案. 若用 k 種顏色涂色前 n 條，最后一

51、條有 k?1 種選擇，方法數(shù)為 . 若用 k?1 種顏色涂色前 n 條，選擇顏色的方式數(shù)為 k, 涂色方法數(shù)為 因此由乘法法則得 . 再根據(jù)加法法則，總方法數(shù)為根據(jù)歸納法命題成立.,,,,,87,方法三,令n+1個球恰落入k+1相同盒子且球編號不相鄰方法數(shù)為 將這些方法分成兩類：其