《離散數(shù)學(xué)教程》第5章 計數(shù)

離散數(shù)學(xué)第5章計數(shù)離散數(shù)學(xué)第5章計數(shù)5.1計數(shù)基本原理5.2排列與組合

5.3重集的排列與組合第5章計數(shù)5.4遞歸式及其應(yīng)用離散數(shù)學(xué)第5章計數(shù)5.1.1加法原理和乘法原理5.1計數(shù)基本原理加法原理：若對象或事件的有限集合S=S1∪S2∪…∪Sn

且S1,…,Sn兩兩不相交，那么|S|=|S1|+|S2|+…+|Sn|

另一個說法：n個獨立事件分別有a1，…，an種方式發(fā)生，那么這n個事件之一發(fā)生的方式總計為a1+…+an種。離散數(shù)學(xué)第5章計數(shù)5.1.1加法原理和乘法原理5.1計數(shù)基本原理乘法原理：若對象或事件的有限集合S是依次取自有限集合S1,S2,…,Sn中事件的序列的集合，那么|S|=|S1|?|S2|

?…

?|Sn|

另一個說法：

n個獨立事件分別有a1，…，an種不同發(fā)生方式，那么這n個事件同時發(fā)生的方式總計為a1?…?an

種。離散數(shù)學(xué)第5章計數(shù)5.1.1加法原理和乘法原理5.1計數(shù)基本原理例5.1(1)

從上海直達天津可以乘坐汽車、火車和飛機旅行。已知每天汽車有3個班次，火車有8個班次，飛機有4個班次，問每天從上海直達到天津有多少種不同的旅行方式？(2)

從上海直達天津可以乘坐汽車、火車和飛機旅行，已知汽車有3個班次，火車有8個班次，飛機有4個班次。從天津直達大連可以乘坐輪船和飛機旅行，已知輪船有2個班次，飛機有3個班次。問從上海經(jīng)天津到大連有多少種旅行方式？解

(1)3+8+4=15種(加法原理)。

(2)15·(2+3)=75種(加法原理和乘法原理)離散數(shù)學(xué)第5章計數(shù)5.1.1加法原理和乘法原理例5.2

一種彩票設(shè)計的獲獎規(guī)則是：當(dāng)你選擇的六個數(shù)字與隨機產(chǎn)生的六個數(shù)字相同，并且順序一致，獲特等獎；當(dāng)你選擇的六個數(shù)字中恰有5個與隨機產(chǎn)生的六個數(shù)字中的5個相同，并且順序一致，獲一等獎。問：你獲得特等獎、一等獎的概率分別是多大，獲獎的概率有多大

？解選取六個數(shù)字的方式：106種（乘法原理）特等獎概率：5.1計數(shù)基本原理一等獎概率：獲獎概率：0.000001＋0.000054＝0.000055離散數(shù)學(xué)第5章計數(shù)5.1.2包含排斥原理定理5.1

考慮集合S1，S2，S=S1∪S2

，那么|S|=|S1|+|S2|?|S1∩S2

|證

由于是元素個數(shù)與元素個數(shù)之和，其中的公共元素被兩次計數(shù)，所以|S|=|S1|+|S2|?|S1∩S2

|。5.1計數(shù)基本原理離散數(shù)學(xué)第5章計數(shù)5.1.2包含排斥原理定理5.2

考慮集合S1,…,Sn，S=S1∪…

∪Sn

，那么

|S|=|

S1∪…

∪Sn

|5.1計數(shù)基本原理證

n＝l時，左邊=|S1|，

右邊，因此等式成立。n＝2時，待證等式為|S|=|

S1∪…∪Sn

|，正是定理4.1。

設(shè)n=k時，等式成立，現(xiàn)對n＝k+1論證。由于n=k+1，那么離散數(shù)學(xué)第5章計數(shù)歸納完成，命題得證。5.1.2包含排斥原理5.1計數(shù)基本原理離散數(shù)學(xué)第5章計數(shù)5.1.2包含排斥原理5.1計數(shù)基本原理

