離散組合數(shù)學(xué)2線性齊次遞推關(guān)系

1、離散數(shù)學(xué)組合數(shù)學(xué) 2 / 26序列/數(shù)列 sequence of numberfnnN: f0, f1, f2, , fn, fn+1, 若 f : NR, 令 fn = f (n) , 可得數(shù)列fnnN數(shù)列是以自然數(shù)集N (或它的子集) 為定義域的函數(shù), 是一列有序的數(shù). 數(shù)列中的每一個(gè)數(shù)都叫做這個(gè)數(shù)列的項(xiàng). 排在第一位的數(shù)稱為該數(shù)列的第1項(xiàng) (首項(xiàng)), , 排在第n位的數(shù)稱為該數(shù)列的第n項(xiàng), 常用fn表示.通項(xiàng)公式: 數(shù)列的第n項(xiàng)fn與項(xiàng)的序數(shù)n之間的關(guān)系可以用一個(gè)公式fn= f (n)來(lái)表示, 這個(gè)公式叫做該數(shù)列的通項(xiàng)公式 3 / 26序列/數(shù)列 通項(xiàng)公式fnnN: f0, f1, f2

2、, , fn, fn+1, 三角形點(diǎn)陣序列 f1=1, f2=3, f3=6, , fn, fn = n(n+1)/2, n1正方形點(diǎn)陣序列 f1=1, f2=4, f3=9, , fn, fn = n2, n1銀行存款 fn = 存款數(shù)額(1+年利率)n斐波那契數(shù)列 f0=f1=1, f2=2, f3=3, f4=5, , fn, fn = f (n) = ? 4 / 26序列/數(shù)列 遞推公式/遞推關(guān)系fnnN: f0, f1, f2, , fn, fn+1, 斐波那契數(shù)列 f0=f1=1, f2=2, f3=3, f4=5, , fn, fn = fn2+fn1 , n2遞推公式: 如果數(shù)

3、列fnnN的第n項(xiàng)與它前一項(xiàng)或幾項(xiàng)的關(guān)系可以用一個(gè)式子來(lái)表示, 那么這個(gè)公式叫做該數(shù)列的遞推公式(遞推關(guān)系). 5 / 26序列,遞推關(guān)系,初值,通解,解fn = fn2 + fn1 , n2f0 =1, f1 =1f0 =2, f1 =5fn = fn2 + fn1 , n22, 5, 7, 12, 19, 序列遞推關(guān)系初值/初始條件1, 1, 2, 3, 5, 序列遞推關(guān)系通項(xiàng)公式/解通項(xiàng)公式/解初值/初始條件通解任意指定c1, c2, 則fn確定一個(gè)序列nNnN 6 / 26遞推關(guān)系與遞歸定義一個(gè)序列的遞歸定義指定了一個(gè)或多個(gè)初始的項(xiàng)以及一個(gè)由前項(xiàng)確定后項(xiàng)的規(guī)則(遞歸關(guān)系). 在遞歸和遞

4、推關(guān)系之間存在重要的聯(lián)系. 遞歸算法依據(jù)較小規(guī)模的同一問(wèn)題的一個(gè)或者多個(gè)實(shí)例的解得到規(guī)模為n的問(wèn)題的解. 因此, 當(dāng)分析一個(gè)遞歸算法的復(fù)雜性時(shí), 可以得到一個(gè)遞推關(guān)系, 它把求解規(guī)模為n的問(wèn)題需要的運(yùn)算次數(shù)用求解一個(gè)或多個(gè)小規(guī)模實(shí)例的同一問(wèn)題所需要的運(yùn)算次數(shù)來(lái)表示. 7 / 26序列/數(shù)列示例集合S=a1, a2, , an的r組合數(shù), rN集合S=a1, a2, , an的r排列數(shù), rN多重集S=n1a1, n2a2, , nkak的r組合數(shù), rN多重集S=n1a1, n2a2, , nkak的r排列數(shù), rNS給定的情況下, n = n1+n2+nk. 令br表示S的r組合數(shù), cr表

5、示S的r排列數(shù)序列brr0: b0, b1, b2, , bn, 0, 0, 序列crr0: c0, c1, c2, , cn, 0, 0, 8 / 26序列/數(shù)列示例續(xù)順序插入排序歸并排序快速排序令fn表示規(guī)模為n時(shí)需要的基本運(yùn)算次數(shù)序列fnn1: f1, f2, , fn, 9 / 26序列/數(shù)列示例續(xù)包含偶數(shù)個(gè)0的n位十進(jìn)制數(shù)字串有多少個(gè)?不包含兩個(gè)連續(xù)0的n位二進(jìn)制位串有多少個(gè)?Hanoi塔 把n個(gè)盤(pán)子從A柱移到C柱需要多少次移動(dòng)?找一個(gè)長(zhǎng)度為n的序列的最大和最小元需多少次比較?二分搜索 規(guī)模為n時(shí)需要多少次比較?整數(shù)的快速乘法 2個(gè)n位二進(jìn)制整數(shù)相乘快速矩陣乘法 2個(gè)n階矩陣相乘n個(gè)

