離散數(shù)學(xué)及應(yīng)用（第3版）課件第一章 基礎(chǔ)知識(shí) （下）

第一章基礎(chǔ)知識(shí)《離散數(shù)學(xué)及應(yīng)用》第一章基礎(chǔ)知識(shí)§1.1集合與序列§1.1.1集合的基本概念§1.1.2集合的運(yùn)算及性質(zhì)§1.1.3序列§1.2數(shù)論基礎(chǔ)§1.3計(jì)數(shù)基礎(chǔ)§1.3.1加法法則與乘法法則§1.3.2排列與組合§1.3.3鴿巢原理§1.3.4有限集合的計(jì)數(shù)——容斥原理§1.3.5遞推關(guān)系§1.4布爾矩陣及其運(yùn)算2加法法則與乘法法則加法法則：設(shè)事件

A

有

m

種產(chǎn)生方式，事件

B

有

n種產(chǎn)生方式，則當(dāng)

A

與

B產(chǎn)生的方式不重疊時(shí)，“事件

A

或

B

之一”有

m+n

種產(chǎn)生方式。加法法則又稱作加法原理（additionprinciple）適用于分類選取問(wèn)題3加法法則與乘法法則例某班選修《古代詩(shī)歌鑒賞》的有8人，不選的有15人，則該班共有8+15=23人。4加法法則與乘法法則加法法則的推廣：事件

A1

有

p1

種產(chǎn)生方式，事件

A2有

p2種產(chǎn)生方式……事件

Ak有

pk

種產(chǎn)生的方式，則當(dāng)其中任何兩個(gè)事件產(chǎn)生的方式都不重疊時(shí)，“事件

A1

或

A2

或…Ak”有

p1+p2+…+pk種產(chǎn)生的方式。5加法法則與乘法法則乘法法則：設(shè)事件

A

有

m

種產(chǎn)生方式，事件

B

有

n

種產(chǎn)生方式，則當(dāng)

A

與

B

產(chǎn)生的方式彼此獨(dú)立時(shí)，“事件

A

與

B

”有

m

n

種產(chǎn)生方式。乘法法則又稱乘法原理（multiplicationprinciple）適用于分步選取問(wèn)題適用條件：無(wú)論事件

A

采用何種方式產(chǎn)生，都不影響事件

B

。6加法法則與乘法法則假如一個(gè)實(shí)驗(yàn)分兩步驟進(jìn)行：步驟一有m

種可能結(jié)果無(wú)論步驟一的結(jié)果是什么，步驟二都有n

種可能結(jié)果那么這個(gè)實(shí)驗(yàn)就共有m

n

種可能的結(jié)果7加法法則與乘法法則例某種字符串由兩個(gè)字符組成，第一個(gè)字符可選自{a,b,c,d,e}，第二個(gè)字符可選自{1,2,3,4}，則這種字符串共有5×4=20個(gè)。8加法法則與乘法法則乘法法則的推廣：事件

A1

有

p1種產(chǎn)生方式，事件

A2有

p2種產(chǎn)生方式……事件

Ak有

pk種產(chǎn)生的方式，則當(dāng)其中任何兩個(gè)事件產(chǎn)生的方式都彼此獨(dú)立時(shí)，“事件

A1

與

A2

與…Ak”有

p1

p2

…

pk種產(chǎn)生的方式。9加法法則與乘法法則例求1400的不同的正因子個(gè)數(shù)。解.1400=235271的正因子為：2i5j7k其中

0

i

3,0

j

2,0

k

1于是，1400的不同的因子數(shù)是N=(3+1)(2+1)(1+1)=2410加法法則與乘法法則例設(shè)

A是集合，如果|A|=n，則|P

(A)|=2n。證明.假設(shè)

A={a1,a2,…,an}考慮

A

的任一個(gè)子集

B則對(duì)于每一個(gè)元素

ai

都有

ai

B

和

ai

B

兩種可能由乘法原理，B

的可能數(shù)目一共為

2n11加法法則與乘法法則例苗苗有

n

塊大白兔奶糖，從生日那天開(kāi)始，她每天至少吃一塊，吃完為止。一共有多少種安排方案？解.方案數(shù)目為

2n

1以

n=5

的情況來(lái)說(shuō)明計(jì)算方法：將5塊糖按下圖所示方式放入9個(gè)格子內(nèi)空白的4個(gè)格子可以填入“|”或保留空白

（共兩種可能）。12加法法則與乘法法則解.方案數(shù)目為

2n

