線性常系數(shù)非齊次遞推關系第1頁，共52頁，2023年，2月20日，星期六2.9線性常系數(shù)非齊次遞推關系例：求n位2進制數(shù)中，從左到右逐步劃去010，最后三位出現(xiàn)010圖象的數(shù)的個數(shù)。對于n位2進制數(shù)從左而右進行掃描，一出現(xiàn)010圖象，便從這圖象后面一位從頭開始掃描，例如對11位2進制數(shù)00101001010從左而右的掃描結果應該是2-4，7-9位出現(xiàn)010圖象，即而不是4-6，7-9位出現(xiàn)的010圖象，即不是2第2頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例 為了找出關于數(shù)列an的遞推關系，需對滿足條件的數(shù)的結構進行分析。由于n位中除了最后三位是010已確定，其余n-3位可取0或1：故最后3位是010的n位2進制數(shù)的個數(shù)是2n-3最后3位出現(xiàn)010圖象:***…010在n-4位到第n-2位出現(xiàn)010圖象，而在最后3位并不出現(xiàn)010圖象:***…010103第3頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例故有利用推得特征方程為4第4頁，共52頁，2023年，2月20日，星期六設解方程組5第5頁，共52頁，2023年，2月20日，星期六2.9線性常系數(shù)非齊次遞推關系分析例題結果假定討論的非齊次遞推關系為對應的齊次遞推關系為若和是非齊次遞推關系的解，則序列是齊次遞推關系的解；則要求的非齊次遞推關系的解等于齊次遞推關系的解和一個非齊次遞推關系的特解的疊加6第6頁，共52頁，2023年，2月20日，星期六2.9線性常系數(shù)非齊次遞推關系例：非齊次遞推關系的特解代入原遞推關系式滿足齊次遞推關系的解：特征方程：7第7頁，共52頁，2023年，2月20日，星期六8第8頁，共52頁，2023年，2月20日，星期六2.9線性常系數(shù)非齊次遞推關系例：齊次遞推關系特解非齊次遞推關系的特解非齊次遞推關系的特解代入原遞推關系式9特征方程為第9頁，共52頁，2023年，2月20日，星期六特解的形式假定討論的非齊次遞推關系為1)其中b(n)是n的p次多項式，r是特征方程的m重根則特解的形式有k0,k1…kp為待定系數(shù)，由非齊次遞推關系確定2)若r不是C(x)=0的根，則令m=0；2是特征根，m=1特解的形式是an的形式是10第10頁，共52頁，2023年，2月20日，星期六母函數(shù)和遞推關系例題：鋪磚題方磚1*1，長磚1*2，給1*n的路鋪路面，求1）方案數(shù)2）總磚數(shù)（所有方案的總磚數(shù)）設方案數(shù)為an,以最后一塊磚分類an-1an-211第11頁，共52頁，2023年，2月20日，星期六2）總磚數(shù)設總磚數(shù)為bn,以最后一塊磚分類bn-1。

。

。an-1bn-2。

。

。an-2α,β是特征根，m=1特解是bn的形式是代入聯(lián)立方程組太復雜12第12頁，共52頁，2023年，2月20日，星期六13第13頁，共52頁，2023年，2月20日，星期六附加作業(yè)題：某人要鋪1*n長度的路，有三種磚可以使用：1*1的方磚，或者兩個直角邊分別為1，1的直角三角磚（方磚從對角線切開得到兩塊這樣的磚，稱為小三角）以及斜邊是2的等邊直角三角磚（稱為大三角）,求：（1）鋪1*n長度的路一共有多少方案數(shù)；（2）鋪1*n長度的路所有方案中一共可能出現(xiàn)的方磚總數(shù)；bn14第14頁，共52頁，2023年，2月20日，星期六2.9線性常系數(shù)非齊次遞推關系例：求n位的2進制數(shù)中，從左向右掃描，最后三位才第一次出現(xiàn)010圖象的數(shù)的個數(shù)。即求對n位2進制數(shù)從左而右掃描，第一次在最后三位出現(xiàn)010圖象的數(shù)的個數(shù)。自然，最后三位除外任取連續(xù)三個都不會是010的。 設表示滿足條件的n位數(shù)個數(shù)，和前例類似，最后三位010的n位2進制數(shù)共個.15第15頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例對這個數(shù)分析如下。 （a）包含了在最后三位第1次出現(xiàn)010圖象的個數(shù)，其個數(shù)為，排除了在第到第位第1次出現(xiàn)010圖象的可能。 （b）包含了在第到第位第1次出現(xiàn)010圖象的數(shù)，其個數(shù)為16第16頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例 （c）包含了在第位到第位第1次出現(xiàn)010圖象的數(shù),其個數(shù)是 （d）包含了在第位到第位第1次出現(xiàn)010圖象的數(shù),其個數(shù)是，因在第位（打*號的格）可以取0或1兩種狀態(tài)。17第17頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例 一般可以歸納為對，從第位到第位第一次出現(xiàn)010圖象的數(shù)，其數(shù)目為。從第位到第位中間的位可以取0，1兩種值,故有種狀態(tài)。

