離散數(shù)學(xué)第2章計數(shù)問題

離散數(shù)學(xué)01二月2023電子科技大學(xué)計算機(jī)科學(xué)與工程學(xué)院2023/2/1第2章計數(shù)問題計數(shù)問題是組合數(shù)學(xué)研究的主要問題之一。西班牙數(shù)學(xué)家Abrahamben

Meir

ibnEzra(1092～1167)和法國數(shù)學(xué)家、哲學(xué)家、天文學(xué)家LevibenGerson(1288～1344)是排列與組合領(lǐng)域的兩位早期研究者。另外，法國數(shù)學(xué)家BlaisePascal還發(fā)明了一種機(jī)械計算器，這種計算器非常類似于20世紀(jì)40年代在數(shù)字電子計算機(jī)發(fā)明之前使用的一種機(jī)械計算器。同時，計數(shù)技術(shù)在數(shù)學(xué)和計算機(jī)科學(xué)中是很重要的，特別是在《數(shù)據(jù)結(jié)構(gòu)》、《算法分析與設(shè)計》等后續(xù)課程中有非常重要的應(yīng)用。2023/2/12.0內(nèi)容提要容斥原理與鴿籠原理3乘法原理和加法原理1排列與組合22023/2/1表2.2.1開胃食品主食飲料種類價格(元)種類價格種類價格玉米片(Co)2.15漢堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85魚排(F)3.15可樂(C)0.75啤酒(B)0.75

包含一種主食和一種飲料的午餐有多少種不同的選擇？

包含一種開胃食品、一種主食和一種飲料的午餐有多少種不同的選擇？2023/2/12.2.1乘法原理如果一些工作需要t步完成，第一步有n1種不同的選擇，第二步有n2種不同的選擇，…

，第t步有nt種不同的選擇，那么完成這項工作所有可能的選擇種數(shù)為：2023/2/11.1本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解1乘法原理和加法原理排列組合的計算利用容斥原理計算有限集合的交與并

3離散概率離散概念的計算公式及性質(zhì)2鴿籠原理鴿籠原理的簡單應(yīng)用遞歸關(guān)系遞歸關(guān)系的建立和計算2023/2/1例2.2.2Melissa病毒1990年，一種名叫Melissa的病毒利用侵吞系統(tǒng)資源的方法來破壞計算機(jī)系統(tǒng)，通過以含惡意宏的字處理文檔為附件的電子郵件傳播。當(dāng)字處理文檔被打開時，宏從用戶的地址本中找出前50個地址，并將病毒轉(zhuǎn)發(fā)給他們。用戶接收到這些被轉(zhuǎn)發(fā)的附件并將字處理文檔打開后，病毒會自動繼續(xù)轉(zhuǎn)發(fā)，不斷往復(fù)擴(kuò)散。病毒非?？焖俚剞D(zhuǎn)發(fā)郵件，將被轉(zhuǎn)發(fā)的郵件臨時存儲在某個磁盤上，當(dāng)磁盤占滿后，系統(tǒng)將會死鎖甚至崩潰。問經(jīng)過四次轉(zhuǎn)發(fā)，共有多少個接收者？解根據(jù)Melissa病毒的擴(kuò)散原理，經(jīng)過四次轉(zhuǎn)發(fā)，共有50×50×50×50+50×50×50+50×50+50+1=6377551個接收者。2023/2/1例2.2.3在一幅數(shù)字圖像中，若每個像素點(diǎn)用8位進(jìn)行編碼，問每個點(diǎn)有多少種不同的取值。分析用8位進(jìn)行編碼可分為8個步驟：選擇第一位，選擇第二位，…

，選擇第八位。每一個位有兩種選擇，故根據(jù)乘法原理，8位編碼共有2×2×2×2×2×2×2×2=28=256種取值。解每個點(diǎn)有256(=28)種不同的取值。2023/2/12.2.2加法原理假定X1,X2,…,Xt均為集合，第i個集合Xi有ni個元素。如X1,X2,…,Xt為兩兩不相交的集合，則可以從X1,X2,…,Xt中選出的元素總數(shù)為：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt個元素。2023/2/1例2.2.4由令狐沖、岳不群、左冷禪、田伯光、任我行和東方不敗六個人組成的委員會，要選出一個主席、一個秘書和一個出納員。（1）共有多少種選法？（2）若主席必須從令狐沖和岳不群種選出，共有多少種選法？（3）若任我行必須有職位，共有多少種選法？（4）若田伯光和東方不敗都有職位，共有多少種選法？2023/2/1例2.2.4解（1）根據(jù)乘法原理，可能的選法種數(shù)為6×5×4=120；（2）[法一]