1則每種填法都對(duì)應(yīng)一種吃糖的安排方案例如下圖表示第一天吃2塊、第二天吃1塊、第三天吃2塊而下圖表示第一天吃1塊、第二天吃4塊13加法法則與乘法法則在實(shí)際問(wèn)題中，分類（加法原則）與分步（乘法原則）通常都結(jié)合使用例A,B,C是3個(gè)城市，從A到B有4條道路，從B到C有2條道路，從A直接到C有3條道路，則從A到C共有4

2+3=11種不同的方式。（先分類，類內(nèi)再分步）某種樣式的套裝上裝有T恤和襯衫兩種，下裝為長(zhǎng)褲。T恤可選紅色、藍(lán)色和橙色，襯衫可選白色、黃色和粉色，長(zhǎng)褲可選黑色、棕色，則共有(3+3)×2=12種著色方案。（先分步，每步再分類）14第一章基礎(chǔ)知識(shí)§1.1集合與序列§1.1.1集合的基本概念§1.1.2集合的運(yùn)算及性質(zhì)§1.1.3序列§1.2數(shù)論基礎(chǔ)§1.3計(jì)數(shù)基礎(chǔ)§1.3.1加法法則與乘法法則§1.3.2排列與組合§1.3.3鴿巢原理§1.3.4有限集合的計(jì)數(shù)——容斥原理§1.3.5遞推關(guān)系§1.4布爾矩陣及其運(yùn)算15排列問(wèn)題：設(shè)集合

S

包含

n

個(gè)元素，從

S中選取

r

個(gè)元素有多少種取法？根據(jù)取出的元素是否允許重復(fù)、取出的過(guò)程是否有序可以將該問(wèn)題分為四個(gè)子類型：16

不重復(fù)選取重復(fù)選取有序選取排列可重排列無(wú)序選取組合可重組合排列從

n

個(gè)不同的對(duì)象中，取

r個(gè)可重復(fù)的對(duì)象，按次序排列，稱為n取r的可重排列。此也即當(dāng)

|A|=n時(shí)，A

中長(zhǎng)為

r

的串的個(gè)數(shù)。17排列定理1

n

取

r

的可重排列數(shù)目為

nr

。18…n

種選擇n

種選擇n

種選擇排列從

n個(gè)不同的對(duì)象中，取

r

個(gè)不重復(fù)的對(duì)象，按次序排列，稱為

n取

r的排列

（permutationofnobjectstakenratatime）。n

取

r

排列的全體構(gòu)成的集合用P(n,r)表示，排列的個(gè)數(shù)用

P(n,r)表示；當(dāng)

r=n時(shí)稱為全排列或置換（permutation）。此也即當(dāng)

|A|=n時(shí)，

A

中長(zhǎng)為

r且各項(xiàng)彼此不同的串的個(gè)數(shù)。19排列20A={a,b,c,d}A

上的所有4取3的排列是：abc,bac,acb,bca,cab,cba,abd,bad,adb,bda,dab,dba,bcd,bdc,cbd,cdb,dbc,dcb,acd,adc,cad,cda,dac,dca排列21abcd,abdc,acbd,acdb,adbc,adcb,bacd,badc,bcad,bcda,bdac,bdca,cabd,cadb,cbad,cbda,cdab,cdba,dabc,dacb,dbac,dbca,dcab,dcbaA={a,b,c,d}A

上的所有全排列是：排列定理2

n

<

r

時(shí)，P(n,r)=0；n

r

時(shí)，P(n,r)=n

(n

1)

…

(n

r+1)。22…n

r+1種選擇n

種選擇n1

種選擇排列全排列經(jīng)常被理解為是包含某個(gè)有限集合中的所有元素一次且僅一次的序列。設(shè)

A是集合，如果|A|=n，則

A的全排列的個(gè)數(shù)為n

(n

1)

…

1這個(gè)值也經(jīng)常被寫作

n!

，稱作n的階乘（factorial）。

23排列24可以給出P(n,r)的一個(gè)更緊湊的表達(dá)式：排列例一個(gè)社團(tuán)共有

10

名成員，從中選出一名主席、一名副主席、一名書記，則共有

P(10,3)=720種方法25排列例如果有4個(gè)男孩和4個(gè)女孩坐成一排，每個(gè)人的旁邊都可以隨便坐，那么共有多少種坐的方式？268!排列例如果有4個(gè)男孩和4個(gè)女孩坐成一排，每個(gè)人旁邊都只能坐著異性，那么共有多少種坐的方式？27BGBGBGBGGBGBGBGB2

4!

4!排列問(wèn)題：設(shè)集合

S

包含

n

個(gè)元素，從

S中選取

r

個(gè)元素有多少種取法？根據(jù)取出的元素是否允許重復(fù)、取出的過(guò)程是否有序可以將該問(wèn)題分為四個(gè)子類型：28