6、點(diǎn)中最接近點(diǎn)對(duì)問(wèn)題計(jì)數(shù)1,2,n放入堆棧后的不同的輸出個(gè)數(shù)令fn表示規(guī)模為n時(shí)需要的基本運(yùn)算次數(shù)序列fnn1: f1, f2, , fn, 10 / 26序列/數(shù)列示例續(xù)n+1個(gè)數(shù)的乘積x0 x1x2xn中加括號(hào)來(lái)規(guī)定乘法的次序的方式數(shù)錯(cuò)位排列多項(xiàng)式x(x1)(x2)(xn+1)的展開(kāi)式xr系數(shù)將給定的正整數(shù)n表示成若干個(gè)正整數(shù)之和.四種情況: 有序/無(wú)序, 不重復(fù)/重復(fù)x1+x2+xk=n非負(fù)整數(shù)解的個(gè)數(shù)令fn表示規(guī)模為n時(shí)的方式數(shù)序列fnn1: f1, f2, , fn, 11 / 26遞推關(guān)系與生成函數(shù)遞推關(guān)系 通解遞推關(guān)系 + 初值 通解 + 初值 解(通項(xiàng)公式) 用形式冪級(jí)數(shù)(生成函

7、數(shù))f0 x0+f1x1+f2x2+f3x3+求解計(jì)數(shù)問(wèn)題, 其中xn的系數(shù)fn代表我們感興趣的序列的項(xiàng). 生成函數(shù)還可用于求解遞推關(guān)系以及證明組合恒等式. 12 / 26用遞推關(guān)系構(gòu)造模型例 對(duì)于不含2個(gè)連續(xù)0的n位二進(jìn)位串的個(gè)數(shù)找出遞推關(guān)系和初始條件. 有多少個(gè)這樣的5位二進(jìn)位串?.01n位串 ann-1位串 an-111n-2位串 an-20解 令an表示滿足條件的n位串的個(gè)數(shù)an =a1=2, a2=3a3=5, a4=8, a5=13按第n位的值分2類處理an1+ an2, n3 13 / 26用遞推關(guān)系構(gòu)造模型續(xù)例 編碼字的枚舉 一個(gè)計(jì)算機(jī)系統(tǒng)把一個(gè)十進(jìn)制數(shù)字串作為一個(gè)編碼字, 如

8、果它包含偶數(shù)個(gè)0, 就是有效的. 設(shè)an是有效的n位編碼字的個(gè)數(shù), 找出一個(gè)關(guān)于an的遞推關(guān)系. 解令an表示n位有效編碼的個(gè)數(shù)按第n位的值(0,1,2,9)分10類處理an = 9an1+(10n1an1) = 8an1+10n1, n2a1=9, a2=82 14 / 26例例 Hanoi塔 從A柱將這些圓盤(pán)移到C柱上去. 如果把一個(gè)圓盤(pán)從一個(gè)柱子移到另一個(gè)柱子稱作一次移動(dòng), 在移動(dòng)和放置時(shí)允許使用B柱, 但不允許大圓盤(pán)放到小圓盤(pán)的上面. 問(wèn)把所有的圓盤(pán)的從A移到C總計(jì)需要多少次移動(dòng)?解 設(shè)移動(dòng)n個(gè)盤(pán)子的總次數(shù)為T(n)T(n) = 2T(n1) +1, T(1)=1 15 / 26例例

9、插入排序解 設(shè)排序(升序) n 個(gè)數(shù)比較次數(shù)為W(n)aw(n)w(n-1)pW(n) = W(n1) + n1, W(1)=0 16 / 26例例 歸并排序(分治算法)解W(n) = 2W(n/2) + n1, W(1)=0W(n)W(n/2)W(n/2)pq13682457 17 / 26Catalan數(shù)例 求關(guān)于Cn的遞推關(guān)系, 其中Cn是通過(guò)對(duì)n+1個(gè)數(shù)的乘積 a0 1 a1 2 a2 3 k-1 ak-1 k ak k+1 n an中加括號(hào)來(lái)規(guī)定乘法的次序的方式數(shù).解 按最后一次計(jì)算的乘號(hào)k分n類處理(1kn). 第k類: k出現(xiàn)在ak-1和ak之間, 即先計(jì)算a0 1 a1 2 k