111

22

23Un=3時的情況的直觀描述：離散數(shù)學(xué)第5章計數(shù)定理5.3

考慮集合，，令為或,那么定理5.4

考慮集合，已知現(xiàn)將記為或，那么5.1.2包含排斥原理5.1計數(shù)基本原理包含排斥（容斥）原理離散數(shù)學(xué)第5章計數(shù)5.1.2包含排斥原理5.1計數(shù)基本原理例5.3(1)

試計算在集合{1，2，3，…，1000}中有多少元素至少能被5，6，8這三個數(shù)中的一個整除。(2)

試計算在集合{1，2，3，…，1000}中有多少元素不能被5，6，8這三個數(shù)中的任何一個整除。解

集合{1，2，3，…，1000}中能被5，6，8這三個數(shù)整除的元素的集合分別是S5，S6，S8離散數(shù)學(xué)第5章計數(shù)（1）至少能被5，6，8這三個數(shù)中的一個整除的元素有（2）不能被5，6，8這三個數(shù)中的任何一個整除的元素有5.1.2包含排斥原理5.1計數(shù)基本原理離散數(shù)學(xué)第5章計數(shù)解

S：密鑰各位位置的集合，A、B：被4或6整除的各位位置的集合。一次未改動的密鑰位集合可表示為Aˉ∩Bˉ；改動兩次，最終與原奇偶性相同的密鑰位集合可表示為A∩B

。

|Aˉ∩Bˉ|+|A∩B|=|S|?|A|?|B|+|A∩B|+|A∩B|最終有38個密鑰位未改變奇偶性。5.1.2包含排斥原理5.1計數(shù)基本原理例5.4

已知：密鑰是長度為L=50的0，1序列，為安全起見，須對密鑰進行變換。變換方式是：改變能被p=4整除或被q=6整除的各位的奇偶性。問：作此改變后，未改變奇偶性的有多少位？離散數(shù)學(xué)第5章計數(shù)5.2.1排列的計數(shù)定義5.1

用或表示“從n個元素的集合中每次取出r個元素進行有序排列時可得到的排列的總數(shù)”。或簡稱為

r-排列數(shù)，簡稱為n-全排列數(shù)。定理5.5

對任意正整數(shù)n,r,r≤n,從n個元素的集合中每次取出r個元素進行有序排列時可得到的排列的總數(shù)是：（約定

）特別地，，5.2排列與組合離散數(shù)學(xué)第5章計數(shù)例5.5

問有多少個大于6400，又同時滿足各位數(shù)字都不相同，且數(shù)中不出現(xiàn)數(shù)字2與7。解滿足條件的數(shù)只能是四、五、六、七和八位數(shù)。五、六、七和八位數(shù)的數(shù)目可以如下分別計算：而五、六、七和八位數(shù)的數(shù)的總數(shù)應(yīng)當(dāng)是：滿足要求的四位數(shù)可如下計算：千位數(shù)大于6的有千位數(shù)是6，而百位數(shù)大于或等于4的有故滿足兩個性質(zhì)的整數(shù)共計有94080+420+120=94620(個)5.2.1排列的計數(shù)5.2排列與組合離散數(shù)學(xué)第5章計數(shù)5.2.1排列的計數(shù)5.2排列與組合定理5.6

對任意正整數(shù)n,r,r≤n,從n個元素的集合中每次取出r個元素，圍繞一個圓周進行有序排列時可得到的排列的總數(shù)是：特別地，全取n個元素的圓排列的數(shù)目是：證

一個r個元素的圓排列，設(shè)想在圓排列的r個間隔處將其切斷，每個不同的切斷均產(chǎn)生一個不同的線排列。故r個元素的圓排列的總數(shù)為r個元素的線排列的總數(shù)除以r，即12

53