不重復(fù)選取重復(fù)選取有序選取排列限制次數(shù)的可重排列無(wú)序選取組合可重組合排列由a,b,b,e,e,h,i,s,s,t,t,t可以組成多少個(gè)長(zhǎng)度為12的字符串？例如：

tseabibttseh29排列先考慮一個(gè)同類型的簡(jiǎn)單問(wèn)題——由a,a,b,c可以組成多少個(gè)長(zhǎng)度為4的字符串？對(duì)a加下標(biāo)得到

a1,a2于是一共可以得到4!=24個(gè)長(zhǎng)度為4的字符串30排列31a1a2bc,a1ba2c,a1bca2,ba1a2c,ba1ca2,bca1a2,a2a1bc,a2ba1c,a2bca1,ba2a1c,ba2ca1,bca2a1,a1a2cb,a1ca2b,a1cba2,ca1a2b,ca1ba2,cba1a2,a2a1cb,a2ca1b,a2cba1,ca2a1b,ca2ba1,cba2a1aabc,abac,abca,baac,baca,bcaa,aabc,abac,abca,baac,baca,bcaa,aacb,acab,acba,caab,caba,cbaa,aacb,acab,acba,caab,caba,cbaa排列先考慮一個(gè)同類型的簡(jiǎn)單問(wèn)題——由a,a,b,c可以組成多少個(gè)長(zhǎng)度為4的字符串？4!/2=1232排列由a,a,a,b可以組成多少個(gè)長(zhǎng)度為4的字符串？對(duì)a加下標(biāo)得到

a1,a2,a3于是一共可以得到4!=24個(gè)長(zhǎng)度為4的字符串33排列34a1a2a3b,a1a3a2b,a2a1a3b,a2a3a1b,a3a1a2b,a3a2a1b,a1a2ba3,a1a3ba2,a2a1ba3,a2a3ba1,a3a1ba2,a3a2ba1,a1ba2a3,a1ba3a2,a2ba1a3,a2ba3a1,a3ba1a2,a3ba2a1,ba1a2a3,ba1a3a2,ba2a1a3,ba2a3a1,ba3a1a2,ba3a2a1aaab,aaab,aaab,aaab,aaab,aaab,aaba,aaba,aaba,aaba,aaba,aaba,abaa,abaa,abaa,abaa,abaa,abaa,baaa,baaa,baaa,baaa,baaa,baaa排列由a,a,a,b可以組成多少個(gè)長(zhǎng)度為4的字符串？4!/3!=435排列由a,a,b,b可以組成多少個(gè)長(zhǎng)度為12的字符串？對(duì)a，b加下標(biāo)得到

a1,a2,b1

,b2于是一共可以得到4!=24個(gè)長(zhǎng)度為4的字符串36排列37a1a2b1b2,a1b1a2b2,a1b1b2a2,b1a1a2b2,b1a1b2a2,b1b2a1a2,a1a2b2b1,a1b2a2b1,a1b2b1a2,b2a1a2b1,b2a1b1a2,b2b1a1a2,a2a1b1b2,a2b1a1b2,a2b1b2a1,b1a2a1b2,b1a2b2a1,b1b2a2a1,a2a1b2b1,a2b2a1b1,a2b2b1a1,b2a2a1b1,b2a2b1a1,b2b1a2a1aabb,abab,abba,baab,baba,bbaa,aabb,abab,abba,baab,baba,bbaa,aabb,abab,abba,baab,baba,bbaa,aabb,abab,abba,baab,baba,bbaa排列由a,a,b,b可以組成多少個(gè)長(zhǎng)度為4的字符串？4!/(2!2!)=638排列定理

由

k1

個(gè)1，k2

個(gè)2，…，kt

個(gè)t組成的長(zhǎng)度為

n

的排列總數(shù)為其中

n=k1+k2+…+kt

。39排列回到問(wèn)題——由a,b,b,e,e,h,i,s,s,t,t,t可以組成多少個(gè)長(zhǎng)度為12的字符串？12!/(2!2!2!3!)=9979200例如：batisthebest40組合問(wèn)題：設(shè)集合

S

包含

n

個(gè)元素，從

S中選取

r

個(gè)元素有多少種取法？根據(jù)取出的元素是否允許重復(fù)、取出的過(guò)程是否有序可以將該問(wèn)題分為四個(gè)子類型：41

不重復(fù)選取重復(fù)選取有序選取排列可重排列無(wú)序選取組合可重組合組合從

n個(gè)不同元素中取

r

個(gè)不重復(fù)的元素組成一個(gè)子集，而不考慮其元素的順序，稱為