根據(jù)題意，確定職位可分為3個步驟：確定主席有2種選擇；主席選定后，秘書有5個人選；主席和秘書都選定后，出納有4個人選。根據(jù)乘法原理，可能的選法種數(shù)為2×5×4=40；[法二]若令狐沖被選為主席，共有5×4=20種方法確定其他職位；若岳不群為主席，同樣有20種方法確定其他職位。由于兩種選法得到的集合不相交，所以根據(jù)加法原理，共有20＋20=40種選法；2023/2/1例2.2.4解(續(xù))(3)[法一]

將確定職位分為3步：確定任我行的職位,有3種方法；確定余下的較高職位人選,有5個人選；確定最后一個職位的人選,有4個人選。根據(jù)乘法原理，共有3×5×4=60種選法；[法二]

根據(jù)(1)的結(jié)論，如果任我行為主席，有20種方法確定余下的職位；若任我行為秘書，有20種方法確定余下的職位；若任我行為出納員，也有20種方法確定余下的職位。由于三種選法得到的集合不相交，根據(jù)加法原理，共有20＋20＋20=60種選法；2023/2/1例2.2.4解(續(xù))（4）將給田伯光、東方不敗和另一個人指定職位分為3步：

給田伯光指定職位，有3個職位可選；

給東方不敗指定職位，有2個職位可選；

確定最后一個職位的人選，有4個人選。根據(jù)乘法原理，共有3×2×4=24種選法。2023/2/12.3排列與組合

郭靖、楊康、黃蓉和丘處機(jī)四個候選人競選同一職位。為了使選票上人名的次序不對投票者產(chǎn)生影響，有必要將每一種可能的人名次序打印在選票上。會有多少種不同的選票呢？從某個集合中有序的選取若干個元素的問題，稱為排列問題。2023/2/12.3.1排列問題定義2.3.1

從含n個不同元素的集合S中有序選取的r個元素叫做S的一個r-排列，不同的排列總數(shù)記為P(n,r)。如果r=n，則稱這個排列為S的一個全排列，簡稱為S的排列。顯然，當(dāng)r＞n時，P(n,r)=0。

2023/2/1例2.3.1從含3個不同元素的集合S中有序選取2個元素的排列總數(shù)。解從含3個元素的不同集合S中有序選取2個元素的排列總數(shù)為6種。如果將這3個元素記為A、B和C，則6個排列為AB,AC,BA,BC,CB,CA。2023/2/1定理2.3.1對滿足r≤n的正整數(shù)n和r有第r位第r-1位第3位第2位第1位nn-1n-2…

…n-(r-2)n-(r-1)2023/2/1推論2.3.2n個不同元素的排列共有n！種，其中

2023/2/1例2.3.2A,B,C,D,E,F組成的排列中，（1）有多少含有DEF的子串？（2）三個字母D、E和F相連的有多少種？解(1)將DEF看成一個對象，根據(jù)推論2.3.2，滿足條件的排列為A,B,C,DEF的全排列，共有4！=24種；（2）根據(jù)題意，滿足該條件的排列分為兩步：第一步確定D,E和F三個字母的全排列，有3！種排列，第二步將已排序的D,E和F看成一個整體，與A,B和C共4個元素構(gòu)造出A,B,C,D,E,F的全排列，有4！種排列。又根據(jù)乘法原理，滿足條件的排列總數(shù)有3！×4！=144。2023/2/1例2.3.36個人圍坐在圓桌上，有多少種不同的坐法？通過轉(zhuǎn)圈得到的坐法視為同一種坐法。解6個人圍坐在圓桌上，有120種不同的坐法。AEFBDCn個人圍坐圓桌上，有(n-1)！種不同的坐法，我們稱這種排列為環(huán)排列，從n個人中選出r個人為圓桌而坐稱為環(huán)形r-排列。2023/2/1定理2.3.3含n個不同元素的集合的環(huán)形r-排列數(shù)Pc(n,r)是2023/2/1例2.3.4求滿足下列條件的排列數(shù)。(1)10個男孩和5個女孩站成一排，無兩個女孩相鄰。(2)10個男孩和5個女孩站成一圓圈，無兩個女孩相鄰.解(1)根據(jù)推論2.3.2，10個男孩的全排列為10!，5個女孩插入到10個男孩形成的11個空格中的插入方法數(shù)為P(11,5)。根據(jù)乘法原理，10個男孩和5個女孩站成一排，沒有兩個女孩相鄰的排列數(shù)為：10!×P(11,5)=（10!×11!)/6!。2023/2/1例2.3.4解（續(xù)）（2）根據(jù)定理2.3.3，10個男孩站成一個圓圈的環(huán)排列數(shù)為9！，5個女孩插入到10男孩形成的10個空中的插入方法數(shù)為P(10,5)。根據(jù)乘法原理，10個男孩和5個女孩站成一個圓圈，沒有兩個女孩相鄰的排列法為：9!×P(10,5)=（9!×10!)/5!。2023/2/12.3.2組合問題定義2.3.2

