線性常系數(shù)非齊次遞推關(guān)系

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

。

。an-1bn-2。

。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義:

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

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

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

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

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