《組合數(shù)學(xué)》課件PPT

組合數(shù)學(xué)課件PPT,組合數(shù)學(xué),組合,數(shù)學(xué),課件,PPT 第六章第六章 遞推關(guān)系遞推關(guān)系-一種重要的組合計(jì)數(shù)方法基本問題：建立關(guān)系；分析性質(zhì)；求解主要內(nèi)容主要內(nèi)容6.1 遞推關(guān)系的建立遞推關(guān)系的建立6.2 常系數(shù)線性齊次遞推關(guān)系的求解常系數(shù)線性齊次遞推關(guān)系的求解6.3 常系數(shù)線性非齊次遞推關(guān)系的求解常系數(shù)線性非齊次遞推關(guān)系的求解6.4*用生成函數(shù)求解遞推關(guān)系用生成函數(shù)求解遞推關(guān)系6.5*用迭代歸納法求解遞推關(guān)系及其應(yīng)用用迭代歸納法求解遞推關(guān)系及其應(yīng)用（1）等差數(shù)列（算術(shù)數(shù)列）等差數(shù)列（算術(shù)數(shù)列）h0,h0+q,h0+2q,h0+nq,遞推關(guān)系：遞推關(guān)系：hn=hn-1+q一般項(xiàng)：一般項(xiàng)：hn=h0+nq前前n+1項(xiàng)和：項(xiàng)和：sn=(n+1)h0+q(n)(n+1)/2（2）等比數(shù)列（幾何數(shù)列）等比數(shù)列（幾何數(shù)列）h0,qh0,q2h0,qnh0,遞推關(guān)系：遞推關(guān)系：hn=qhn-1一般項(xiàng)：一般項(xiàng)：hn=qnh0前前n+1項(xiàng)和：項(xiàng)和：sn=h0(1-qn+1)/(1-q)定義6.1.1 給定一個(gè)數(shù)的序列H(0),H(1),H(n),若存在正整數(shù)n0，使得當(dāng)nn0時(shí)，可以用等號(hào)(或小于，大于號(hào))把H(n)和前面某些項(xiàng)H(i)，0 i n，聯(lián)系起來，這樣的式子叫做遞推關(guān)系。遞推關(guān)系也稱遞歸關(guān)系，遞歸方程。從本質(zhì)上講，遞推關(guān)系是研究整變量函數(shù)的或者說是研究數(shù)列的，與此對(duì)應(yīng)的是連續(xù)論域中的微分方程。因此，我們可以類似的方法對(duì)它們進(jìn)行研究。利用遞推關(guān)系和初值在某些情況下可以求出序列的通項(xiàng)表示式H(n)。但是對(duì)于大多數(shù)遞推關(guān)系，目前還解不出H(n)的顯式來，即使這樣，對(duì)于給定的n也可以從初值開始，一步一步地計(jì)算出H(n)的值或者范圍，而H(n)一般代表了某個(gè)組合計(jì)數(shù)問題的解，因此遞推關(guān)系是組合計(jì)數(shù)的重要工具。基本問題 建立關(guān)系；分析性質(zhì)；求解求解遞推關(guān)系的常用方法 迭代歸納法；特征根法；生成函數(shù)法；例6.1.1（爬樓梯問題）一個(gè)小孩要爬上n階樓梯，每次可上一階或兩階，問上n階有多少種上法？解：顯然登上1階臺(tái)階有1種方法，登上2臺(tái)階有2種方法，f(1）=1，f(2)=2,稱為遞推關(guān)系的初始條件。設(shè)有f(n)種方法，要登上這n階臺(tái)階，最后邁上一個(gè)臺(tái)階或兩個(gè)臺(tái)階完成.（1）若最后是邁上一個(gè)臺(tái)階完成的，則前面登上了n-1階臺(tái)階，有f(n-1)種方法；（2）若最后是邁上兩個(gè)臺(tái)階完成的，則前面登上了n-2階臺(tái)階，有f(n-2)種方法，根據(jù)加法原理有遞推關(guān)系：f(n)=f(n-1)+f(n-2).例例6.1.2 Fibonacci數(shù)列問題是一個(gè)古老的數(shù)數(shù)列問題是一個(gè)古老的數(shù)學(xué)問題，是于學(xué)問題，是于12021202年提出的，問題表述如下年提出的，問題表述如下:把一對(duì)兔子（雌、雄各一只）在某年的把一對(duì)兔子（雌、雄各一只）在某年的開始放到圍欄中，每個(gè)月這對(duì)兔子都生出一開始放到圍欄中，每個(gè)月這對(duì)兔子都生出一對(duì)新兔，其中雌、雄各一只。由第二個(gè)月開對(duì)新兔，其中雌、雄各一只。由第二個(gè)月開始，每對(duì)新兔每個(gè)月也生出一對(duì)新兔，也是始，每對(duì)新兔每個(gè)月也生出一對(duì)新兔，也是雌、雄各一只。問一年后圍欄中有多少對(duì)兔雌、雄各一只。問一年后圍欄中有多少對(duì)兔子？子？這是一個(gè)數(shù)學(xué)模型的形象表示，不能真正用來表示兔子的繁殖規(guī)律。這是一個(gè)數(shù)學(xué)模型的形象表示，不能真正用來表示兔子的繁殖規(guī)律。對(duì)于n=1,2,令f(n)表示第n個(gè)月開始時(shí)圍欄中的兔子對(duì)數(shù)，顯然有f(1)=1,f(2)=2。在第n個(gè)月的開始，那些第n-1個(gè)月初已經(jīng)在 圍欄中的兔子仍然存在，而且每對(duì)在第n-2個(gè)月初就存在的兔子將在第n-1個(gè)月開始將要生出一對(duì)新兔來，所以有：f(n)=f(n-1)+f(n-2)(n3,n為整數(shù))f(1)=1,f(2)=2 這是一個(gè)帶有初值的遞推關(guān)系。如果規(guī)定f(0)=1,則上式變成：f(n)=f(n-1)+f(n-2)(n2,n為整數(shù))f(0)=1,f(1)=1稱滿足這個(gè)式子的數(shù)列就成為Fibonacci數(shù)列，數(shù)列中的項(xiàng)叫做Fibonacci數(shù).例例6.1.3（Hanoi塔問題）現(xiàn)有A，B，C三根立柱以及n個(gè)大小不等的中空?qǐng)A盤，這些圓盤自小到大套在A柱上形成塔形，如圖所示，要把n個(gè)圓盤從A柱上搬到C柱上，并保持原來的順序不變，要求每次只能從一根立柱上拿下一個(gè)圓盤放在另一根立柱上，且不允許大盤壓在小盤上，問至少要搬多少次？解：記f(n)為n個(gè)圓盤從A柱搬到C柱所需的最小次數(shù).整個(gè)搬運(yùn)過程可分成三個(gè)階段；（1）將套在A柱上面的n-1個(gè)圓盤從A柱按要求搬到B柱，搬動(dòng) 次數(shù)為f(n-1);（2）把A柱上最下面的那個(gè)圓盤搬到C柱上，搬動(dòng)次數(shù)為1;（3）把B柱上的n-1個(gè)圓盤按要求搬到C柱上，搬動(dòng)次數(shù)為f(n-1);由加法原則知，f(n)=2f(n-1)+1又顯然f(1)=1，所以有如下帶有初值的遞推關(guān)系:f(n)=2f(n-1)+1 f(1)=1 例例6.1.3 平面上有一點(diǎn)P，它是n個(gè)連通域的共同交界點(diǎn)，如圖所示，現(xiàn)取k種顏色對(duì)這n個(gè)域進(jìn)行著色，要求相鄰兩個(gè)域著的顏色不同。試求著色的方案數(shù)。期末試題：用紅、綠、黃、藍(lán)、白五種顏色涂在一個(gè)不可旋轉(zhuǎn)和翻轉(zhuǎn)的田字形的小方格內(nèi),每格涂一種顏色，相鄰兩格不同色。如果顏色可以重復(fù)使用，共有多少種不同的涂色方法？（7分）（1）和 有相同的顏色：有k-1種顏色可選，而對(duì)于 的著色方案與n-2個(gè)域的著色方案一 一對(duì)應(yīng) .（2）和 所著顏色不同：有k-2種顏色可選，而對(duì)于 的著色方案與n-1個(gè)域的著色方案一 一對(duì)應(yīng) .再考慮初值：故著色方案的遞推關(guān)系為：.6.2 常系數(shù)線性齊次遞推關(guān)系的求解常系數(shù)線性齊次遞推關(guān)系的求解設(shè)k是給定的正整數(shù)，若數(shù)列的相鄰k+1項(xiàng)間滿足關(guān)系對(duì) 成立，k 階線性遞推關(guān)系 若 k 階常系數(shù)線性遞推關(guān)系 k 階常系數(shù)線性齊次遞推關(guān)系 遞推關(guān)系的解 如果一個(gè)數(shù)列滿足以上遞推關(guān)系常系數(shù)線性齊次遞推關(guān)系的一般形式為 -(6.2.2)遞推關(guān)系的特征方程 方程 xk-c1xk-1-c2xk-2-ck=0 遞推關(guān)系的特征根 特征方程的k個(gè)根q1，q2qk(可能有重根)，其中qi(i=1,2,k)是復(fù)數(shù)。遞推關(guān)系的解與特征根的關(guān)系？引理引理6.2.1 設(shè)q是非零復(fù)數(shù).則f(n)=qn是常系數(shù)線性齊次遞推關(guān)系的解，當(dāng)且僅當(dāng)q是它的特征根.證明證明 設(shè)f(n)=qn是遞推關(guān)系(6.2.2)的解，即 因?yàn)?，所以 即是遞推關(guān)系的特征根，反之亦然.如果qn是常系數(shù)線性齊次遞推關(guān)系的解，還有嗎？如果有，那么以特征根為特解如何構(gòu)造遞推關(guān)系的通解？引理引理6.2.2 如果 都是遞推關(guān)系（6.2.2）的解，是常數(shù)，則 也是遞推關(guān)系（6.2.2）的解.證明證明 因?yàn)?都是遞推關(guān)系（6.2.2）的解，所以 =從而也是遞推關(guān)系(6.2.2)的解.由引理由引理 6.2.1和引理和引理6.2.2知，知，若若 q1，q2，qk是遞推關(guān)系6.2.2的特征根，則 f(n)b1q1 nb2q2 nbkqk n是遞推關(guān)系的解.（b1,b2,bk是常數(shù)）定義定義6.2.3 如果對(duì)于遞推關(guān)系（6.2.2）的每個(gè)解h(n)，都可以選擇一組常數(shù) ，使得 成立，則稱 f(n)b1q1 nb2q2 n bkqk n 是遞推關(guān)系（6.2.2）的通解，其中，為任意常數(shù)。定理定理6.2.1 設(shè) 是遞推關(guān)系（6.2.2）的個(gè)互不相等的特征根，則 f(n)b1q1 nb2q2 nbkqk n 是遞推關(guān)系（6.2.2）的通解。證明證明 由前面的分析可知,f(n)是遞推關(guān)系(6.2.2)的解.設(shè)h(n)是這個(gè)遞推關(guān)系的任意一個(gè)解，則由k個(gè)初值 h(0)=a0,h(1)=a1,.,h(k-1)=ak-1 唯一地確定，所以有 (6.2.4)如果方程組（6.2.4）有唯一解 ，這說明可以找到這k個(gè)常數(shù)，使得 h(n)b1q1 nb2q2 nbkqk n 成立，從而b1q1 nb2q2 nbkqk n是該遞推關(guān)系的通解.考察方程組（6.2.4），它的系數(shù)行列式為這是著名的Vandermonde行列式.因?yàn)?互不相等，所以該行列式不等于零，這也就是說方程組（6.2.4）有唯一解.常系數(shù)線性齊次遞推關(guān)系的求解步驟常系數(shù)線性齊次遞推關(guān)系的求解步驟1.根據(jù)題意求遞推關(guān)系根據(jù)題意求遞推關(guān)系2.利用遞推關(guān)系得到特征方程利用遞推關(guān)系得到特征方程3.解特征方程，求特征根解特征方程，求特征根4.利用特征根寫遞推關(guān)系通解利用特征根寫遞推關(guān)系通解5.根據(jù)初值確定通解中的系數(shù)根據(jù)初值確定通解中的系數(shù)6.給出遞推關(guān)系的解給出遞推關(guān)系的解關(guān)于關(guān)于微分微分方程方程求解求解的已知結(jié)論的已知結(jié)論:1.對(duì)于對(duì)于4次以及次以及4次以下的方程次以下的方程,目前已有代數(shù)解法目前已有代數(shù)解法.(在復(fù)數(shù)在復(fù)數(shù)域內(nèi)求解域內(nèi)求解)2.阿貝爾定理阿貝爾定理:5次以及更高次的代數(shù)方程沒有一般的代數(shù)解法次以及更高次的代數(shù)方程沒有一般的代數(shù)解法.例例6.2.1 求求Fibonacci數(shù)的遞推關(guān)系數(shù)的遞推關(guān)系例6.2.2例 6.2.3由定理6.2.1，可知3n是此遞推關(guān)系的解（不考慮初值），我們不妨試一試n3n，將其帶入此遞推關(guān)系。這說明n3n也是遞推關(guān)系的解，而且與線性3n無關(guān)，所以原遞推關(guān)系的通解為代入初值，得：設(shè)遞推關(guān)系 的特征方程為 令如果q是P(x)=0的二重根，這q也是Pn(x)=0的二重根，也是Pn(x)=0的根，Pn(x)是Pn(x)的微商，即因此，q也是xPn（x）=0的根，而代入x=q，得這說明nqn是原遞推關(guān)系的解。可以證明以下的結(jié)論：如果q是P(x)=0的e重根,則qn,nqn,n2qn,ne-1qn都是原遞推關(guān)系的解.定理6.2.2設(shè)q1，q2，qt是遞推關(guān)系f(n)=a1f(n-1)+a2f(n-2)+akf(n-k)(nk，ak0),的不相等的特征根，其重?cái)?shù)分別為e1，e2，et(e1+e2+et=k),則這個(gè)遞推關(guān)系的通解是：f(n)=f1(n)+f2(n)+ft(n)其中：fi(n)c1qi nc2nqi n例例6.2.5.求解遞推關(guān)系求解遞推關(guān)系對(duì)對(duì)通解為解方程組，得c1=5,c2=2,c3=-4所以原遞推關(guān)系的解為 f（n)=5*2n+2n*2n-4*3n一般形式：f(n)=c1f(n-1)+c2f(n-2)+ckf(n-k)+g(n)(nk,ck0,g(n)0),其通解是齊次通解與特解之和，即f(n)=f(n)+f(n)其中f(n)是原遞推關(guān)系的特解；f(n)是所對(duì)應(yīng)的齊次遞推關(guān)系 f(n)=c1f(n-1)+c2f(n-2)+ckf(n-k)的通解。下面主要介紹f(n)的求解方法。6.3常系數(shù)線性非齊次遞推關(guān)系的求解常系數(shù)線性非齊次遞推關(guān)系的求解 對(duì)于一般對(duì)于一般g(n)沒有普遍的解法，只對(duì)一些沒有普遍的解法，只對(duì)一些簡(jiǎn)單的情況可以用簡(jiǎn)單的情況可以用待定系數(shù)法待定系數(shù)法求求f(n)。一般方法總結(jié)一般方法總結(jié):1.求齊次關(guān)系的一般解求齊次關(guān)系的一般解2.求非齊次關(guān)系的一個(gè)特解求非齊次關(guān)系的一個(gè)特解3.將一般解和特解結(jié)合將一般解和特解結(jié)合,通過初始條件確定通過初始條件確定一般解中出現(xiàn)的常系數(shù)值一般解中出現(xiàn)的常系數(shù)值.比較等式兩邊例6.3.1 求解遞推關(guān)系解：因?yàn)?不是特征方程的根，所以該遞推關(guān)系的非齊次特解為，將其代入遞推關(guān)系，得的系數(shù)，得 從而 a=2.而相應(yīng)齊次遞推關(guān)系的通解為，由定理6.3.1知，非齊次遞推關(guān)系的通解為 由初值得從而 故 例例6.3.2 求解遞推關(guān)系求解遞推關(guān)系解 由于3是特征方程的根，所以該遞推關(guān)系的特解為 將它代入遞推關(guān)系，得到 a=6從而非齊次遞推關(guān)系的通解為再由初值求得于是根據(jù)前面的分析，可知該遞推關(guān)系的通解為 解 相應(yīng)的特征方程為x=2，故齊次解為2n。設(shè)非齊次特解為b，代入原遞推關(guān)系，得 例例6.3.3 求求Hanoi塔問題滿足的遞推關(guān)系塔問題滿足的遞推關(guān)系 所以特解為代入初值得所以