離散組合數(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ù)列中的每一個數(shù)都叫做這個數(shù)列的項. 排在第一位的數(shù)稱為該數(shù)列的第1項 (首項), , 排在第n位的數(shù)稱為該數(shù)列的第n項, 常用fn表示.通項公式: 數(shù)列的第n項fn與項的序數(shù)n之間的關(guān)系可以用一個公式fn= f (n)來表示, 這個公式叫做該數(shù)列的通項公式 3 / 26序列/數(shù)列 通項公式fnnN: f0, f1, f2

2、, , fn, fn+1, 三角形點陣序列 f1=1, f2=3, f3=6, , fn, fn = n(n+1)/2, n1正方形點陣序列 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項與它前一項或幾項的關(guān)系可以用一個式子來表示, 那么這個公式叫做該數(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)系通項公式/解通項公式/解初值/初始條件通解任意指定c1, c2, 則fn確定一個序列nNnN 6 / 26遞推關(guān)系與遞歸定義一個序列的遞歸定義指定了一個或多個初始的項以及一個由前項確定后項的規(guī)則(遞歸關(guān)系). 在遞歸和遞

4、推關(guān)系之間存在重要的聯(lián)系. 遞歸算法依據(jù)較小規(guī)模的同一問題的一個或者多個實例的解得到規(guī)模為n的問題的解. 因此, 當(dāng)分析一個遞歸算法的復(fù)雜性時, 可以得到一個遞推關(guān)系, 它把求解規(guī)模為n的問題需要的運(yùn)算次數(shù)用求解一個或多個小規(guī)模實例的同一問題所需要的運(yùn)算次數(shù)來表示. 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時需要的基本運(yùn)算次數(shù)序列fnn1: f1, f2, , fn, 9 / 26序列/數(shù)列示例續(xù)包含偶數(shù)個0的n位十進(jìn)制數(shù)字串有多少個?不包含兩個連續(xù)0的n位二進(jìn)制位串有多少個?Hanoi塔 把n個盤子從A柱移到C柱需要多少次移動?找一個長度為n的序列的最大和最小元需多少次比較?二分搜索 規(guī)模為n時需要多少次比較?整數(shù)的快速乘法 2個n位二進(jìn)制整數(shù)相乘快速矩陣乘法 2個n階矩陣相乘n個

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

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

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

9、插入排序解 設(shè)排序(升序) n 個數(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是通過對n+1個數(shù)的乘積 a0 1 a1 2 a2 3 k-1 ak-1 k ak k+1 n an中加括號來規(guī)定乘法的次序的方式數(shù).解 按最后一次計算的乘號k分n類處理(1kn). 第k類: k出現(xiàn)在ak-1和ak之間, 即先計算a0 1 a1 2 k

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

11、兩個部分, 分別為k+1邊形和nk+1邊形.遞推方程 19 / 26線性遞推關(guān)系模型中遞推關(guān)系很多. 某些遞推關(guān)系可以用迭代或者其他的特定技術(shù)求解. 但是, 有一類重要的遞推關(guān)系可以用一種系統(tǒng)的方法明確地求解. 在這種遞推關(guān)系中, 序列的項由它的前項的線性組合來表示.定義 一個常系數(shù)k階線性齊次遞推關(guān)系是形如an = c1an1 + c2an2 + + ckank的遞推關(guān)系, 其中c1,c2,ck是實數(shù), ck0.線性: an是若干序列前項的線性組合齊次: 出現(xiàn)的各項都是aj (1次方)的倍數(shù), 序列各項的系數(shù)都是常數(shù)而不是依賴于n的函數(shù) k階: 因為an由序列中其前面的k項來表示. 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個不等的根 r1, r2 , rt , 其重數(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根與重數(shù)r1 = 1, m1 = 1; r2 = -1, m2 = 2注意: 該定理提到的解是具體的序列, 此時所有的系數(shù)bi,j必須確定在沒有初值的情況下, 求出通解即可, 此時bi,j是任意的實數(shù) 22 / 26求解常系數(shù)線性齊次遞推關(guān)系續(xù)定理 設(shè)c1和c2是實數(shù). 假設(shè) r2c1rc2=0 有兩個不同的根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ù)b1和b2的表達(dá)式依賴于r1r2的事實, 因此, 當(dāng)r1=r2時, 這個定理不成立. 23 / 26求解常系數(shù)線性齊次遞推關(guān)系續(xù)定理 設(shè)c1和c2是實數(shù), c20. 假設(shè) r2c1rc2=0 有二重根r. 則序列an是遞推關(guān)系an=c1an1+c2an2的解, 當(dāng)且僅當(dāng) an= b1rn+b2n