4離散數(shù)學(xué)第5章計數(shù)例5.68位女士和8位先生圍著一張圓桌聚餐，要求安排女士和先生交替就座。問：有多少可能的安排方案。解

先安排女士坐下，兩位之間留一空位，然后安排先生就座。安排8位女士坐下（圓排列）的方案數(shù)是安排先生在8個空位上就座的方案數(shù)是滿足要求安排方案共計有5.2.1排列的計數(shù)5.2排列與組合離散數(shù)學(xué)第5章計數(shù)定理5.7

對任意正整數(shù)n,r,r≤n,從n個元素的集合中每次取出r個元素組成子集合的總數(shù)是：特別地，，，約定。定義5.2

用或表示“從n個元素的集合中每次取出r個元素（不進行有序排列）組成子集合的總數(shù)。或簡稱為r-組合數(shù)”。5.2.2組合的計數(shù)5.2排列與組合離散數(shù)學(xué)第5章計數(shù)解

S1能踢后場的5人，S2能踢前場的8人，S3能踢后場和前場的2人

(1)

不用S3人員：

(2)

用S3中一個人員：踢前鋒踢后衛(wèi)

(3)

用S3中兩個人員：踢前鋒踢后衛(wèi)一個踢后衛(wèi)、另一個踢前鋒

共計：40+280+160+280+80+560=1400(種)

5.2.2組合的計數(shù)例4.7

一個足球隊有15名隊員，其中5人能踢后場，8人能踢前場，2人既能踢后場又能踢前場。今需從中選取7名前鋒和4名后衛(wèi)參加比賽，問：有多少種不同的選法（只考慮隊員的前后場特長組合，不考慮同一位置上的左右區(qū)別）。5.2排列與組合離散數(shù)學(xué)第5章計數(shù)定理5.8

對任意正整數(shù)n,r,r≤n,5.2.2組合的計數(shù)5.2排列與組合離散數(shù)學(xué)第5章計數(shù)5.2.2組合的計數(shù)牛頓二項式定理：對任意正整數(shù)n5.2排列與組合定理5.9

對任意正整數(shù)n，證

根據(jù)牛頓二項式定理：(3)只是(2)的簡單變形。離散數(shù)學(xué)第5章計數(shù)證

等式的左邊表示從n個元素的集合中每次取出k個元素組成子集合的總數(shù)。取定元素a，這些子集合可以分為兩類：

(1)不含元素a的k個元素組成的子集合，個數(shù)是；

(2)必含元素a的k個元素組成的子集合，個數(shù)是因此定理5.10

對于滿足條件1≤k≤n–1的任意正整數(shù)k和n

，有5.2.2組合的計數(shù)5.2排列與組合（楊輝三角公式或帕斯卡公式）離散數(shù)學(xué)第5章計數(shù)5.3重集的排列與組合5.3重集的排列與組合重集：允許多個相同的對象同時出現(xiàn)的對象的總體。重集中的對象仍稱為重集的元素，重集中相同元素的個數(shù)稱為元素的重數(shù)。具有n1個a1，n2個a2，…，nm個am的重集，稱之為n(n=n1+n2+…nm)個元素的m元重集，可以表示為約定表示a在重集中可出現(xiàn)任意多次。重集中的所有元素均可以任意多次地出現(xiàn)，稱為無窮重數(shù)的m元重集。離散數(shù)學(xué)第5章計數(shù)5.3.1重集的排列定義5.3

重集的r-排列是指從重集（其中各ni

可以是∞）中每次取出r個元素進行有序的排列，此時可得到的排列的總數(shù)稱為r-排列數(shù)。當(dāng)時，稱此r-排列為全排列，此時可得到的排列的總數(shù)稱為全排列數(shù)。定理5.11

無窮重數(shù)的m元重集的r-排列數(shù)是mr。證