18第18頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例故得遞推關系如下： 時有下面幾種狀態(tài)：排除了01010，因從左而右掃描時01010屬于前三位出現(xiàn)010圖象的。19第19頁，共52頁，2023年，2月20日，星期六

請注意，遞推關系式不是常系數(shù)遞推關系。故時有時有其它依此類推。20第20頁，共52頁，2023年，2月20日，星期六令21第21頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例整理得22第22頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例例11：解圖電路網(wǎng)絡中的

設其中23第23頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例根據(jù)歐姆定律有圖2-8-5由于各點的電流代數(shù)和為零，24第24頁，共52頁，2023年，2月20日，星期六

代入得遞推關系或由點的電流代數(shù)和為零，可得特征方程是25第25頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例設解方程組得26第26頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例例：求圖2-8-6所示的n級網(wǎng)絡的等效電阻。所謂等效電路，相當于圖2-8-6中虛線所包圍的塊用一電阻取代，使在兩端點和之間的效果一樣。RRRRRRRRRRRRRR圖2-8-627第27頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例

Rn可以作為由Rn-1等效電阻如圖2-8-7所示的方式串并聯(lián)構成的.圖2-8-7遞推關系28第28頁，共52頁，2023年，2月20日，星期六令因此令29第29頁，共52頁，2023年，2月20日，星期六將代入得到特征方程是30第30頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例解方程組31第31頁，共52頁，2023年，2月20日，星期六§2.8母函數(shù)和遞推關系應用舉例

例13：設有地址從1到n的單元，用以紀錄一組信息。這個信息的每個元素都占用兩個單元，而且存放的地址是完全隨機的，因而可能出現(xiàn)兩個存放信息單元之間留下一個空單元無法存放其他信息，求這n個單元留下空單元的平均數(shù)。設這個平均數(shù)為。12i+1i+2n-1n存儲單元如上圖，設某一信息占用了第i+1，i+2兩個單元，把這組單元分割成兩個部分，一是從1到i，另一從i+3到n。32第32頁，共52頁，2023年，2月20日，星期六（2-8-13）式是變系數(shù)遞推關系，可改為33由于用相鄰兩個單元的幾率相等，12i+1i+2n-1n第33頁，共52頁，2023年，2月20日，星期六設34第34頁，共52頁，2023年，2月20日，星期六35第35頁，共52頁，2023年，2月20日，星期六§2.10Stirling數(shù)前面見到的遞推關系都是一個參數(shù)的。Stirling數(shù)導出的遞推關系式是兩個參數(shù)的。（1）多項式系數(shù)n個有區(qū)別的球放到兩個有區(qū)別的盒子里，若要求第1個盒子放k個球，第二個盒子放n-k個球方案數(shù)應是中項的系數(shù)依據(jù)加法法則有

第36頁，共52頁，2023年，2月20日，星期六§2.10Stirling數(shù)可把上面的討論推廣到n個有區(qū)別的球放到m個有區(qū)別的盒子里，要求m個盒子放的球數(shù)分別是的情況，其不同方案數(shù)用表示。從n個有區(qū)別的球中取出個放到第1個盒子里去，其選取方案數(shù)為；當?shù)?個盒子的個球選定后，第2個盒子里的個球則是從n-n1個中選取的，其方案數(shù)應為；第3個盒子的n3個球則是從n-n1-n2中選取，其方案數(shù)為；第37頁，共52頁，2023年，2月20日，星期六§2.10Stirling數(shù)根據(jù)乘法法則有：第38頁，共52頁，2023年，2月20日，星期六§2.10Stirling數(shù)