n取

r的組合（r-combination），該子集稱作

r

-子集（r-subset）。n

取

r

組合的全體構(gòu)成的集合用

C(n,r)表示，其元素個(gè)數(shù)用C(n,r)表示，有時(shí)也記作

。42(n)r組合例1設(shè)集合

A={a,b,c,d}，則

A上的所有4取3的組合是：43abc,bac,acb,bca,cab,cba,{a,b,c},{a,b,d},{a,c,d},{b,c,d}.abd,bad,adb,bda,dab,dba,bcd,bdc,cbd,cdb,dbc,dcb,acd,adc,cad,cda,dac,dca組合例1C(4,3)

3!=P(4,3)一般地講，有C(n,r)

r!=P(n,r)因此當(dāng)n

r時(shí)，C(n,r)=C(n,n

r)

44組合例2一個(gè)社團(tuán)共有10名成員，從中選出3人組成指導(dǎo)委員會(huì)，則共有C(10,3)=120種方法。（注意和“排列”進(jìn)行比較）45組合例3（簡(jiǎn)單格路問(wèn)題）從(0,0)點(diǎn)出發(fā)沿

x軸或

y

軸的正方向每步走一個(gè)單位，最終走到

(m,n)

點(diǎn)，有多少條路徑？46組合例3（簡(jiǎn)單格路問(wèn)題）從(0,0)點(diǎn)出發(fā)沿

x軸或

y

軸的正方向每步走一個(gè)單位，最終走到

(m,n)

點(diǎn)，有多少條路徑？478次10次C(10+8,8)組合回到曾經(jīng)遇見(jiàn)過(guò)的問(wèn)題由a,b,b,e,e,h,i,s,s,t,t,t可以組成多少個(gè)長(zhǎng)度為12的字符串？48組合4912個(gè)字符：

a,b,b,e,e,h,i,s,s,t,t,t12個(gè)空白位置：選擇3個(gè)放置“t”C(12,3)種可能ttt組合50剩余的字符：

a,b,b,e,e,h,i,s,s剩余9個(gè)空白位置：選擇2個(gè)放置“s”C(9,2)種可能tttss組合51剩余的字符：

a,b,b,e,e,h,i剩余7個(gè)空白位置：選擇2個(gè)放置“e”C(7,2)種可能tttssee組合52剩余的字符：

a,b,b,h,i剩余5個(gè)空白位置：選擇2個(gè)放置“b”C(5,2)種可能tttsseebb組合53剩余的字符：

a,h,i剩余3個(gè)空白位置：對(duì)剩余的3個(gè)字符進(jìn)行全排列3!種可能tttsseebbaih組合共有C(12,3)

C(9,2)

C(7,2)

C(5,2)

3!

=9979200

種可能可以得到相同結(jié)果54組合問(wèn)題：設(shè)集合

S

包含

n

個(gè)元素，從

S中選取

r

個(gè)元素有多少種取法？根據(jù)取出的元素是否允許重復(fù)、取出的過(guò)程是否有序可以將該問(wèn)題分為四個(gè)子類型：55

不重復(fù)選取重復(fù)選取有序選取排列可重排列無(wú)序選取組合可重組合組合例：現(xiàn)在有4種口味的棒棒糖，你要從中選3個(gè)(允許你選同種口味)總共有多少種不同的選法？56組合假設(shè)選定：口味1的棒棒糖x1個(gè)口味2的棒棒糖x2個(gè)，口味3的棒棒糖x3個(gè)，口味4的棒棒糖x4個(gè)，x1,

x2,x3,x4的值都是非負(fù)整數(shù)，而且滿足等式x1+x2+x3+x4=3

。57組合例如：

x1=2,x2=0,x3=1,x4=058x1x2x3x4組合59001101組合60001101C(6,3)#棒棒糖#棒棒糖+#口味數(shù)

1組合n取k的可重組合定理

假設(shè)從

n

個(gè)相異對(duì)象中選取

k

個(gè)對(duì)象，且允許重復(fù)選取，則不同的選取方法數(shù)目為

C(n+k

1,k)

