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

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

Meir

ibnEzra(1092～1167)和法國數(shù)學(xué)家、哲學(xué)家、天文學(xué)家LevibenGerson(1288～1344)是排列與組合領(lǐng)域的兩位早期研究者。另外，法國數(shù)學(xué)家BlaisePascal還發(fā)明了一種機(jī)械計(jì)算器，這種計(jì)算器非常類似于20世紀(jì)40年代在數(shù)字電子計(jì)算機(jī)發(fā)明之前使用的一種機(jī)械計(jì)算器。同時(shí)，計(jì)數(shù)技術(shù)在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中是很重要的，特別是在《數(shù)據(jù)結(jié)構(gòu)》、《算法分析與設(shè)計(jì)》等后續(xù)課程中有非常重要的應(yīng)用。2023/2/12.0內(nèi)容提要容斥原理與鴿籠原理3乘法原理和加法原理1排列與組合22023/2/1表2.2.1開胃食品主食飲料種類價(jià)格(元)種類價(jià)格種類價(jià)格玉米片(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種不同的選擇，那么完成這項(xiàng)工作所有可能的選擇種數(shù)為：2023/2/11.1本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解1乘法原理和加法原理排列組合的計(jì)算利用容斥原理計(jì)算有限集合的交與并

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

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

根據(jù)題意，確定職位可分為3個(gè)步驟：確定主席有2種選擇；主席選定后，秘書有5個(gè)人選；主席和秘書都選定后，出納有4個(gè)人選。根據(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個(gè)人選；確定最后一個(gè)職位的人選,有4個(gè)人選。根據(jù)乘法原理，共有3×5×4=60種選法；[法二]

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

給田伯光指定職位，有3個(gè)職位可選；

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

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

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

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

2023/2/1例2.3.1從含3個(gè)不同元素的集合S中有序選取2個(gè)元素的排列總數(shù)。解從含3個(gè)元素的不同集合S中有序選取2個(gè)元素的排列總數(shù)為6種。如果將這3個(gè)元素記為A、B和C，則6個(gè)排列為AB,AC,BA,BC,CB,CA。2023/2/1定理2.3.1對(duì)滿足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個(gè)不同元素的排列共有n！種，其中

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

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

證明先從n個(gè)不同元素中選出r個(gè)元素，有C(n,r)種選法，再把每一種選法選出的r個(gè)元素做全排列，有r！種排法。2023/2/1定理2.3.4（續(xù)）根據(jù)乘法原理，n個(gè)元素的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）該組合問題需四步完成：

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

二選第二個(gè)點(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

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

定義2.4.1

所謂容斥，是指我們計(jì)算某類物體的數(shù)目時(shí)，要排斥那些不應(yīng)包含在這個(gè)計(jì)數(shù)中的數(shù)目，但同時(shí)要包容那些被錯(cuò)誤地排斥了的數(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對(duì)所給的集合驗(yàn)證定理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，需先計(jì)算A∪B和A∩B，再計(jì)算|A|,|B|和|A∪B|，然后代入公式(2.4.1)兩端，驗(yàn)證等式即可。分析解(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三個(gè)集合的情形定理2.4.3

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

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

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

設(shè)A、B、C分別表示選修數(shù)學(xué)課程，計(jì)算機(jī)課程和商貿(mào)課程的人構(gòu)成的集合，則三種課程都不選的學(xué)生集合為，只選修計(jì)算機(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個(gè)有限集合，則推論2.4.6

設(shè)U為全集，A1,A2,…,An是任意n個(gè)有限集合，則2023/2/1例2.4.3對(duì)24名科技人員進(jìn)行掌握外語情況的調(diào)查，其統(tǒng)計(jì)資料如下：會(huì)英、日、德、法語的人數(shù)分別為13、5、10和9。其中同時(shí)會(huì)英語、日語的人數(shù)為2；同時(shí)會(huì)英語和德語、同時(shí)會(huì)英語和法語、同時(shí)會(huì)德語和法語兩種語言的人數(shù)均為4；會(huì)日語的人既不會(huì)法語也不會(huì)德語。試求(1)只會(huì)一種語言的人數(shù)各為多少？(2)同時(shí)會(huì)英、德、法語的人數(shù)為多少？2023/2/1解設(shè)A、B、C、D分別為會(huì)英、日、德、法語的人的集合，由已知條件可知：?|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，即同時(shí)會(huì)英、德、法語的只有1人。2023/2/1例2.4.3解（續(xù)）設(shè)只會(huì)英、日、德、法語的人數(shù)分別為x1,x2,x3,x4，則x1＝|A|－|(B∪C∪D)∩A|＝|A|－|(B∩A)∪(C∩A)∪(D∩A)|對(duì)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個(gè)鴿籠，則有一個(gè)鴿籠至少住進(jìn)2只鴿子。證明(反證法)假設(shè)每個(gè)鴿籠至多住進(jìn)1只鴿子，則n個(gè)鴿籠至多住進(jìn)n只鴿子，這與有n+1只鴿子矛盾。故存在一個(gè)鴿籠至少住進(jìn)2只鴿子。?

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