無窮重數(shù)的m元重集的r-排列的每一個位置上，均可選取m個不同元素中的每一個，因此每一個位置上元素的排放法有m種，故而r-排列數(shù)應(yīng)當(dāng)是mr。5.3重集的排列與組合離散數(shù)學(xué)第5章計數(shù)例5.8（1）用7顆六彩的珠子串成長鏈，可以串出多少種不同的長鏈？（2）用7顆六彩的珠子串成環(huán)鏈，至少用兩種顏色的珠子，可以串出多少種不同的環(huán)鏈？（假定六彩的珠子取之不盡，并且不考慮鏈子的反轉(zhuǎn)）解（1）

67=279936(種)

（2）

(67-6)÷7=39990（種）5.3.1重集的排列5.3重集的排列與組合離散數(shù)學(xué)第5章計數(shù)定理5.12

m元重集的全排列數(shù)是其中5.3.1重集的排列5.3重集的排列與組合

證

從n個排列的位置中選n1個放a1：C(n,n1)種從n-n1個排列的位置中選n2個放a2：C(n-n1,n2)種…從n-n1-n2…-nm-1個排列的位置中選nm個放am：C(n-n1-…-nm-1,nm)種因此，m元重集的全排列數(shù)是離散數(shù)學(xué)第5章計數(shù)例5.9

一位秘書在某大廈B工作，該大廈在她家（H）東邊9個街段，北邊7個街段。假定她每天從家里到大廈去上班都不走回頭路。問她可以有多少種不同的走法？又若圖中的AC段積水，使她無法通過，這時她又可以有多少種不同的走法？5.3.1重集的排列5.3重集的排列與組合BHAC(9,7)(0,0)(4,3)(5,3)解

一種走法對應(yīng)于重集{9·E，7·N}的一個全排列，故不同的走法是離散數(shù)學(xué)第5章計數(shù)從H到A的走法：5.3.1重集的排列例5.9（續(xù)）

AC段積水，她又可以有多少種不同的走法？5.3重集的排列與組合從C到B的走法：必經(jīng)AC街段時她的走法總數(shù)是不經(jīng)AC街段時她的走法總數(shù)是BHAC(9,7)(0,0)(4,3)(5,3)離散數(shù)學(xué)第5章計數(shù)例5.10（1）問方程x1+x2+…+xm=r

有多少組自然數(shù)解？（2）問方程x1+x2+…+xm=r有多少組正整數(shù)解？5.3.1重集的排列5.3重集的排列與組合解：（1）自然數(shù)解的數(shù)目等同于重集{(m-1).0,r.1}的全排列數(shù):（2）正整數(shù)解的數(shù)目等同于集合{p1,p2,…,pr-1}的(m–1)-組合數(shù)：離散數(shù)學(xué)第5章計數(shù)定義5.4

重集的r-組合是指從重集（其中各

ni可以是∞）中每次取出r個元素組成子重集，此時可得到的子重集的總數(shù)稱為重集的r-組合數(shù)。定理4.13

無窮重數(shù)的m元重集的r-組合數(shù)是。因此，r-組合數(shù)與方程x1+x2+…+xm=r的自然數(shù)解的數(shù)目相等，故m元重集的r-組合數(shù)是證

m元重集的r-組合是r個元素組成子重集5.3.2重集的組合5.3重集的排列與組合。離散數(shù)學(xué)第5章計數(shù)證

無窮重數(shù)的m元重集{∞·a1,∞·a2,…,∞·am}的r-組合是r個元素組成子重集其中x1+x2+…xm=r且x1,x2,…,xm

均為整數(shù)因此，r-組合數(shù)與方程x1+x2+…+xm=r的正整數(shù)解的數(shù)目相等根據(jù)例5.10（2），結(jié)論成立。定理5.14

要求無窮重數(shù)的m元重集{∞·a1,∞·a2,…,∞·am}的r-組合中a1,a2,…，am

均至少選入一次的r-組合數(shù)是C(r-1,m-1)。5.3.2重集的組合5.3重集的排列與組合離散數(shù)學(xué)第5章計數(shù)5.3.2重集的組合5.3重集的排列與組合例5.11