。61組合例：如果從{A,B,C}中選擇4個(gè)字母并且允許重復(fù)，則共有多少種選擇方法？62A,A,A,A;A,A,A,B;A,A,A,C;A,A,B,B;A,A,B,C;A,A,C,C;A,B,B,B;A,B,B,C;A,B,C,C;A,C,C,C;B,B,B,B;B,B,B,C;B,B,C,C;B,C,C,C;C,C,C,C第一章基礎(chǔ)知識(shí)§1.1集合與序列§1.1.1集合的基本概念§1.1.2集合的運(yùn)算及性質(zhì)§1.1.3序列§1.2數(shù)論基礎(chǔ)§1.3計(jì)數(shù)基礎(chǔ)§1.3.1加法法則與乘法法則§1.3.2排列與組合§1.3.3鴿巢原理§1.3.4有限集合的計(jì)數(shù)——容斥原理§1.3.5遞推關(guān)系§1.4布爾矩陣及其運(yùn)算63鴿巢原理鴿巢原理（pigeonholeprinciple）是組合數(shù)學(xué)中最簡(jiǎn)單也是最基本的原理，也稱作狄利克雷抽屜原則（Dirichlet'sdrawerprinciple）。因?yàn)榈依死祝―irichlet，1805－1859）首先明確提出抽屜原則并用以證明一些數(shù)論中的問(wèn)題。6465鴿巢原理定理（鴿巢原理）

若有

n

個(gè)鴿巢，n+1

個(gè)鴿子，則至少有一個(gè)巢內(nèi)有至少兩個(gè)鴿子。66鴿巢原理例1假設(shè)在一個(gè)盒子里面有10雙黑色襪子、12雙藍(lán)色襪子和8雙紅色襪子。那么拿出4只襪子一定可以保證有同色的兩只。每種顏色作為抽屜拿出的襪子數(shù)目作為蘋果67鴿巢原理例2在1到10中選取6個(gè)數(shù)，則其中必定有兩個(gè)數(shù)的和是11。證明.68{1,10},{2,9},{3,8},{4,7},{5,6},鴿巢原理例3一次酒會(huì)上有

n

名來(lái)賓，其中一些來(lái)賓相互握手致意，已知沒(méi)有人和自己握手、兩人之間至多只握一次手。證明：一定有兩名來(lái)賓的握手次數(shù)相同。69鴿巢原理將來(lái)賓作為“蘋果”，握手的次數(shù)作為“抽屜”。每名來(lái)賓的握手次數(shù)最多為

n?1，最少為

0

。但是不可能既有來(lái)賓握手次數(shù)為

n?1

又有來(lái)賓握手次數(shù)為

0

：假如有來(lái)賓握手次數(shù)為

n?1

，則說(shuō)明他與其他任何一名來(lái)賓都握過(guò)手，那么不可能有來(lái)賓沒(méi)有與其它人握過(guò)手；反過(guò)來(lái)，假如有來(lái)賓握手次數(shù)為

0

，則說(shuō)明他與其他任何一名來(lái)賓都沒(méi)有握過(guò)手，那么不可能有來(lái)賓與其它人都握過(guò)手。因此抽屜的個(gè)數(shù)最多為

n?1，蘋果的個(gè)數(shù)為

n，必定有兩個(gè)蘋果在同一個(gè)抽屜中，也即必定有兩名來(lái)賓的握手次數(shù)相同。70鴿巢原理例4任意12個(gè)整數(shù)中一定存在兩個(gè)整數(shù)，其差是11的倍數(shù)。證明.任何一個(gè)整數(shù)模11的余數(shù)都只有11種：0,1,2,…,10；于是任意的12個(gè)整數(shù)中必定存在兩個(gè)整數(shù)模11的余數(shù)相同，它們的差就是11的倍數(shù)。

71鴿巢原理定理（一般性鴿巢原理）

設(shè)

m1,m2,…,

mn都是正整數(shù)，并有

m1+m2+…+mn

n+1只鴿子住進(jìn)

n

個(gè)鴿巢，則至少對(duì)某個(gè)

i有：第

i

個(gè)巢中至少有

mi個(gè)鴿子，i=1,2,…,n。推論

m

只鴿子住進(jìn)

n

個(gè)巢，且

m

1=q

n+r，其中

q

和

r

是整數(shù)，且

0≤r<n。則至少有一個(gè)巢里有

q+1

只鴿子。72鴿巢原理例5如果小張?jiān)?5天內(nèi)作了170道習(xí)題，那么他一定有某一天做了至少12道習(xí)題。證明

170

1=169=11

15+473鴿巢原理例6在如圖所示的邊長(zhǎng)為1的正六邊形中任意放置19個(gè)點(diǎn)，則其中必有兩點(diǎn)之間的距離不超過(guò)

。74SchoolofSoftwareEngineer1鴿巢原理75則19個(gè)點(diǎn)中必定有4個(gè)點(diǎn)在同一個(gè)正三角形中（包括邊界）。鴿巢原理再將該三角形按圖所示方法分為三個(gè)圓心角為60