10、-1 ak-1, 再計(jì)算ak k+1 ak+1 k+2 n an, 最后計(jì)算k.分步處理: 1.計(jì)算a0 1 a1 2 k-1 ak-1, 方式數(shù)Ck-12.計(jì)算ak k+1 ak+1 k+2 n an, 方式數(shù)Cn-k 18 / 26Catalan數(shù)續(xù)定義 一個(gè)凸n+1邊形, 通過(guò)不相交于n+1邊形內(nèi)部的對(duì)角線把n+1邊形劃分成三角形, 劃分方案?jìng)€(gè)數(shù)記作hn, 稱為Catalan數(shù). 如h2=1, h4=5遞推方程: 考慮n+1邊形, 端點(diǎn)A1,An+1的邊記為a, 對(duì)于任意的k=1,2,n1, 以Ak+1A1為邊, An+1Ak+1為另一邊, 與a構(gòu)成三角形T, T將多邊形劃分成R1和R2

11、兩個(gè)部分, 分別為k+1邊形和nk+1邊形.遞推方程 19 / 26線性遞推關(guān)系模型中遞推關(guān)系很多. 某些遞推關(guān)系可以用迭代或者其他的特定技術(shù)求解. 但是, 有一類重要的遞推關(guān)系可以用一種系統(tǒng)的方法明確地求解. 在這種遞推關(guān)系中, 序列的項(xiàng)由它的前項(xiàng)的線性組合來(lái)表示.定義 一個(gè)常系數(shù)k階線性齊次遞推關(guān)系是形如an = c1an1 + c2an2 + + ckank的遞推關(guān)系, 其中c1,c2,ck是實(shí)數(shù), ck0.線性: an是若干序列前項(xiàng)的線性組合齊次: 出現(xiàn)的各項(xiàng)都是aj (1次方)的倍數(shù), 序列各項(xiàng)的系數(shù)都是常數(shù)而不是依賴于n的函數(shù) k階: 因?yàn)閍n由序列中其前面的k項(xiàng)來(lái)表示. 20 /

12、 26求解常系數(shù)線性齊次遞推關(guān)系定理 an= rn 是遞推關(guān)系 an=c1an1+c2an2+ckank 的解, 當(dāng)且僅當(dāng) rn = c1rn1+c2rn2+ckrnkrkc1rk1c2rk2ck1rck = 0 (*)(*)式叫做該遞推關(guān)系的特征方程. 方程的解叫做遞推關(guān)系的特征根. 可以用這些特征根給出這種遞推關(guān)系的所有解( 通解 ). 21 / 26定理 設(shè)c1,c2,ckR, 方程rkc1rk1ck=0有t個(gè)不等的根 r1, r2 , rt , 其重?cái)?shù)分別為 m1, m2, , mt, 滿足mi1, i=1,2,t, 且m1+m2+mt=k. 則序列an是遞推關(guān)系an=c1an1+c2

13、an2+ckank的解, 當(dāng)且僅當(dāng)求解常系數(shù)線性齊次遞推關(guān)系續(xù)例 方程r3+r2r1 = (r1)(r+1)2 = 0根與重?cái)?shù)r1 = 1, m1 = 1; r2 = -1, m2 = 2注意: 該定理提到的解是具體的序列, 此時(shí)所有的系數(shù)bi,j必須確定在沒(méi)有初值的情況下, 求出通解即可, 此時(shí)bi,j是任意的實(shí)數(shù) 22 / 26求解常系數(shù)線性齊次遞推關(guān)系續(xù)定理 設(shè)c1和c2是實(shí)數(shù). 假設(shè) r2c1rc2=0 有兩個(gè)不同的根r1和r2, 則序列an是遞推關(guān)系an=c1an1 +c2an2的解, 當(dāng)且僅當(dāng) an=b1r1n+b2r2n, n0, b1和b2是常數(shù).充分性b1r1n+b2r2n

14、= c1(b1r1n-1+b2r2n-1) + c2(b1r1n-2+b2r2n-2)b1r1n-2(r12c1r1c2) + b2r2n-2(r22c1r2c2) = 0必要性: a0 = b1+b2b1 = (a1a0r2) / (r1r2)a1 = b1r1+b2r2b2 = (a0r1a1) / (r1r2)注意: 證明必要性時(shí), 確定兩個(gè)常數(shù)b1和b2的表達(dá)式依賴于r1r2的事實(shí), 因此, 當(dāng)r1=r2時(shí), 這個(gè)定理不成立. 23 / 26求解常系數(shù)線性齊次遞推關(guān)系續(xù)定理 設(shè)c1和c2是實(shí)數(shù), c20. 假設(shè) r2c1rc2=0 有二重根r. 則序列an是遞推關(guān)系an=c1an1+c2an2的解, 當(dāng)且僅當(dāng) an= b1rn+b2n