一家面包店賣6種面包，假如你要買11個面包，可以有多少種選擇方案(假定各種面包的數(shù)量都大大超過11只)？假如你要買11個面包，且每種面包至少一只，可以有多少種選擇方案？解

第一問：求重集{∞·a1,∞·a2,…,∞·a6}的11-組合數(shù)，解為

第二問：求重集{∞·a1,∞·a2,…,∞·a6}的、每個元素至少取一個的11-組合數(shù)，解為離散數(shù)學(xué)第5章計數(shù)例5.12

設(shè)求S的r-組合數(shù)。5.3.2重集的組合5.3重集的排列與組合S的r-組合的構(gòu)成：先從S1中選出i個元素(i=0,1,2,…，t),再從S2中選出r–i個元素。S的r-組合數(shù)：（將原式中的K改成了m）解

將S分為兩個子集離散數(shù)學(xué)第5章計數(shù)5.3.2重集的組合5.3重集的排列與組合例5.13

試計算重集S={3.a,4.b,5.c}的10-組合數(shù)解

重集T={∞·a,∞·b,∞·c}，令P1：T的10-組合中多于3個a

P2：T的10-組合中多于4個b

P3：T的10-組合中多于5個c

則S的10-組合數(shù)等于不具有性質(zhì)P1,P2,P3的T的10-組合數(shù)離散數(shù)學(xué)第5章計數(shù)定義5.5

集合{1，2，3，…，n}的全排列，使得每個數(shù)i都不在第

i位上，稱這樣的排列為{1，2，3，…，n}的一個錯置。定理5.15

集合{1，2，3，…，n}的錯置的總數(shù)（記為Dn）是（約定D0=1）5.3.3錯置的計數(shù)5.3重集的排列與組合定理5.16（1）Dn=(n-1)(Dn-2+Dn-1)

（2）Dn=nDn-1+(-1)n離散數(shù)學(xué)第5章計數(shù)5.3.3錯置的計數(shù)5.3重集的排列與組合定義5.6

集合{1，2，3，…，n}的每個數(shù)i都不緊鄰在數(shù)i-1后面的全排列，稱為{1，2，3，…，n}的Qn－禁位全排列，其排列總數(shù)記為Qn。定理5.17

集合{1，2，3，…，n}的Qn－禁位全排列總數(shù)離散數(shù)學(xué)第5章計數(shù)5.4遞歸式及其應(yīng)用5.4遞歸式及其應(yīng)用遞歸關(guān)系式或遞歸式：運用函數(shù)的前驅(qū)值來計算函數(shù)當(dāng)前值的關(guān)系式。例如（定理5.16）（1）Dn=(n-1)(Dn-2+Dn-1)

（2）Dn=nDn-1+(-1)n離散數(shù)學(xué)第5章計數(shù)5.4遞歸式及其應(yīng)用5.4遞歸式及其應(yīng)用例5.14

確定an=3n（n是非負(fù)整數(shù)）是否為遞歸關(guān)系an=2an-1–an-2

(n=2,3,4,…)的解。若an=2n或an=5呢？解：(1)

設(shè)對每一非負(fù)整數(shù)n，an=3n對n≥2，可看出2an-1–an-2=2·3(n–1)–3(n–2)=3n=an故an=3n是該遞歸關(guān)系的解。

(2)

設(shè)對每一非負(fù)整數(shù)n，an=2n那么，a0=1，a1=2，a2=4，2a1–a0=2·2–1=3≠a2。故an=2n不是該遞歸關(guān)系的解

(3)