的扇形（不必互不相交），則這4個(gè)點(diǎn)中至少存在兩點(diǎn)在同一個(gè)扇形中（包括邊界）。76鴿巢原理這兩個(gè)點(diǎn)之間的距離必然不超過(guò)

。7777第一章基礎(chǔ)知識(shí)§1.1集合與序列§1.1.1集合的基本概念§1.1.2集合的運(yùn)算及性質(zhì)§1.1.3序列§1.2數(shù)論基礎(chǔ)§1.3計(jì)數(shù)基礎(chǔ)§1.3.1加法法則與乘法法則§1.3.2排列與組合§1.3.3鴿巢原理§1.3.4有限集合的計(jì)數(shù)——容斥原理§1.3.5遞推關(guān)系§1.4布爾矩陣及其運(yùn)算7879A={0,1,2,3},B={1,3,5,7,9}A∪B={0,1,2,3,5,7,9}A∩B={1,3}|A∪B|=7,|A∩B|=2|A|=4,|B|=5|A|+|B

|

|A∩B| =4+5-2=7=|A∪B|容斥原理79容斥原理定理

設(shè)

A、B為兩個(gè)有限集，則|A∪B|=|A|+|B|

|A∩B|。證明顯然，若

A和

B沒(méi)有共同的元素，即A∩B=

，則

|A1∪A2|=|A1|+|A2|。若

A∩B≠

，由

A∪B=(A

B)∪B

且

(A

B)∩B=

，及

A=(A

B)∪(A∩B)且

(A

B)∩(A∩B)=

，有

|A∪B|=|A

B|+|B|

及

|A|=|A

B|+|A∩B|，即|A∪B|=|A|+|B|

|A∩B|8081上述定理稱作容斥原理（inclusion-exclusionprinciple）容斥原理81容斥原理例有多少個(gè)以“1”開(kāi)始或者以“00”結(jié)尾的長(zhǎng)度為8的0-1序列？解.以“1”開(kāi)始的長(zhǎng)度為8的0-1序列有27=128個(gè)；以“00”結(jié)尾的長(zhǎng)度為8的0-1序列有26=64個(gè)；以“1”開(kāi)始且以“00”結(jié)尾的長(zhǎng)度為8的0-1序列有25=32個(gè)；由容斥原理，滿足題意的序列有128+64

32=160個(gè)82容斥原理容斥原理可以推廣到三個(gè)有限集元素的計(jì)數(shù)問(wèn)題：定理

設(shè)

A,B,C

是有限集合，則

|A∪B∪C|=|A|+|B|+|C|

|A∩B|

|B∩C|

|A∩C|

+|A∩B∩C|。

83容斥原理證明|A∪B∪C|=|A|+|B∪C|

|A∩(B∪C)|=|A|+|B∪C|

|(A∩B)∪(A∩C)|=|A|+|B|+|C|

|B∩C|

(|A∩B|+|A∩C

|

|(A∩B)∩(A∩C)|)

=|A|+|B|+|C|

|B∩C|

(|A∩B|+|A∩C

|

|(A∩A)∩(B∩C)|)

=|A|+|B|+|C|

|A∩B|

|B∩C|

|A∩C|+|A∩B∩C|84容斥原理容斥原理還可以進(jìn)一步推廣到

m

個(gè)有限集的計(jì)數(shù)問(wèn)題上：85第一章基礎(chǔ)知識(shí)§1.1集合與序列§1.1.1集合的基本概念§1.1.2集合的運(yùn)算及性質(zhì)§1.1.3序列§1.2數(shù)論基礎(chǔ)§1.3計(jì)數(shù)基礎(chǔ)§1.3.1加法法則與乘法法則§1.3.2排列與組合§1.3.3鴿巢原理§1.3.4有限集合的計(jì)數(shù)——容斥原理§1.3.5遞推關(guān)系§1.4布爾矩陣及其運(yùn)算86遞推關(guān)系設(shè)序列為

a0,a1,…,an,…。一個(gè)把a(bǔ)n

與某個(gè)或某些

ai(i<n)聯(lián)系起來(lái)的等式叫做關(guān)于序列

{an}的遞推關(guān)系（recurrencerelation）。當(dāng)給定遞推關(guān)系和適當(dāng)?shù)?/p>

初值后就唯一確定了序列。87遞推關(guān)系例1階乘數(shù)列

1,2,6,24,120,…遞推關(guān)系：F(n)=n

F(n

1)初值：

F(1)=188遞推關(guān)系例2初值：

a1=1遞推關(guān)系：an=an

1+2n

1定義了序列

1,4,9,16,25,…其中an=n289遞推關(guān)系例3初值：

a1=2遞推關(guān)系：an=3an

1+1定義了序列