從含有n個不同元素的集合S中無序選取的r個元素叫做S的一個r-組合，不同的組合總數(shù)記為C(n,r)。當(dāng)n≥r=0時，規(guī)定C(n,r)=1。顯然，當(dāng)r＞n時，C(n,r)=0。2023/2/1定理2.3.4對滿足0<r≤n的正整數(shù)n和r有，即

證明先從n個不同元素中選出r個元素，有C(n,r)種選法，再把每一種選法選出的r個元素做全排列，有r！種排法。2023/2/1定理2.3.4（續(xù)）根據(jù)乘法原理，n個元素的r排列數(shù)為：即

2023/2/1例2.3.5一副52張的撲克牌含有4種花色：梅花、方片、紅桃和黑桃；各有13種點(diǎn)數(shù)，分別為A,2—10,J,Q,K。試求滿足下列條件的組合數(shù)。（1）手中持有5張牌稱為一手牌，一手牌共有多少種可能的組合？（2）一手牌中的5張都是同一花色，共有多少種可能的組合？（3）一手牌中有3張牌點(diǎn)數(shù)相同，另外兩張牌點(diǎn)數(shù)相同，共有多少種可能的組合？2023/2/1例2.3.5解（1）一手牌可能的組合數(shù)等于從52張牌中選出5張的可能組合數(shù)，有C(52,5)種可能的組合；（2）選同一花色的5張牌分兩步進(jìn)行：一選花色，有C(4,1)種，二在選定的花色中選5張牌，有C(13,5)種。據(jù)乘法原理，有C(4,1)×C(13,5)種；2023/2/1例2.3.5解（續(xù)）（3）該組合問題需四步完成：

一選第一個點(diǎn)數(shù)，有C(13,1)種；

二選第二個點(diǎn)數(shù)，有C(12,1)種：

三選第一點(diǎn)數(shù)的3張牌，有C(4,3)種；

四選第二點(diǎn)數(shù)的2張牌，有C(4,2)種。根據(jù)乘法原理，共有

C(13,1)×C(12,1)×C(4,3)×C(4,2)=13×12×4×6=3744種選法。2023/2/12.4

容斥原理與鴿籠原理容斥原理是研究若干有限集合交與并的計數(shù)問題鴿籠原理則是研究某些特定對象的存在性問題。2023/2/12.4.1容斥原理

定義2.4.1

所謂容斥，是指我們計算某類物體的數(shù)目時，要排斥那些不應(yīng)包含在這個計數(shù)中的數(shù)目，但同時要包容那些被錯誤地排斥了的數(shù)目，以此補(bǔ)償。這種原理稱為容斥原理(ThePrincipleofInclusion-exclusion)，又稱為包含排斥原理。2023/2/1定理2.4.1

設(shè)A和B是任意有限集合，有|A∪B|=|A|＋|B|－|A∩B|。分析

由圖容易看出，A∪B=(A-B)∪(A∩B)∪(B-A)，A=(A-B)∪(A∩B)B=(A∩B)∪(B-A)UABA∩BA-BB-A|A|=|A-B|+|A∩B||B|=|A∩B|+|B-A||A∪B|=|A-B|+|A∩B|+|B-A|

推論2.4.2

設(shè)U為全集，A和B是任意有限集合，則2023/2/1例2.4.1對所給的集合驗證定理2.4.1。（1）A={1,2,3,4}，B={2,3,5,6,8}；（2）A={1,2,3,4}，B={5,6,7,8}。根據(jù)定理2.4.1，需先計算A∪B和A∩B，再計算|A|,|B|和|A∪B|，然后代入公式(2.4.1)兩端，驗證等式即可。分析解(1)∵A∪B={1,2,3,4,5,6,8}，A∩B={2,3}∴|A∪B|=7,|A∩B|=2。