設(shè)對每一非負(fù)整數(shù)n，an=5那么，對n≥2，有2an-1–an-2=2·5-5=5=an因此an=5是該遞歸關(guān)系的解。離散數(shù)學(xué)第5章計數(shù)5.4遞歸式及其應(yīng)用5.4遞歸式及其應(yīng)用研究遞歸關(guān)系式的主要目的：針對要求解的問題建立遞歸關(guān)系式。由遞歸關(guān)系式解出數(shù)列（自然數(shù)函數(shù)）的解析式。利用遞歸關(guān)系式解決一些重要的計數(shù)問題。離散數(shù)學(xué)第5章計數(shù)5.4.1遞歸式建模5.4遞歸式及其應(yīng)用例5.15

兔子繁殖問題：在一年的年初把一對剛出生的小兔子放進養(yǎng)殖場。小兔子兩個月長成，長成后即可生育，每月可生產(chǎn)雌雄一對。出生的小兔子均在一月后長成，并在日后不斷生產(chǎn)。問一年后養(yǎng)殖場有多少對兔子？n個月后養(yǎng)殖場有多少對兔子？解：用F(n)表示在第n個月養(yǎng)殖場里兔子的對數(shù)，是正整數(shù)。那么，費波那契數(shù)列費波那契數(shù)費波那契遞歸關(guān)系。F(1)=1F(2)=1

F(3)=1+1=2F(4)=2+1=3……離散數(shù)學(xué)第5章計數(shù)5.4.1遞歸式建模5.4遞歸式及其應(yīng)用例5.16

集合{1,2,3,…,n}的子集稱為是交替的，如果它的元素在按照上升次序排列時，是奇、偶交替地出現(xiàn)的，且第一個數(shù)是奇數(shù)。規(guī)定空集和奇數(shù)單元素子集是交替的。令f(n)表示{1,2,3,…,n}的交替子集的數(shù)目。求解f(n)。解:f(1)=2交替子集：{1}、

f(2)=3交替子集：{1,2}、{1}、

{1,2,3,…,n}的所有子集分兩部分：{1,2,3,…,n-1}，交替子集：f(n-1){1,2,3,…,n-1}的每個子集加進元素n以后所得到的子集（包含n）交替子集：{1,2,3,…,n-2}的交替子集并入{n-1,n}或{n}，為f(n-2)。故f(n)=f(n-1)+f(n-2)

再由f(1)=2=F(3)，f(2)=3=F(4)可得：f(n)=F(n+2)離散數(shù)學(xué)第5章計數(shù)5.4.1遞歸式建模5.4遞歸式及其應(yīng)用

例5.17

有三個木樁，在其中一個木樁上有n個大小不等的圓盤，按照由小到大的次序迭放著，最大的圓盤放在最底下。需將這些圓盤從個木樁轉(zhuǎn)移到另一個空木樁上，并依然按原來的次序迭放，轉(zhuǎn)移中可以利用第三個空木樁，但要求在轉(zhuǎn)移過程中的任何時候都保持讓較大的圓盤在較小的圓盤之下。問：完成這樣的轉(zhuǎn)移，必須移動圓盤多少次。離散數(shù)學(xué)第5章計數(shù)5.4.1遞歸式建模解:

令h(n)為完成這樣的一次轉(zhuǎn)移必須移動圓盤的次數(shù)。顯然，h(0)=0，h(1)=1，h(2)=3把n個圓盤從一個移到另一個木樁，可遞歸地將轉(zhuǎn)移分三個過程：1.

將n-1個圓盤從所在木樁轉(zhuǎn)移到第三個木樁，留下最大的圓盤。必須移動的次數(shù)是h(n-1)。2.

將最大的圓盤移至目標(biāo)木樁。必須移動的次數(shù)是1.

3.

將n-1個圓盤從第三個木樁轉(zhuǎn)移到目標(biāo)木樁。必須移動的次數(shù)是h(n-1)。因而得遞歸式h(n)=2h(n-1)+1（求解見后）

離散數(shù)學(xué)第5章計數(shù)5.4.2遞歸式求解5.4遞歸式及其應(yīng)用遞歸式的迭代求解方法由兩個步驟組成：（1）利用遞歸式對其右邊的表達式進行迭代，并推測解的公式。（2）用數(shù)學(xué)歸納法證明得到的公式。（一）遞歸式的迭代求解離散數(shù)學(xué)第5章計數(shù)5.4.2遞歸式求解

