《組合數(shù)學(xué)》教案 3章(遞推關(guān)系)

組合數(shù)學(xué) 第三章 遞推關(guān)系第三章 遞推關(guān)系1. 遞推關(guān)系及其分類(lèi)2. 建立應(yīng)用問(wèn)題的遞推關(guān)系的方法3. 求解線性常系數(shù)遞推關(guān)系的特征根方法4. 求解遞推關(guān)系的其它方法5. 三個(gè)典型數(shù)列及其應(yīng)用3.1 基本概念（一） 遞推關(guān)系【定義3.1.1】（隱式）對(duì)數(shù)列和任意自然數(shù)n，一個(gè)關(guān)系到和某些個(gè)的方程式，稱(chēng)為遞推關(guān)系，記作例 【定義3.1. 】（顯式） 對(duì)數(shù)列，把與其之前若干項(xiàng)聯(lián)系起來(lái)的等式對(duì)所有nk均成立（k為某個(gè)給定的自然數(shù)），稱(chēng)該等式為的遞推關(guān)系，記為 （3.1.1）例 （二） 分類(lèi)（1） 按常量部分： 齊次遞推關(guān)系：指常量0，如； 非齊次遞推關(guān)系，即常量0，如。（2） 按的運(yùn)算關(guān)系： 線性關(guān)系，F(xiàn)是關(guān)于的線性函數(shù)，如（1）中的與均是如此； 非線性關(guān)系，F(xiàn)是的非線性函數(shù)，如。（3） 按的系數(shù)： 常系數(shù)遞推關(guān)系，如（1）中的與； 變系數(shù)遞推關(guān)系，如，之前的系數(shù)是隨著n而變的。（4） 按數(shù)列的多少： 一元遞推關(guān)系，其中的方程只涉及一個(gè)數(shù)列，如（3.1.1）和（3.1.1）均為一元的； 多元遞推關(guān)系，方程中涉及多個(gè)數(shù)列，如（5）顯式與隱式：（三） 定解問(wèn)題【定義3.1.2】（定解問(wèn)題）稱(chēng)含有初始條件的遞推關(guān)系為定解問(wèn)題，其一般形式為 （3.1.2）解遞推關(guān)系，指根據(jù)式（3.1.1）或（3.1.2）求an的與a0、a1、an1無(wú)關(guān)的解析表達(dá)式或數(shù)列an的母函數(shù)。（四） 例【例3.1.1】（Hanoi塔問(wèn)題）n個(gè)圓盤(pán)按從小到大的順序一次套在柱A上。規(guī)定每次只能從一根柱子上搬動(dòng)一個(gè)圓盤(pán)到另一根柱子上，且要求在搬動(dòng)過(guò)程中不允許大盤(pán)放在小盤(pán)上，而且只有A、B、C三根柱子可供使用。用an表示將n個(gè)盤(pán)從柱A移到柱C上所需搬動(dòng)圓盤(pán)的最少次數(shù)，試建立數(shù)列的遞推關(guān)系。 A B C（解）特例：a11，a23，對(duì)于任何n3。一般情形：第一步，將套在柱A的上部的n1個(gè)盤(pán)按要求移到柱B上，共搬動(dòng)了次；第二步，將柱A上的最大一個(gè)盤(pán)移到柱C上，只要搬動(dòng)一次；第三步，再?gòu)闹鵅將n1個(gè)盤(pán)按要求移到柱C上，也要用次。由加法法則： （3.1.3）求解 【例3.1.2】（Lancaster戰(zhàn)斗方程）兩軍打仗，每支軍隊(duì)在每天戰(zhàn)斗結(jié)束時(shí)都清點(diǎn)人數(shù)，用a0和b0分別表示在戰(zhàn)斗打響前第一支和第二支軍隊(duì)的人數(shù)，用an和bn分別表示第一支和第二支軍隊(duì)在第n天戰(zhàn)斗結(jié)束時(shí)的人數(shù)，那么，an1an就表示第一支軍隊(duì)在第n天戰(zhàn)斗中損失的人數(shù)，同樣，bn1bn表示第二支軍隊(duì)在第n天戰(zhàn)斗中損失的人數(shù)。假設(shè)：一支軍隊(duì)所減少的人數(shù)與另一支軍隊(duì)在每天戰(zhàn)斗開(kāi)始前的人數(shù)成比例，則常量A、B度量每支軍隊(duì)的武器系數(shù) （3.1.4）含有兩個(gè)未知量的一階線性遞歸關(guān)系組。【例3.1.3】設(shè)，求an所滿足的遞推關(guān)系。（解）下整數(shù)函數(shù)。即不大于x的最大整數(shù)。n為偶數(shù)：n為奇數(shù)：分兩種情況：當(dāng)n為偶數(shù)時(shí)，令n2m，則m1an前兩項(xiàng)求和： 后兩項(xiàng)求和：當(dāng)n為奇數(shù)時(shí)也成立。求初值：a0a11。則1r，r12r，r(12r)r (1r)13rr(13r)r (12r)14r3【例3.1.4】設(shè)0出現(xiàn)偶數(shù)次的n位八進(jìn)制數(shù)共有個(gè)，0出現(xiàn)奇數(shù)次的數(shù)共有個(gè)。求和滿足的遞推關(guān)系。對(duì)0出現(xiàn)偶數(shù)次的n位八進(jìn)制數(shù)分兩種情況討論：（1）最高位是0，則其余n1位應(yīng)該含有奇數(shù)個(gè)0，這類(lèi)八進(jìn)制數(shù)共有個(gè)。（2）最高位不是0，則其余n1位還應(yīng)該含有偶數(shù)個(gè)0，這類(lèi)八進(jìn)制數(shù)共有7個(gè)。因此有7。同理可得7，所以、滿足例 n20出現(xiàn)偶數(shù)次的數(shù) 00，11，12，13，14，15，77，共50個(gè)0出現(xiàn)奇數(shù)次的數(shù) 01，10，02，20，03，30，70，共14個(gè)【例3.1.5】用后退的Euler公式求常微分方程的數(shù)值解。（解）函數(shù)yy(x)在點(diǎn)xn處的真值記為y(xn)，近似值記為yn，求數(shù)值解即利用數(shù)值方法求y(x)在處xn的近似值yn（n1,2,）。思想：以直代曲。向前的Euler方法：，其中h稱(chēng)為步長(zhǎng)。向后的Euler方法：后退的Euler公式是指對(duì)常微分方程，當(dāng)已知函數(shù)y在處的值時(shí)，可通過(guò)解代數(shù)方程求得函數(shù)y在處的數(shù)值解，其中h是自變量x的步長(zhǎng)（n0,1,2,）。已知原方程為，代入Euler公式可得函數(shù)y的數(shù)值解為（五） 本章研究?jī)?nèi)容1. 建模；2. 求解。3.2 常系數(shù)線性遞推關(guān)系常系數(shù)的線性遞推關(guān)系： （3.2.1）或 （3.2.2）分別稱(chēng)為k階齊次遞推關(guān)系和k階非齊次遞推關(guān)系。其中f(n)稱(chēng)為自由項(xiàng)。顯然，式（3.2.1）至少有一個(gè)平凡解 ，而人們更關(guān)心的是它的非零解。結(jié)論：對(duì)于常系數(shù)線性遞推關(guān)系的定解問(wèn)題，其解必是唯一的。求解方法：首推特征根法。思想：來(lái)源于解常系數(shù)線性微分方程，因?yàn)閮烧咴诮Y(jié)構(gòu)上很類(lèi)似，所以其解的結(jié)構(gòu)和求解的方法也類(lèi)似。3.2.1 解的性質(zhì)【性質(zhì)1】設(shè)數(shù)列和是（3.2.1）的解，則也是（3.2.1）之解。其中為任意常數(shù)。（證）、滿足方程（3.2.1），即 令r1r2得：（規(guī)定c01，下同）?！就茝V】設(shè)均為（3.2.1）之解，則也是（3.2.1）的解。其中為任意常數(shù)?！拘再|(zhì)2】設(shè)和是（3.2.2）的解，則是（3.2.1）的解?！拘再|(zhì)3】若是（3.2.1）的解，是（3.2.2）的解，則是（3.2.2）的解。一般情形：設(shè)是（3.2.2）的解，分別是（3.2.1）的解，則是（3.2.2）的解?！拘再|(zhì)4】設(shè)是遞推關(guān)系的解，是遞推關(guān)系的解，則是遞推關(guān)系的解。3.2.2 解的結(jié)構(gòu)（一） 概念 （3.2.1）【定義3.2.1】稱(chēng)多項(xiàng)式C(x)為齊次遞推關(guān)系（3.2.1）的特征多項(xiàng)式，相應(yīng)的代數(shù)方程C(x) 0 稱(chēng)為（3.2.1）的特征方程，特征方程的解稱(chēng)為（3.2.1）的特征根。（二） 結(jié)論【定理3.2.1】數(shù)列（3.2.1）的非零解的充分必要條件是q為（3.2.1）的特征根。（證）是（3.2.1）的解q是方程C(x)0的根，即q是（3.2.1）的特征根。意義：將求解常系數(shù)線性齊次遞推關(guān)系的問(wèn)題轉(zhuǎn)化為常系數(shù)代數(shù)方程的求根問(wèn)題，從而給出了一個(gè)實(shí)用且比較簡(jiǎn)單的解此類(lèi)遞推關(guān)系的方法。（三） 通解【定義3.2.2】 若是（3.2.1）的不同解，且（3.2.1）的任何解都可以表為，則稱(chēng)為（3.2.1）的通解。其中為任意常數(shù)。此處所說(shuō)的不同解是指將每一個(gè)解都視為一個(gè)無(wú)窮維的解向量，而這些向量之間是線性無(wú)關(guān)的。說(shuō)明 通解的特征： 通解首先是解； 組成通解的所有解向量線性無(wú)關(guān)； 任何一個(gè)具體的解都被包容在通解中。3.2.3 特征根法思路：通過(guò)解式（3.2.1）的特征方程，求得其特征根，再利用特征根構(gòu)造（3.2.1）的通解。（一） 特征根為單根情形設(shè)是（3.2.1）的互不相同的特征根，則（3.2.1）的通解為 （3.2.3）其中為任意常數(shù)（待定）。（證）（1）是（3.2.1）的解：由定理3.2.1知是方程（3.2.1）的解，再由性質(zhì)1知也是（3.2.1）的解。（2）向量線性無(wú)關(guān)：（3）（3.2.1）的所有解都可以表為（3.2.3）的形式：設(shè)是（3.2.1）的一個(gè)解，且滿足初始條件，i0, 1, 2, , k1。令，代入初始條件，得關(guān)于的線性方程組 （3.2.4）系數(shù)行列式為范德蒙行列式：所以式（3.2.4）有唯一解。即一定可以表示為（3.2.3）的形式。由于的任意性，故知結(jié)論成立?！纠?.2.1】求遞推關(guān)系的通解。（解）特征方程為，解之得特征根1， 2，3 通解為 其中，A、B、C為任意常數(shù)。若是定解問(wèn)題，設(shè)初值為：，帶入通解得解得A0，B2，C3，故若初值為4，1，7，則求A、B、C的方程組為規(guī)律：（二） 重根情形【例3.2.2】求遞推關(guān)系的通解。（解）特征方程特征根 （二重根）仿單根情形 一個(gè)待定常數(shù)。問(wèn)題：滿足兩個(gè)初始條件不太可能。實(shí)質(zhì)：兩個(gè)解向量和是線性相關(guān)的。任務(wù)：找兩個(gè)線性無(wú)關(guān)的解向量和。另一解：令，也是解，且與線性無(wú)關(guān)。n4(n1)4(n2)02通解： （需證明）一般情形：設(shè)q為k重根，則通解為更一般的情形：有t個(gè)根，為重根。通解 【例3.2.3】求0的通解。（解）特征方程 0特征根： x1（三重），x2（二重）通解 (A11A12nA13n2)( A21A22n)(A11A12nA13n2)( A21A22n)（三） 復(fù)根情形 設(shè)特征方程有一對(duì)共軛（單）復(fù)根：，則通解中含通解： 優(yōu)點(diǎn)：避免了復(fù)數(shù)運(yùn)算。尤其是當(dāng)數(shù)列是實(shí)數(shù)時(shí)，的虛部為零。一般情形：q是m重復(fù)根，也是m重復(fù)根，通解中有小結(jié)：特征根通解中對(duì)應(yīng)的項(xiàng)實(shí)根q為單根m重根復(fù) 根一對(duì)單復(fù)根 ,一對(duì)m重復(fù)根 ,【例3.2.4】求定解。（解）特征方程： q22q20特征根： q1（方法I）按復(fù)根形式：，通解： an代初值： 解： A0，B1定解： ，m0,1,數(shù)列：0，1，2，2，0，-4，-8，-8，0，16，-32，-32，（方法II）按單根形式：通解： 代入初值： ， 即定解： 化復(fù)數(shù)表示形式為實(shí)數(shù)形式【例3.2.5】求定解（解）特征方程：0特征根： q2，2，通解： 代初值： 解： A3，B0，C1，D0，E1定解： ，n0,1, （四） 代數(shù)方程求根方程：0，在復(fù)數(shù)域上必有n個(gè)根（k重根按k個(gè)算）。（1）韋達(dá)定理 （2）推論：例3.2.1中，方程若有整數(shù)根，則此根必整除-6，即此根必為1，2，3，6之一。（3）方程的降階：由韋達(dá)定理知-1是解，方程必可分解為03.2.4 非齊次方程（一） 結(jié)構(gòu)困難性：與微分方程類(lèi)似?？山馇樾危篺(n)的幾種特殊情形。 （3.2.1） （3.2.2）【定理3.2.2】設(shè)是（3.2.2）的一個(gè)特解，是（3.2.1）的通解，則（3.2.2）的通解為（證）（1）是解；（2）是通解。（類(lèi)似齊次情形）意義：?jiǎn)栴}歸結(jié)為求非齊次遞推關(guān)系的特解。（二） 待定系數(shù)法目的：求特解困難：無(wú)一般通用方法特例：當(dāng)自由項(xiàng)f(n)比較簡(jiǎn)單時(shí)，采用待定系數(shù)法（一）f(n)b（b為常數(shù)）m表示1是m重特征根。若1不是特征根（即m0），則A。（二）（b為常數(shù)）m表示b是m重特征根。若b不是特征根，則。（三），其中為關(guān)于n的r次多項(xiàng)式，b為常數(shù)。是與同次的多項(xiàng)式，m是b為特征根的重?cái)?shù)。當(dāng)b不是特征根時(shí)，。（三） 例【例3.2.6】求非齊次方程an13 an212an33的通解。（解）分析：方程右邊為常數(shù)3特征方程： q313q120特征根： q1，3，-4，m1特解： An（A稱(chēng)為待定系數(shù)）代入遞推關(guān)系： An13A(n2)12A(n3)3整理得 10A3解之 A，故為通解：B1B23 nB3(4) nn。其中B1、B2、B3為任意常數(shù)?！纠?.2.7】求遞推關(guān)系an4 an14an22n 的通解。（解）分析：方程右邊為特征根： q2（二重根），特解： An2 2n代入原式：A4A4A展開(kāi)：An22A(n22n1)2A(n24n4)2整理： 2A待定系數(shù)： A通解：B1B2nn2。其中B1、B2為任意常數(shù)?！纠?.2.8】求an4an1an2n(n1) 的通解。（解）分析：方程右邊為多項(xiàng)式：f(n)n2n（b1）特征根： q2（b1不是特征根）特解： An2 BnC代入原方程：4n(n1)整理： 6An2 6(2AB)n2(4A3B3C)n2n比較兩邊同類(lèi)項(xiàng)的系數(shù)：解得 A，B，C通解：。其中B1、B2為任意常數(shù)。（四） 化非齊次方程為齊次方程 【例3.2.9】求。（解）（1）滿足的遞推關(guān)系 注：不能用迭代法求解。（2）化為齊次遞推關(guān)系改寫(xiě)遞推關(guān)系 類(lèi)似得 得 同理 得 規(guī)律：左邊升階，右邊降階。（3）求解特征根：q1是三重根。代初值： A0， BC 用遞推關(guān)系證明了求和公式（五） 一般求和公式（1）問(wèn)題：求（2）化為齊次遞推關(guān)系求解首先，當(dāng)r1時(shí)，由（四）知當(dāng)r2時(shí)，可得 得 得 就得關(guān)于的齊次定解問(wèn)題特征根仍然是q1（四重），所以再利用初值條件得（3）快速求常數(shù)A、B、C、D等當(dāng)r1時(shí)，令代入初始條件后得 解得 A0，B1A1，C(3A2B) 優(yōu)點(diǎn)：不需要解線性代數(shù)方程組，即可逐步遞推地解出系數(shù)A、B、C等。另法：令代入初值條件 解得 A0，B1A1，C3A2B1優(yōu)點(diǎn)：在利用初值確定A、B、C時(shí)更加方便。因?yàn)榉匠讨蟹謩e關(guān)于A、B、C的系數(shù)恰好是1，不做除法。當(dāng)r2時(shí)，可令代入初值得方程組A0， B1， C3， D2對(duì)于較大的r，求部分和時(shí)，利用非齊次遞推關(guān)系求解還是要比將其化為齊次遞推關(guān)系方便得多。（4）一般情形若通解為r階多項(xiàng)式，對(duì)定解問(wèn)題（3.1.2），可令使得用初值條件求解常數(shù)非常簡(jiǎn)單。3.2.5 一般遞推關(guān)系化簡(jiǎn)對(duì)于某些非線性或變系數(shù)的遞推關(guān)系，可以將其化為線性關(guān)系來(lái)求解?！纠?.2.10】解定解問(wèn)題 （解）線性變系數(shù)一階齊次關(guān)系。改寫(xiě)兩邊取對(duì)數(shù)： 令，得再令，?；癁閮蓚€(gè)遞推關(guān)系 和 用迭代法解，得，用待定系數(shù)法解，得。從而得 【例3.2.11】解定解問(wèn)題 （解）線性變系數(shù)一階非齊次關(guān)系。令得 通解為 由初始條件 知 即【例3.2.12】解定解問(wèn)題 。（解）線性變系數(shù)一階非齊次遞推關(guān)系。難點(diǎn)： 觀察： 令，化為 特解： ， 通解： 的通解： 另法：對(duì)于，可以用迭代法或直接觀察出，再用歸納法證明之即可。【例3.2.13】設(shè)n1時(shí)，0，解定解問(wèn)題。（解）常系數(shù)非線性二階遞推關(guān)系。令，變?yōu)椋?，解之得，從而。3.3 解遞推關(guān)系的其它方法3.3.1 迭代法與歸納法適應(yīng)情況：1. 迭代法：對(duì)某些一階的遞推關(guān)系，使用迭代法求解可能更快。2. 歸納法：觀察n比較小時(shí)的表達(dá)式的規(guī)律，總結(jié)或猜出的一般表達(dá)式，然后用歸納法證明?！纠?.3.1】（解）變換 逐步迭代： 當(dāng)n0時(shí)，上式仍成立（即滿足所給的初值），故解為另法：先做變量代換（n1, 2, ），得 迭代求解： ， 然后反代回去得 ， 【例3.3.2】解遞推關(guān)系。（解） 因 ，迭代得 所以 當(dāng)n0時(shí)，上式仍成立，故定解問(wèn)題的解為【例3.3.3】解遞推關(guān)系。（解）由題設(shè)所以 ， ，當(dāng)k0時(shí)，上面兩個(gè)式子仍成立。故或 ， 【例3.3.4】用歸納法解遞推關(guān)系， （解）計(jì)算較小n時(shí)的，并觀察得由此可猜想再用歸納法證之：顯然n0，1，2，3時(shí)結(jié)論為真。假設(shè)nk時(shí)結(jié)論為真，即成立。 考慮nk1時(shí) 結(jié)論成立。故對(duì)一切非負(fù)整數(shù)n，有。3.3.2 母函數(shù)方法思路：對(duì)較復(fù)雜的遞推關(guān)系，利用母函數(shù)求解。方法：l 設(shè)欲求解的數(shù)列 an 的母函數(shù)為G(x)；l 利用遞推關(guān)系本身求函數(shù)G(x)滿足的方程（代數(shù)方程或微分方程等）；l 解方程求出G(x)；l 將G(x)展開(kāi)成x的冪級(jí)數(shù)。則xn的系數(shù)便是an的解析表達(dá)式（即遞推關(guān)系的解）?！纠?.3.5】解遞推關(guān)系an5an16an22n， n2（解）（利用無(wú)窮求和）：令A(yù)(x)，原方程兩邊同乘xn得即 對(duì)n從2到求和得5656(A(x)a0a1x）5x(A(x)a0)6x2A(x)(12x)解之得A(x)A(x)將A(x)展開(kāi)A(x)c22 比較等式兩端xn的系數(shù)(n1)式中c1、c2為任意常數(shù)，由初值a0和a1確定。例如，設(shè)a01，a12，則c1、c2滿足下列方程組解得c10，c23 .因此滿足上述初值條件的遞推關(guān)系的解為3(n1) (12n) 【例3.3.6】求定解問(wèn)題 .（解）（思路：拆項(xiàng)）。反推求 F0F2F10設(shè) Fn的母函數(shù)為G(x)根據(jù)遞推關(guān)系有G(x)0xxG(x)xx G(x)x2 G(x)G(x) （3.3.1）利用“待定系數(shù)法”展開(kāi)G(x)為冪級(jí)數(shù)，G(x)G(x)得A、B應(yīng)滿足的方程 解之得 A，B G(x)展開(kāi)G(x)，令，G(x) Fn說(shuō)明：l 此為著名的Fibonacci數(shù)列（見(jiàn)3.4）。l 一個(gè)事實(shí)，雖然Fn都是正整數(shù)，但它們卻可由一些無(wú)理數(shù)表示出來(lái)。 【例3.3.7】解定解問(wèn)題。（解）根據(jù)方程的特點(diǎn)，令A(yù)(x)a1a2xa3x2a4x3an兩邊對(duì)x求導(dǎo)A(x)2a3x3a4x2(n1)an（注意由原問(wèn)題知a20），計(jì)算A(x)x A(x)，得(1x)A(x)2a3x(3a42a3)x2(4a53a4)x3(n1)an(n2)an12a1x2a2 x22a3 x32an22x A(x)（注意原方程可化為 (n1)an(n2)an12an2，a3a1）即 2注意到，兩邊對(duì)x積分得2x2ln(1x)即 lnA(x)ln(1x)22x A(x)(1x)2展成冪級(jí)數(shù)A(x) an1 【例3.3.8】（用指母函數(shù)求解）：求解遞推關(guān)系（解）由原方程反推可得D0D1(1)01。觀察：Dn隨n的增大而急劇增大，有點(diǎn)象n!，故用指母函數(shù)。令 D(x) 用乘以原方程的兩端，并對(duì)n從1到求和，得與母函數(shù)比較 D(x)D0xD(x)1亦即 D(x)由母函數(shù)的性質(zhì)3 Dn 【例3.3.9】用母函數(shù)方法求解二.（解）設(shè)數(shù)列、的母函數(shù)分別為、。方程一兩邊同乘以得 兩邊對(duì)求和： 即 32代入初值并整理： (13)21 同理，由方程二可得 (1)0 聯(lián)立方程、解之函數(shù)分解：冪級(jí)數(shù)展開(kāi)解為 3.4 三種典型數(shù)列Fibonacci數(shù)列、Stirling數(shù)列和Catalan數(shù)列經(jīng)常出現(xiàn)在組合計(jì)數(shù)問(wèn)題中，是比較典型的三種數(shù)列。其典型性還不在于數(shù)列本身，是在于許多實(shí)際計(jì)數(shù)問(wèn)題的計(jì)算關(guān)系都與這三種數(shù)列是相同或相似的。3.4.1 Fibonacci數(shù)列（一） 背景定義：序列1，1，2，3，5，8，13，21，34，中，每個(gè)數(shù)都是它前兩者之和，這個(gè)序列稱(chēng)為Fibonacci數(shù)列。意義：由于它在算法分析和近代優(yōu)化理論中起著重要作用，又具有很奇特的數(shù)學(xué)性質(zhì)，因此，1963年起美國(guó)就專(zhuān)門(mén)出版了針對(duì)這一數(shù)列進(jìn)行研究的季刊Fibonacci Quarterly.來(lái)源：1202年由意大利著名數(shù)學(xué)家Fibonacci提出的一個(gè)有趣的兔子問(wèn)題：有雌雄一對(duì)小兔，一月后長(zhǎng)大，兩月起往后每月生 （雌雄）一對(duì)小兔。小兔亦同樣如此。設(shè)一月份只有一對(duì)小兔，問(wèn)一年后共有多少對(duì)兔子？一般化：?jiǎn)杗個(gè)月后共有多少對(duì)兔子？設(shè)第n個(gè)月的兔子數(shù)為Fn，則F1F21.月份1234n2n1nn1小兔子數(shù)111Fn2大兔子數(shù)112Fn2Fn1總數(shù)1123Fn2Fn1FnFn前一個(gè)月兔子數(shù)本月新增兔子數(shù)Fn1Fn2即 （3.4.1）（二） 求解Fn 或 （三） 應(yīng)用【例3.4.1】（上樓梯問(wèn)題）某人欲登上n級(jí)樓梯，若每次只能跨一級(jí)或兩級(jí)，問(wèn)他從地面上到第n級(jí)樓梯，共有多少種不同的方法？（解）設(shè)上到第n級(jí)樓梯的方法數(shù)為an。分類(lèi)統(tǒng)計(jì)：（1） 第一步跨一級(jí)，則余下的n1級(jí)有an1種上法；（2） 第一步跨兩級(jí)，則余下的n2級(jí)有an2種上法。由加法原理 （反推得）。F1F2F3F4F5F6112358a1a2a3a4A5【例3.4.2】（棋盤(pán)染色問(wèn)題）給一個(gè)具有1行n列的1n棋盤(pán)（見(jiàn)圖3.4.1）的每一個(gè)方塊涂以紅、藍(lán)二色之一，要求相鄰的兩塊不能都染成紅色，設(shè)不同的染法共有種，試求。123n1n圖3.4.1 1n棋盤(pán)（解）分類(lèi)統(tǒng)計(jì)，對(duì)格子1的染色有兩種可能：（1） 染紅色：染色方式總數(shù)11；123n（2） 染藍(lán)色：染色方式總數(shù)1123n由加法原理（）F1F2F3F4F5F6112358a1a2a3a4類(lèi)似問(wèn)題：無(wú)兩個(gè)1相連的n位二進(jìn)制數(shù)共有個(gè)?！纠?.4.3】（交替子集問(wèn)題）有限整數(shù)集合的一個(gè)子集稱(chēng)為交替的，如果按上升次序列出其元素時(shí)，排列方式為奇、偶、奇、偶、。例如1，4，7，8和3，4，11都是，而2，3，4，5則不是。令表示交替子集的數(shù)目（其中包括空集），證明且有（證）初值：，對(duì)應(yīng)的交替子集和1。，對(duì)應(yīng)的交替子集、1、1，2。分析：將的所有子集分為兩部分：（1）的所有子集；（2）的每一個(gè)子集加入元素n后所得子集。舉例：n4，的所有子集劃分為兩類(lèi)（i） 、1、2、3、1，2、1，3、2，3、1，2，3（ii） 4、1，4、2，4、3，4、1，2，4、1，3，4、2，3，4、1，2，3，4第一部分，即的交替子集數(shù)為。第二部分中的交替子集的交替子集，有個(gè)。對(duì)應(yīng)關(guān)系為給的交替子集加上n或n與n1即可。， ， 的遞推關(guān)系為 解與例3.4.2同 【例3.4.4】（棋盤(pán)的（完全）覆蓋問(wèn)題）用規(guī)格為12的骨牌覆蓋pq的方格棋盤(pán)，要求每塊骨牌恰好蓋住盤(pán)上的相鄰兩格。所謂完全覆蓋是指對(duì)棋盤(pán)的一種滿覆蓋（即盤(pán)上所有格子都被覆蓋），而且骨牌不互相重疊。容易看出，一定存在對(duì)2n棋盤(pán)的完全覆蓋?，F(xiàn)在的問(wèn)題是，究竟有多少種不同的完全覆蓋方案？（解）設(shè)所求方案數(shù)為。對(duì)最左面的四格有且僅有兩種可能的覆蓋方式：（1） 一塊骨牌豎著放：等價(jià)于2（n1）棋盤(pán)的完全覆蓋問(wèn)題，有1種方案；111213141n212223232n（2） 一塊骨牌橫著放：等價(jià)于2（n2）棋盤(pán)的完全覆蓋問(wèn)題。有11種方案。111213141n212223232n圖3.4.2 2n棋盤(pán)由加法原理 3.4.2 Stirling數(shù)列（一） Stirling數(shù)（1） 下階乘函數(shù)，1（2） 遞歸定義，（3） （下階乘函數(shù)）與冪函數(shù)的關(guān)系：互相表示， ， ， ， ，例 （4） Stirling數(shù)【定義3.4.1】設(shè)， ，則稱(chēng)、分別為第一類(lèi)和第二類(lèi)Stirling數(shù)。（5） 說(shuō)明數(shù)列的普母函數(shù)即為下階乘函數(shù)，其基函數(shù)為。反之以為基函數(shù)，定義一種母函數(shù)，數(shù)列的這種母函數(shù)就是（二） 組合意義等價(jià)定義（1）分配問(wèn)題：將n個(gè)有區(qū)別的球放入m個(gè)相同的盒子，要求各盒不空，則不同的放法總數(shù)為；（2）集合的劃分：將含有n個(gè)元素的集合恰好分成m個(gè)無(wú)序非空子集的所有不同劃分的數(shù)目即為。這種劃分也稱(chēng)為集合的m劃分。（三） 性質(zhì)【定理3.4.1】第一類(lèi)Stirling數(shù)的性質(zhì)：（1）， （2），（3）， （4），（5），（6）滿足遞推關(guān)系（證）由的表達(dá)式即知（1）（5）成立。，1（6）由遞歸定義 ，左右各自展開(kāi)比較等式兩端同次冪的系數(shù)。利用的性質(zhì)，可以像楊輝三角形那樣寫(xiě)出第一類(lèi)Stirling數(shù)值表（見(jiàn)表3.4.1）。 表3.4.1 的數(shù)值表kn123451121132314611615245035101【定理3.4.2】第二類(lèi)Stirling數(shù)有如下性質(zhì)：（1），n>0 ； （2），n1；（3）； （4）；（5）；（6）（證）（1）（3），顯然。（4）n個(gè)球放入n1個(gè)盒，各盒不空，必有一盒有兩個(gè)球。從n個(gè)相異的球中選取2個(gè)，共有種組合方案。（5）n個(gè)球，2個(gè)盒。任取某一球x，其余的n1個(gè)球每個(gè)都有兩種可能的放法，即與x同盒或不同盒。故有種可能。但要排除大家都與x同盒的情形（這時(shí)另一盒將空），故總的放法有種。（6）從n個(gè)球中任選一個(gè)記為x，方案分兩類(lèi)：（a）x獨(dú)占一盒：有種放法；（b）x不獨(dú)占一盒：第一步：其余n1個(gè)球放入k個(gè)盒子，各盒不空，放法有種；第二步：將x放入其中某盒，放法有k種。由乘法原理，放法有種。表3.4.2 的數(shù)值表kn1234511211313141761511525101其它結(jié)論：（1），（2）.（四） 應(yīng)用【例3.4.5】所有從1,2,n1中取nk個(gè)不同數(shù)的積之和是多少？例如，所有從1, 2, 3, 4中取2個(gè)不同整數(shù)的積之和是（n5，k3)12131423243435（解）設(shè)和數(shù)為f(n,k)，分類(lèi)統(tǒng)計(jì)：第一類(lèi)：含有因子n1的項(xiàng)。其和為(n1)f(n1,k)，即從所有從1,2,n2中取(nk)1(n1)k個(gè)不同整數(shù)的積之和，再乘以n1得出。第二類(lèi)：不含n1的項(xiàng)。其和為f(n1,k1)，即所有從1,2,n2中取nk(n1)(k1)個(gè)不同整數(shù)的積之和。由加法法則得為使上式對(duì)k1和kn1都成立，規(guī)定，從而有令，可得與的性質(zhì)比較，即知g(n,k)。 【例3.4.6】Stirling數(shù)的另一個(gè)重要應(yīng)用就是分配問(wèn)題：即將n個(gè)球（物體）放入k個(gè)盒子，其放法的總數(shù)可以分成8種情況分別予以討論（見(jiàn)表3.4.3）。表3.4.3. 分配問(wèn)題方案計(jì)數(shù)表n個(gè)球k個(gè)盒是否空盒不同的方案數(shù)有區(qū)別不同是否相同是，rmin(n,k)否無(wú)區(qū)別不同是C(nk1，n)否C(n1, k1)相同是展開(kāi)式中xn的系數(shù)否展開(kāi)式中xn的系數(shù)說(shuō)明：，上述8種情形不包括所有的分配模型，例如：（1）在情形1中考慮球的次序，方案數(shù)應(yīng)為（2）對(duì)情形1，每個(gè)盒中最多只能放入一個(gè)球，方案數(shù)為，而不是。3.4.3 Catalan數(shù)列（一） 定義滿足遞推關(guān)系 （3.4.2） 的數(shù)列稱(chēng)為Catalan數(shù)列。其解為。值 1，1，2，5，14，42，132，429，1430，4862，16796，（二） 求解（解）設(shè)母函數(shù)為A(x)，即，則 ，由于，而，舍去利用泰勒展開(kāi)式f(x)得 （三） 應(yīng)用【例3.4.7】（凸n邊形的剖分）Euler在精確計(jì)算對(duì)凸n邊形的不同的對(duì)角線三角剖分的個(gè)數(shù)問(wèn)題時(shí)，最先得到了這個(gè)數(shù)列。其問(wèn)題是：將凸n邊形用不相交的對(duì)角線分成三角形，有多少種不同的分法？例如，五邊形就有五種剖分方案（見(jiàn)圖3.4.3）。圖 3.4.3 凸五邊形的剖分方案（解）凸多邊形指該多邊形內(nèi)的任意不相鄰兩點(diǎn)的連線都在多邊形內(nèi)部。（1）求滿足的遞推關(guān)系設(shè)凸n邊形的對(duì)角三角形剖分的個(gè)數(shù)為。顯然，n3且，。當(dāng)時(shí)，設(shè)凸n1邊形的頂點(diǎn)依次為v1, v2, , vn1，固定一條邊，再另取一個(gè)頂點(diǎn)vk（k2,3,n），作三角形，它分多邊形為兩個(gè)較小的凸多邊形。一個(gè)是凸k邊形，其剖分?jǐn)?shù)為，另一個(gè)是nk2邊形，其剖分?jǐn)?shù)為（見(jiàn)圖3.4.4（a），由乘法原理和加法原理知 （3.4.3）其中規(guī)定。圖 3.4.4 任意凸多邊形的剖分（2）求解令，得的定解問(wèn)題 則，【例3.4.8】設(shè)P為n個(gè)數(shù)的連乘積，保持原來(lái)的排列順序，試問(wèn)有多少種不同的結(jié)合方案（即根據(jù)乘法的結(jié)合律插入n1對(duì)括號(hào)，使得每對(duì)括號(hào)內(nèi)為恰好是兩個(gè)因子的乘積。如n4，P.（解）分析：設(shè)為插入n1對(duì)括號(hào)的方案數(shù)。對(duì)于的每一種結(jié)合方案，其最后的那次乘法運(yùn)算，必是的相乘結(jié)果P1和的結(jié)果P2兩項(xiàng)相乘，即最外層括號(hào)所含的兩個(gè)因子P1和P2。對(duì)于固定的k，P1有種不同的結(jié)合方案，P2則有種。例子P，P1，P2，P，P1，P2結(jié)論 求解 。事實(shí)上，n個(gè)數(shù)連乘積的結(jié)合方案與凸n1邊形的三角形剖分是一一對(duì)應(yīng)的。圖3.4.5給出了n4時(shí)的對(duì)應(yīng)情形類(lèi)似的問(wèn)題：在n項(xiàng)求和式中，不改變各數(shù)的相對(duì)排列次序，只給其插入括號(hào)，改變求和順序，不同的結(jié)合方案數(shù)也是n4時(shí)連乘積與凸5邊形三角剖分的對(duì)應(yīng)關(guān)系【例3.4.9】具有n個(gè)結(jié)點(diǎn)的所有不同的二叉樹(shù)的個(gè)數(shù)是（解）特點(diǎn)：每個(gè)結(jié)點(diǎn)都是一棵子樹(shù)的根，而且它至多有兩棵子樹(shù)。因此可以歸納定義二叉樹(shù)為結(jié)點(diǎn)的有限集合，該集合或者是空集，或者是由一個(gè)根（一個(gè)特定結(jié)點(diǎn)）及兩個(gè)不相交的被稱(chēng)作這個(gè)根的左子樹(shù)和右子樹(shù)所組成。令表示n個(gè)結(jié)點(diǎn)的二叉樹(shù)總數(shù)，則。特例：含有3個(gè)結(jié)點(diǎn)的所有不同的二叉樹(shù)。一般情形：二叉樹(shù)有一個(gè)根結(jié)點(diǎn)及n1個(gè)非根結(jié)點(diǎn)，后者又可分為兩個(gè)子集，分別構(gòu)成左子樹(shù)和右子樹(shù)。不失一般性，設(shè)左子樹(shù)有k個(gè)結(jié)點(diǎn)，則右子樹(shù)有n1k個(gè)結(jié)點(diǎn)。左子樹(shù)的所有可能的二叉樹(shù)的數(shù)目是，右子樹(shù)的所有可能的二叉樹(shù)的數(shù)目是 （k0,1,n1） 。所以求解：令，得即 所以，即【例3.4.10】有n個(gè)結(jié)點(diǎn)的所有不同的有序樹(shù)的個(gè)數(shù)是。（解）有序樹(shù)是實(shí)際硬用中另一種重要的樹(shù)形結(jié)構(gòu)。當(dāng)一棵樹(shù)中任何一個(gè)結(jié)點(diǎn)的諸子樹(shù)的相對(duì)次序要考慮時(shí)，它就是有序樹(shù)。眾所周知，任何一個(gè)有序樹(shù)都可用二叉樹(shù)表示。同時(shí)注意到，這棵二叉樹(shù)的根的右子樹(shù)是空二叉樹(shù)，故具有n個(gè)結(jié)點(diǎn)的有序樹(shù)和具有n1個(gè)結(jié)點(diǎn)的二叉樹(shù)之間存在一一對(duì)應(yīng)的關(guān)系。因此，有n個(gè)結(jié)點(diǎn)的有序樹(shù)的個(gè)數(shù)為，即。特例：4個(gè)結(jié)點(diǎn)的有序樹(shù)共有個(gè)，分別與有3個(gè)結(jié)點(diǎn)的二叉樹(shù)一一對(duì)應(yīng)。 對(duì)應(yīng)規(guī)則：有序樹(shù)的長(zhǎng)子樹(shù)作二叉樹(shù)的左子樹(shù)，次弟作右子樹(shù)。【例3.4.11】由n個(gè)1和n個(gè)0組成的2n位的二進(jìn)制數(shù)，要求從左向右掃描，1的累計(jì)數(shù)不小于0的累計(jì)數(shù)，試求這樣的二進(jìn)制數(shù)有多少？（解）解法一：設(shè)滿足條件的二進(jìn)制數(shù)有個(gè)。將其視為由字符0和1構(gòu)成的二進(jìn)制串，現(xiàn)分類(lèi)統(tǒng)計(jì)其個(gè)數(shù)如下：設(shè)從左向右掃描到第2k位時(shí)（1kn），第一次出現(xiàn)了0的個(gè)數(shù)等于1的個(gè)數(shù)。那么在此之前，掃描到任何一位時(shí)，1的個(gè)數(shù)總是大于0的個(gè)數(shù)。例如下面的二進(jìn)制串：1110001100（k3），1101001100（k3），1101010010（k4），1101010100（k5）設(shè)具有這種性質(zhì)的串有個(gè)，則這是因?yàn)榭梢詫⒎项}目要求的串分為前后兩個(gè)子串，前子串共2k位，后子串有2(nk)位。首先，由題目的條件知，后子串也是符合題目要求的二進(jìn)制串，只是其長(zhǎng)度為2(nk)，故有個(gè)。其次，針對(duì)前子串，由其性質(zhì)知，當(dāng)去掉第1位和第2位時(shí)，剩下的2(k1)位串也符合題目條件，故前子串有個(gè)。 由乘法法則，具有此性質(zhì)的串共有個(gè)。而相應(yīng)于不同的k值（k1,2,n），兩類(lèi)這樣的二進(jìn)制串不可能互相有重復(fù)的情況，故由加法法則，所求的串的個(gè)數(shù)為且有1。另外，觀察上式，可知應(yīng)有1。參照例3.4.9中關(guān)于數(shù)列所滿足的遞推關(guān)系的解法，可知解法二：用排列組合的方法求解。詳見(jiàn)本教材的配套資料組合數(shù)學(xué) 學(xué)習(xí)指導(dǎo)書(shū)中關(guān)于第一章習(xí)題32的求解過(guò)程。3.5 應(yīng) 用【例3.5.1】求下列行列式的值。（解）利用行列式的性質(zhì)，將其按第一行展開(kāi)得21再將第二個(gè)n1階行列式按第一列展開(kāi)得2即故得定解問(wèn)題 特征根 x1（二重），通解其中A、B為任意常數(shù)，代入初值得，所以即n1.【例3.5.2】（錯(cuò)排問(wèn)題）n個(gè)有序元素的一個(gè)排列，若每個(gè)元素都不在其原來(lái)應(yīng)在的位置，則稱(chēng)該排列為錯(cuò)位排列，簡(jiǎn)稱(chēng)錯(cuò)排。具體地說(shuō)，如自然數(shù)1，2，n本身就是一個(gè)由小到大的有序排列，現(xiàn)在打亂順序重排，要求數(shù)不在第個(gè)位置，就是錯(cuò)位排列。求所有錯(cuò)位排列的數(shù)目Dn，就是錯(cuò)排問(wèn)題。（1）n較小時(shí)的Dnn1，1的錯(cuò)排數(shù)為D10.n2，12的錯(cuò)排為 21，錯(cuò)排數(shù)D21.n3，123的錯(cuò)排為： 312和231，錯(cuò)排數(shù)D3兩個(gè)錯(cuò)排可以理解為在自然排列123中先將12錯(cuò)排后得213，再在213中將3分別與1或2互換位置而得。n4，錯(cuò)排情形分為三種（共兩類(lèi)）（1）4321，3412，2143：4分別與1，2，3中某一個(gè)互換位置，其余兩元素錯(cuò)排；（2.1）4123，3421，3142： 4與123的一個(gè)錯(cuò)排312構(gòu)成3124，再將4分別與各數(shù)互換；（2.2）4312，2413，2341：針對(duì)123的錯(cuò)排231，方法同（2.1）。（2）一般規(guī)律由此可以看出產(chǎn)生錯(cuò)排的一種方法：針對(duì)n個(gè)數(shù)1n的自然順序排列12n ，任取其中一數(shù)（n），將所有錯(cuò)排分為兩類(lèi)：1）與其它某數(shù)互換位置后，其余的n2個(gè)數(shù)錯(cuò)排，共得(n1) Dn2個(gè)錯(cuò)排；2）在原位置不動(dòng)，其它n1個(gè)數(shù)先錯(cuò)排，然后再與其中每一個(gè)數(shù)互換位置可得(n1) Dn1個(gè)錯(cuò)排。（3）Dn的遞推關(guān)系反推可知，D0 1。（4）Dn的不同表示可以證明Dn與滿足遞推關(guān)系的數(shù)列是同一數(shù)列。即T1，T2（5）求解解之得（見(jiàn)；例3.3.4） Dn n! 當(dāng)n充分大時(shí)，可得Dn的非常簡(jiǎn)單的近似公式Dn （n>>1） 且這是因?yàn)閚!n! << Dn， 即Dn 【例3.5.3】（經(jīng)濟(jì)模型） 由諾貝爾獎(jiǎng)獲得者Paul Samuelson于1939年提出。an第n年國(guó)民總收入，g(n) 政府支出，cn私人消費(fèi)支出，私人的投資。，基本假設(shè)： cn與an1成正比，即按照經(jīng)濟(jì)學(xué)的說(shuō)法，常數(shù)稱(chēng)為消費(fèi)的臨界傾向。再設(shè) 式中是非負(fù)常數(shù)，稱(chēng)為加速系數(shù)。所以從而對(duì)一切n2，有即【例3.5.4】某粒子反應(yīng)器內(nèi)有高能自由粒子，低能自由粒子和核子3種，假設(shè)一個(gè)高能粒子撞擊一個(gè)核子且被吸收引起它放射出3個(gè)高能粒子和一個(gè)低能粒子，一個(gè)低能粒子撞擊核子且被吸收并引起它放出兩個(gè)高能粒子和一個(gè)低能粒子。設(shè)開(kāi)始n0微妙時(shí)，在具有核子的系統(tǒng)里放入一個(gè)高能粒子，問(wèn)第n微妙時(shí)系統(tǒng)中高能、低能粒子各有多少？（解）設(shè)第n微妙時(shí)，系統(tǒng)里有高能自由粒子an個(gè)，低能自由粒子bn個(gè)，由條件知a0 1， b0 0并有遞推關(guān)系解之得【例3.5.5】核反應(yīng)堆中有，兩種粒子，每單位時(shí)間，一個(gè)粒子分裂為3個(gè)粒子，1個(gè)粒子分裂為2個(gè)粒子和一個(gè)粒子，假設(shè)t0時(shí)刻，反應(yīng)堆中只有1個(gè)粒子，那么，在t 100時(shí)刻，該反應(yīng)堆中、粒子各有多少，總數(shù)為何?（解）設(shè)tn時(shí)刻，粒子有an個(gè)，粒子有bn個(gè)，由題意可得定解問(wèn)題由上可得anbn13 an22 bn23 an22 an1b0a10，于是， an 的定解問(wèn)題為用特征根法解之得從而所以在第n時(shí)刻時(shí)反應(yīng)堆的總粒子數(shù)為那么，在第100時(shí)刻堆內(nèi)的總粒子數(shù)是。另法：就堆內(nèi)總粒子數(shù)而言，由于粒子和粒子都是分解為3個(gè)粒子，故t 1時(shí)刻，共有3個(gè)粒子（3個(gè)），t2時(shí)刻共有3332個(gè)粒子（32個(gè)個(gè)粒子，3個(gè)粒子），到tn時(shí)刻，應(yīng)為3n個(gè)粒子?！纠?.5.6】（信號(hào)傳輸）在信道上傳輸a，b，c構(gòu)成的字符串（長(zhǎng)度為n），兩個(gè)a相連的串不能傳，求允許傳輸?shù)拇膫€(gè)數(shù)。（解）用表示該信道允許傳的長(zhǎng)度為n的串的個(gè)數(shù)，顯然，a1 3，a23218，當(dāng)n3時(shí)，將符合要求的串分為兩類(lèi)：第一類(lèi)： 第一字母不是a的串有2 an1個(gè)；第二類(lèi)： 首字母為a，次字母必為b或c，這樣的串有2 an2個(gè)。綜合以上情況有類(lèi)似的問(wèn)題：兩個(gè)0不能相連的三進(jìn)制串的個(gè)數(shù)一般情形：設(shè)兩個(gè)0不能相連的p進(jìn)制串的個(gè)數(shù)為，則有【例3.5.7】一個(gè)圓形區(qū)域分成n個(gè)扇形區(qū)域，用k種顏色涂這些扇形，使相鄰的扇形沒(méi)有相同的顏色，問(wèn)共有多少種染法？（解）令an表示n個(gè)扇形的所有滿足條件的染法數(shù)目，表示這n個(gè)扇形，扇形Rn的涂色方法，至多有兩種情況：第一種情況：Rn1和R1同色，這時(shí)Rn有k1種顏色可供選擇，并且扇形R1至Rn2有an2種涂色方法，所以共有(k1) an2種染法。第二種情況：Rn1和R1異色，這時(shí)Rn有n2種顏色可供選擇，并且扇形R1至Rn1有an1種涂色方法。所以共有(k2) an1種染法，故知涂色方法總數(shù)的遞推方程為：解之得 【例3.5.8】平面上有n個(gè)圓（n2），任何兩個(gè)圓都相交但無(wú)3個(gè)圓共點(diǎn)，問(wèn)這n個(gè)圓把平面劃分成多少個(gè)不連通的區(qū)域？（解）設(shè)這n個(gè)圓把平面劃分成an個(gè)不連通的區(qū)域。初值：a01，a12，a24。分析：當(dāng)n2時(shí)，n1個(gè)圓把平面劃分成an1個(gè)不連通的區(qū)域。新加入的圓C與其余n1個(gè)圓都相交，且所得的2(n1)個(gè)交點(diǎn)彼此相異（因無(wú)3個(gè)圓共點(diǎn)），這2(n1)個(gè)交點(diǎn)把圓C分成2(n1)段弧，每段弧把原來(lái)的一個(gè)區(qū)域劃分成兩個(gè)小區(qū)域，故增加了2(n1)個(gè)區(qū)域，從而an滿足遞推關(guān)系解之得 顯見(jiàn)當(dāng)n1時(shí)，上式仍成立。 【例3.5.9】【例3.5.10】（排序算法）應(yīng)用：據(jù)統(tǒng)計(jì)，在計(jì)算機(jī)的全部運(yùn)行時(shí)間里，幾乎有1/4時(shí)間是用在排序上。排序問(wèn)題：給定n個(gè)數(shù)ai， ai存放于在單元K(i) （i1，2，n） ，要求按遞增次序?qū)ζ渲匦屡帕??！舅惴ㄒ弧恐苯舆x擇排序：基本思路：第一步從n個(gè)數(shù)中選出最大者，將它與K(n)中的數(shù)交換位置（此時(shí)K(n)存放的是最大的數(shù)）；第二步，對(duì)余下的n1個(gè)數(shù)，遞歸地重復(fù)執(zhí)行上述做法，選出其中最大者，與K(n1)中的數(shù)交換；。經(jīng)過(guò)n1步后，就達(dá)到了排序目的。例 4 6 7 2 5 1 3 4 6 3 2 5 1 7復(fù)雜性：僅用元素的比較次數(shù)來(lái)計(jì)算它的時(shí)間復(fù)雜性。時(shí)間復(fù)雜度：令T(n)表示用直接選擇排序法將n個(gè)元素排序所需的比較次數(shù)。那么，第一步在n個(gè)數(shù)中找最大者，需要比較n1次。算法執(zhí)行一步后，對(duì)余下個(gè)n1個(gè)元素再排序需要次比較。由加法法則解之得 T(n)(n1)O(n2)【算法二】分治合并排序：本算法是分治策略在排序問(wèn)題上的應(yīng)用?；舅枷耄喊汛判虻臄?shù)列（設(shè)n2m）劃分成大小相同的兩個(gè)子序列 和 分別對(duì)每個(gè)子序列中的數(shù)按遞增次序進(jìn)行排序，然后再把這兩個(gè)排好序的子序列合并成一個(gè)遞增數(shù)列，算法是遞歸進(jìn)行的。當(dāng)對(duì)兩個(gè)已排好序的子序列進(jìn)行合并時(shí)，把每個(gè)子序列的最大數(shù)取出來(lái)進(jìn)行比較，所得的較大數(shù)便是合并后的序列中的最大者。復(fù)雜度：不難證明，將長(zhǎng)為n/2的兩個(gè)子序列合并成一個(gè)長(zhǎng)為n的序列所需的比較次數(shù)最多為n1次。例 8 4 6 7 2 5 1 3 4 6 7 8 1 2 3 58 4 6 7 2 5 1 3 4 8 6 7 2 5 1 3由加法法則，使用分治合并算法將n個(gè)元素排序在最壞情況下需要的比較次數(shù)T(n)滿足迭代求解 即 T(n) 類(lèi)似地，不難證明，在最好情況下用本算法所需要的比較次數(shù)為?？傊?，分治合并算法的比較次數(shù)是與同階的。所以，當(dāng)n充分大時(shí)，與直接選擇算法相比，本算法要快得多。【算法三】快速排序：由C.A.R.Hoare于1962年提出。基本思想：仍采用分治策略的遞歸算法。從序列中先選某一數(shù)k ，并把它移到其應(yīng)占的正確位置上，在移的同時(shí)就對(duì)其它數(shù)進(jìn)行重新排列，原則是大于k的數(shù)放在k的右邊，小于k的數(shù)放在k的左邊（但只相對(duì)k這樣做，其它數(shù)之間暫時(shí)還不排序），以k為邊界，數(shù)列分為兩個(gè)子序列，再對(duì)子序列遞歸進(jìn)行同樣的工作。算法的復(fù)雜度問(wèn)題：（1） 最壞情形1 2 3 4 5 6 7 1 2 3 4 5 6 7設(shè)輸入的n個(gè)數(shù)本身已按遞增次序排列，此時(shí)，雖然每個(gè)數(shù)都已位于各自的正確位置上，但若對(duì)此序列應(yīng)用快速算法排序時(shí)，卻要花費(fèi)次比較。（2） 最好情形4 6 7 2 5 1 3 2 1 3 4 6 7 5序列的首項(xiàng)的正確位置恰好在整個(gè)序列的正中間，即第一步結(jié)束時(shí)，a1到位，而且序列的其余元素被分為兩個(gè)長(zhǎng)度大致相同的子序列。不僅如此，而且以后每一步結(jié)束時(shí)，都將原來(lái)的子序列分為兩個(gè)更小的長(zhǎng)度相近的子序列。這時(shí)T(n)滿足如下遞推關(guān)系其中，n1是第一步把n個(gè)數(shù)的序列一分為二時(shí)所作的比較次數(shù)。設(shè)n2m1，m為正整數(shù)，不難得到上述遞推關(guān)系的解為（3） 平均情況設(shè)C(n)為用快速排序算法對(duì)n個(gè)元素進(jìn)行排序所需比較的平均次數(shù)。那么，由于快速排序算法取輸入序列的第一個(gè)數(shù)作為劃分成兩個(gè)子序列的標(biāo)準(zhǔn)，假設(shè)每個(gè)數(shù)都以相同的概率作為序列的首項(xiàng)；若取第k個(gè)最小數(shù)作為首項(xiàng)，則一步結(jié)束時(shí)，一個(gè)子序列有k1個(gè)數(shù)