又∵|A|=4,|B|=5，∴|A|＋|B|－|A∩B|=4＋5－2=7=|A∪B|即定理2.4.1成立；(2)略。2023/2/1三個集合的情形定理2.4.3

設(shè)A，B和C是任意三個有限集合，有推論2.4.4

設(shè)U為全集，A，B和C是任意有限集合，則2023/2/1例2.4.2

調(diào)查260個大學(xué)生，獲得如下數(shù)據(jù)：64人選修數(shù)學(xué)課程，94人選修計算機(jī)課程，58人選修商貿(mào)課程，28人同時選修數(shù)學(xué)課程和商貿(mào)課程，26人同時選修數(shù)學(xué)課程和計算機(jī)課程，22人同時選修計算機(jī)課程和商貿(mào)課程，14人對三種課程都選修。問（1）調(diào)查中三種課程都不選的學(xué)生有多少？（2）調(diào)查中只選修計算機(jī)科學(xué)課程的學(xué)生有多少？2023/2/1例2.4.2解

設(shè)A、B、C分別表示選修數(shù)學(xué)課程，計算機(jī)課程和商貿(mào)課程的人構(gòu)成的集合，則三種課程都不選的學(xué)生集合為，只選修計算機(jī)科學(xué)課程學(xué)生的集合為。UABC2023/2/1例2.4.2解（續(xù)）（1）∵|U|=260,|A|=64,|B|=94,|C|=58,|A∩C|=28,|A∩B|=26,|B∩C|=22,|A∩B∩C|=14，所以利用容斥原理得

=106（2）2023/2/1容斥原理的推廣定理2.4.5

設(shè)A1,A2,…,An是任意n個有限集合，則推論2.4.6

設(shè)U為全集，A1,A2,…,An是任意n個有限集合，則2023/2/1例2.4.3對24名科技人員進(jìn)行掌握外語情況的調(diào)查，其統(tǒng)計資料如下：會英、日、德、法語的人數(shù)分別為13、5、10和9。其中同時會英語、日語的人數(shù)為2；同時會英語和德語、同時會英語和法語、同時會德語和法語兩種語言的人數(shù)均為4；會日語的人既不會法語也不會德語。試求(1)只會一種語言的人數(shù)各為多少？(2)同時會英、德、法語的人數(shù)為多少？2023/2/1解設(shè)A、B、C、D分別為會英、日、德、法語的人的集合，由已知條件可知：?|A|＝13，|B|＝5，|C|＝10，|D|＝9，|A∩B|＝2，|A∩C|＝|A∩D|＝|C∩D|＝4，|B∩C|＝|B∩D|＝0,|A∩B∩C|＝|A∩B∩D|＝|B∩C∩D|＝0，|A∩B∩C∩D|＝0，|A∪B∪C∪D|＝24，2023/2/1解（續(xù)）利用容斥原理，并代入已知條件得

24＝13＋5＋10＋9－2－4－4－4－0－0＋0＋0＋0＋|A∩C∩D|－0。得：|A∩C∩D|＝1，即同時會英、德、法語的只有1人。2023/2/1例2.4.3解（續(xù)）設(shè)只會英、日、德、法語的人數(shù)分別為x1,x2,x3,x4，則x1＝|A|－|(B∪C∪D)∩A|＝|A|－|(B∩A)∪(C∩A)∪(D∩A)|對B∩A、C∩A、D∩A應(yīng)用容斥原理，得

|(B∩A)∪(C∩A)∪(D∩A)|＝2＋4＋4－0－0－1＋0＝9故，x1＝13-9＝4。類似地可求出：x2＝3，x3＝3，x4＝2。2023/2/12.4.2鴿籠原理

鴿籠原理（PigeonholePrinciple）又稱為抽屜原理、鴿舍原理，是指如下定理。定理2.4.7(鴿籠原理)

若有n+1只鴿子住進(jìn)n個鴿籠，則有一個鴿籠至少住進(jìn)2只鴿子。證明(反證法)假設(shè)每個鴿籠至多住進(jìn)1只鴿子，則n個鴿籠至多住進(jìn)n只鴿子，這與有n+1只鴿子矛盾。故存在一個鴿籠至少住進(jìn)2只鴿子。?

注意：（1）鴿籠原理僅提供了存在性證明；（2）使用鴿籠原理，必須能夠正確識別鴿子(對象)和鴿巢(某類要求的特征)，并且能夠計算出鴿子數(shù)和鴿巢數(shù)。2023/2/1例2.4.4抽屜里有