n個有區(qū)別的球，放到m個有標志的盒子的問題，也可以考慮把n個有區(qū)別的球進行全排列。對于每一個排列依次取n1個放到第1個盒子里，取n2個放到第2個盒子里，…，最后nm個放到第m個盒子里。然而，放到盒子里的球不考慮球的順序，故得不同的方案數(shù)為稱為多項式系數(shù)。第39頁，共52頁，2023年，2月20日，星期六§2.10Stirling數(shù)多項式的展開式是由式右端的n項中，每項各取一個元素相乘而得到的。

表達式中共有n個因子項，令第i個因子項對應于第i個有標志的球，從第i個因子項中取對應于把第i個有標志的球放到第i個盒子。式展開的一般項表示第一個盒子有個球，第二個盒子有個球，等等。因此式中項的系數(shù)應為第40頁，共52頁，2023年，2月20日，星期六§2.10Stirling數(shù)

定理：展開式的項數(shù)等于C(n+m-1,n)，而且這些系數(shù)之和等于

證明：展開式中的項和從m個元素中取n個作允許重復的組合一一對應。故得展開式的項數(shù)等于C(n+m-1,n),

第41頁，共52頁，2023年，2月20日，星期六§2.10Stirling數(shù)從m個中取n個作允許重復的組合的全體，對于每個球都有m個盒子可供選擇，根據(jù)乘法法則有第42頁，共52頁，2023年，2月20日，星期六§2.10Stirling數(shù)

(2)Stirling數(shù)只準備討論其中的第二類Stirling數(shù),至于第一類的Stirling數(shù)只準備給出它的定義和遞推關系.

定義:

稱為第一類Stirling數(shù),或用S1表示顯然有fallingfactorial第43頁，共52頁，2023年，2月20日，星期六

定義:n個有區(qū)別的球放到m個相同的盒子中,要求無一空盒,其不同的方案數(shù)用或者表示,稱為第二類Stirling數(shù).例如紅,黃,藍,白四種顏色的球,放到兩個無區(qū)別的盒子里,不允許有空盒,其方案有如下七種:其中r表紅球,y表黃球,b表藍球,w表白球,§2.10Stirling數(shù)第44頁，共52頁，2023年，2月20日，星期六有序拆分的放球模型：n的一個r-分拆相當于把n個無區(qū)別的球放到r個有標志的盒子，盒子不允許空著:C(k-1,r-1)相當于把n個無區(qū)別的球放到r個有標志的盒子，盒子允許空著:C(n+r-1,n)相當于把n個無區(qū)別的球放到n個無標志的盒子，盒子允許空著，也允許放多于一個球。1..11..11..11..1n個1x1個1nn-1個空隙r-1……

的xn項系數(shù)。r-1個門框第45頁，共52頁，2023年，2月20日，星期六§2.10Stirling數(shù)定義:n個有區(qū)別的球放到m個相同的盒子中,要求無一空盒,其不同的方案數(shù)稱為第二類Stirling數(shù).定理:第二類Stirling數(shù)S(n,m)有下列性質:證明:公式(a),(b),(e)是顯然的,只證(c),(d).第46頁，共52頁，2023年，2月20日，星期六(c)設有n個不相同的球從中取出球,其余的個球,每個都有與b1同盒,或不與同盒兩種選擇.但必須排除一種情況,即全體與同盒,因這時另一盒將是空盒.故實際上只有種方案,即(d)n個球放到個盒子里,不允許有一空盒,故必有一盒有兩個球,從n個有區(qū)別的球中取2個共有種組合方案.第47頁，共52頁，2023年，2月20日，星期六§2.10Stirling數(shù)

定理:第二類Stirling數(shù)滿足下面的遞推關系,

證明:設有n個有區(qū)別的球從中取一個球設為.把n個球放到m個盒子無一空盒的方案的全體可分為兩類。（a）獨占一盒，其方案數(shù)顯然為（b）不獨占一盒，這相當于先將剩