5.4遞歸式及其應(yīng)用例5.18

平面上有n條兩兩相交的直線，又沒有任何三條直線交于一點。問共有多少不同交點。（要求用遞歸關(guān)系式求解）解：設(shè)已知的n(n≥2)條直線的交點數(shù)為h(n)，顯然，h(2)=1。增添第n+1條，它與前n條相交產(chǎn)生新的n個交點，故有

h(n+1)=h(n)+n

或h(n)=h(n-1)+1迭代：離散數(shù)學(xué)第5章計數(shù)5.4遞歸式及其應(yīng)用用數(shù)學(xué)歸納法證明歸納基礎(chǔ)：

n=2時，已知h(2)=1，而歸納推理：設(shè)那么歸納完成，證畢。5.4.2遞歸式求解

離散數(shù)學(xué)第5章計數(shù)5.4.2遞歸式求解5.4遞歸式及其應(yīng)用遞歸式的迭代求解方法由兩個步驟組成：（1）利用遞歸式對其右邊的表達式進行迭代，并推測解的公式。（2）用數(shù)學(xué)歸納法證明得到的公式。（一）遞歸式的迭代求解離散數(shù)學(xué)第5章計數(shù)5.4.2遞歸式求解5.4遞歸式及其應(yīng)用例5.17的求解：

……離散數(shù)學(xué)第5章計數(shù)5.4.2遞歸式求解5.4遞歸式及其應(yīng)用歸納法證明歸納基礎(chǔ)：n=0時，已知h(0)=0，而歸納推理：設(shè)，那么n=k+1時歸納完成，證畢。離散數(shù)學(xué)第5章計數(shù)5.4.2遞歸式求解5.4遞歸式及其應(yīng)用（二）常系數(shù)線性齊次遞歸式的求解定義5.7

下列方程組定義稱為數(shù)列H(n)的常系數(shù)線性齊次遞歸式若方程組的最后一式為則方程組稱為定義數(shù)列H(n)的常系數(shù)線性非齊次遞歸式。離散數(shù)學(xué)第5章計數(shù)5.4.2遞歸式求解5.4遞歸式及其應(yīng)用定理5.18

設(shè)q是一個非零的實數(shù)或復(fù)數(shù)，那么，H(n)=qn是遞歸式

的解當(dāng)且僅當(dāng)p是它的一個特征根。離散數(shù)學(xué)第5章計數(shù)定理5.19

設(shè)是非零實數(shù)或復(fù)數(shù)，那么，的解當(dāng)且僅當(dāng)是它的k個不同的特征根。5.4.2遞歸式求解5.4遞歸式及其應(yīng)用是遞歸式離散數(shù)學(xué)第5章計數(shù)5.4.2遞歸式求解5.4遞歸式及其應(yīng)用例5.19

解下列遞歸式：離散數(shù)學(xué)第5章計數(shù)5.4.2遞歸式求解5.4遞歸式及其應(yīng)用例5.20

某人有n(n≥1)元錢，他每一天購買一次物品，或者買一元錢的甲物品，或者買二元錢的乙物品，或者買二元錢的丙物品。問：此人有多少種方式化完這n元錢。離散數(shù)學(xué)第5章計數(shù)5.4.2遞歸式求解5.4遞歸式及其應(yīng)用例5.21

解下列遞歸式：離散數(shù)學(xué)第5章計數(shù)那么該遞歸式的一般解是的特征方程的個不同的特征根，各有重。定理5.20

設(shè)是非零實數(shù)或復(fù)數(shù)，它們是遞歸關(guān)系式5.4.2遞歸式求解5.4遞歸式及其應(yīng)用其中離散數(shù)學(xué)第5章計數(shù)5.4.2遞歸式求解5.4遞歸式及其