2,7,22,67,…其中an=?90遞推關(guān)系例4初值：

a1=1,a2=3遞推關(guān)系：an=4an

1

4an

2

定義了序列

1,3,8,20,48,…其中an=?91遞推關(guān)系方法之一——倒推法例1a1=1,an=an

1

nan=an

1

n

=an

2(n

1)

n

=an

3

(n

2)(n

1)

n

=……

=an

(n

1)(n

(n

1)+1)…(n

1)

n

=a12…(n

1)

n

=n!92遞推關(guān)系例2a1=1,an=an-1+2n

1an=an

1+2n

1

=an

2+2(n

1)

1+2n

1

=an

3+2(n

2)

1+2(n

1)

1+2n

1

=……

=an

(n

1)+2(n

(n

1)+1)

1+…2(n

2)

1+2(n

1)

1+2n

1

=a1+2(2+…+n)(n1)

=1+(n+2)(n1)(n1)

=n29394遞推關(guān)系例3a1=2,an=3an

1+1an=3an

1+1

=3(3an

2+1)+1=32an

2+3+1

=32(3an

3+1)+3+1=33an

3+32+3+1

=……

=3(n

1)a1+3(n

1)

1+…+32+3+1

=2

3(n

1)+3(n

1)

1+…+32+3+1

=(5

3n

11)/2漢諾塔法國(guó)數(shù)學(xué)家盧卡斯（EdouardLucas）在1883年提出了一個(gè)數(shù)學(xué)游戲：傳說(shuō)在世界中心貝拿勒斯（印度北部）的圣廟里，一塊黃銅板上有三根寶石柱。印度教的主神大梵天在創(chuàng)造世界的時(shí)候，在其中一根柱上從下到上地穿好了由大到小的64片金盤。大梵天命令僧侶們將圓盤從下面開(kāi)始按大小順序重新擺放在另一根柱子上，并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。預(yù)言說(shuō)當(dāng)這些盤子移動(dòng)完畢時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。95漢諾塔這個(gè)傳說(shuō)又稱作梵天寺之塔問(wèn)題(TowerofBrahmapuzzle)，而且有若干變體：其一是寺院的地點(diǎn)位于越南河內(nèi)，因此該問(wèn)題也常被稱作“河內(nèi)塔”或“漢諾塔（TowerofHanoi）”。

考慮該問(wèn)題的一般形式：有

n

個(gè)圓盤，最初自下而上、自大而小地穿在A柱上，每次按規(guī)則移動(dòng)一個(gè)圓盤，最終將所有圓盤移動(dòng)到C柱上。96漢諾塔共移動(dòng)7次97ABC98漢諾塔漢諾塔先將A柱上所有其他盤子移到B柱上（這是一個(gè)類似于自己的子問(wèn)題）接著將最大的盤子從A柱移到C柱，之后不必再管它最后再將剛才移到B柱上的盤子移到C柱上（這又是一個(gè)子問(wèn)題）。99nABCn-11……漢諾塔漢諾塔的遞歸算法

Hanoi(n,source,dest,by)

輸入：圓盤數(shù)

n。1.

If(n=1)then

1.1.

Print(Movediskfromsourcetodest)2.

Else2.1.

Hanoi(n

1,source,by,dest)2.2.

Print(Movediskfromsourcetodest)2.3.

Hanoi(n

1,by,dest,source)100漢諾塔遞歸算法101直接解決足夠簡(jiǎn)單?Y通過(guò)一些操作簡(jiǎn)化為與自己類似的子問(wèn)題N問(wèn)題規(guī)模變小漢諾塔用

T(n)

表示移動(dòng)

n個(gè)圓盤所需要的步數(shù)根據(jù)算法先把前面

n

1個(gè)盤子轉(zhuǎn)移到B上；然后把第

n個(gè)盤子轉(zhuǎn)到C上；最后再次將B上的

n

1個(gè)盤子轉(zhuǎn)移到C上得到遞推關(guān)系

T(n)=2T(n

1)+1102漢諾塔使用倒推法求解T(n)=2T(n

1)+1,T(1)=1:T(n)=2T(n

1)+1 =2(2T(n

2)+1)+1=22T(n

2)+2+1 =22(2T(n

3)+1)+2+1=23T(n

3)+22+2+1 =…… =2n

1T(1)+2(n

1)

1+…+22+2+1 =2n

1+2(n

1)

1+…+22+2+1 =2n

1103漢諾塔回到最初的漢諾塔問(wèn)題，要將64片金盤重新擺放在另一根柱子上，最少需要

264

1

步，即使僧侶每秒鐘移動(dòng)一步而且每次移動(dòng)都是正確的方法，那么也需要

5.8

1011年，即5千多億年！104斐波那契數(shù)列十三世紀(jì)時(shí)，意大利數(shù)學(xué)家斐波那契（Fibonacci，1170-1250）在名為《算盤書》的數(shù)學(xué)著作中，提出了著名的“兔子問(wèn)題”：假定最初有新生的雌雄兔子一對(duì)，除了本月新生的兔子外，每對(duì)兔子每個(gè)月都可以生出一對(duì)新的兔子；而且假定兔子永遠(yuǎn)不會(huì)死，請(qǐng)問(wèn)

n

個(gè)月后一共有多少對(duì)兔子？105斐波那契數(shù)列106123456…斐波那契數(shù)列設(shè)滿

n個(gè)月時(shí)兔子對(duì)數(shù)為

fn，其中當(dāng)月新生兔數(shù)目設(shè)為

Nn對(duì)，第

n

1個(gè)月存活的兔子數(shù)目設(shè)為

On對(duì)，則有

fn

=Nn+On而

On=fn

1，Nn=fn

2，由此得到

遞推關(guān)系

fn

=fn

1+fn

2初值

f1

=1，f2=1107斐波那契數(shù)列初值：

f1

=1，f2=1遞推關(guān)系：fn=fn

1+fn2，n

3定義了序列

1,1,2,3,5,8,…

這個(gè)序列稱作斐波那契數(shù)列，其本身有著許多應(yīng)用108斐波那契數(shù)列例一個(gè)樓梯有

n級(jí)，每次可以跨上1級(jí)或2級(jí)，求從樓梯的最底端登到最頂端的不同的方法數(shù)。109斐波那契數(shù)列例使用多米諾（dominos）骨牌——即1

2的小方格，覆蓋2

n的方格棋盤有多少種不同的方式？110……斐波那契數(shù)列解.假設(shè)覆蓋

2

n的方格棋盤的不同方式數(shù)為

Sn考慮覆蓋最左上角的小方格，必定是圖(a)或(b)的情況在(a)的情況下，繼續(xù)覆蓋完方格棋盤共有

Sn

2種不同方式在(b)的情況下，繼續(xù)覆蓋完方格棋盤共有

Sn

1種不同方式初值是

S1=1，S2=2因此

Sn就是第

n+1

個(gè)斐波那契數(shù)。111…………(a)(b)112如果an的遞推關(guān)系滿足an+C1an

1+C2an

2+…+Ckan

k=0，且初值為a0=d0,a1=d1,…

ak1=dk1，

則稱這個(gè)等式為k階常系數(shù)線性齊次遞推關(guān)系（linearhomogeneousrelationofdegreek）多項(xiàng)式xk+C1xk

1+C2xk

2+…+Ck=0稱為它的特征多項(xiàng)式或特征方程（characteristicequation），其根稱為特征根（characteristicroot）。2階常系數(shù)線性齊次遞推關(guān)系2階常系數(shù)線性齊次遞推關(guān)系113是否常系數(shù)線性齊次遞推關(guān)系？an=an

1

nXan=an

1+2n

1Xan=3an

1+1Xan=4an

1

4an

2

fn=fn

1+fn

2

Tn=2Tn

1+1Xxn+1=xn(1

xn)X2階常系數(shù)線性齊次遞推關(guān)系例1f1=1,f2=1,fn=fn

1+fn

2特征方程是x2

x

1=0例2a1=1,a2=3,an=4an

1

4an

2

特征方程是

x2

4x+4=01142階常系數(shù)線性齊次遞推關(guān)系下面我們給出2階常系數(shù)線性齊次遞推關(guān)系的解法：假設(shè)

,

是

an=c1an

1+c2an

2的特征方程

x2

c1x

c2=0的兩個(gè)根an=(

+

)an

1

(

)an

2容易驗(yàn)證有

an

an

1=

(an

1

an

2)遞推可以得到：an

an

1=

(an

1

an

2)=

2(an

2

an

3)=...=

n-1(a1

a0)由此倒推得到：an

na0=(

n

1+

n

2+

2

n

3+...+

n

1)(a1

a0)1152階常系數(shù)線性齊次遞推關(guān)系下面我們給出2階常系數(shù)線性齊次遞推關(guān)系的解法：假設(shè)

,

是

an=c1an

1+c2an

2的特征方程

x2

c1x

c2=0的兩個(gè)根若

，則an=u

n+v

n，其中

u,v

由初值決定若

=

，則an=a0

n+(a1

a0)

n

n

11162階常系數(shù)線性齊次遞推關(guān)系例1f1=1,f2=1,fn=fn

1+fn

2