第2章計數(shù)問題

廣東工業(yè)大學(xué)計算機學(xué)院----離散數(shù)學(xué)離散數(shù)學(xué)蔡瑞初23一月20242024/1/23第一篇預(yù)備知識第2章計數(shù)問題2024/1/232.0內(nèi)容提要容斥原理與鴿籠原理3離散概率4乘法原理和加法原理1排列與組合2遞歸關(guān)系52024/1/232.1本章學(xué)習(xí)要求重點掌握一般掌握了解11乘法原理和加法原理2排列組合的計算3利用容斥原理計算有限集合的交與并

31離散概率2離散概念的計算公式及性質(zhì)21鴿籠原理2鴿籠原理的簡單應(yīng)用3遞歸關(guān)系4遞歸關(guān)系的建立和計算

2024/1/232.2.1乘法原理如果一些工作需要t步完成，第一步有n1種不同的選擇，第二步有n2種不同的選擇，…

，第t步有nt種不同的選擇，那么完成這項工作所有可能的選擇種數(shù)為：2024/1/23例2.2.3在一幅數(shù)字圖像中，若每個像素點用8位進行編碼，問每個點有多少種不同的取值。分析用8位進行編碼可分為8個步驟：選擇第一位，選擇第二位，…

，選擇第八位。每一個位有兩種選擇，故根據(jù)乘法原理，8位編碼共有2×2×2×2×2×2×2×2=28=256種取值。解每個點有256(=28)種不同的取值。2024/1/232.2.2加法原理假定X1,X2,…,Xt均為集合，第i個集合Xi有ni個元素。如{X1,X2,…,Xt}為兩兩不相交的集合，則可以從X1,X2,…,Xt中選出的元素總數(shù)為：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt個元素。2024/1/23例2.2.4由Alice、Ben、Connie、Dolph、Egbert和Francisco六個人組成的委員會，要選出一個主席、一個秘書和一個出納員。若主席必須從Alice和Ben種選出，共有多少種選法？2024/1/23例2.2.4解

若Alice被選為主席，共有5×4=20種方法確定其他職位；若Ben為主席，同樣有20種方法確定其他職位。由于兩種選法得到的集合不相交，所以根據(jù)加法原理，共有20＋20=40種選法；2024/1/232.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。

2024/1/23定理2.3.1對滿足r≤n的正整數(shù)n和r有第r位第r-1位第3位第2位第1位nn-1n-2……n-(r-2)圖2.3.1n-(r-1)2024/1/23例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。2024/1/232.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。2024/1/23定理2.3.4對滿足0<r≤n的正整數(shù)n和r有，即

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

2024/1/232.4

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

定義2.4.1

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

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

由圖2.4.1容易看出，A∪B=(A-B)∪(A∩B)∪(B-A)，A=(A-B)∪(A∩B)，B=(A∩B)∪(B-A)。UAB圖2.4.1A∩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是任意有限集合，則2024/1/23例2.4.1對所給的集合驗證定理2.4.1。（1）A={1,2,3,4}，B={2,3,5,6,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成立；2024/1/23三個集合的情形定理2.4.3

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

(2.4.3)推論2.4.4

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

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

設(shè)A、B、C分別表示選修數(shù)學(xué)課程，計算機課程和商貿(mào)課程的人構(gòu)成的集合，則三種課程都不選的學(xué)生集合為，只選修計算機科學(xué)課程學(xué)生的集合為。U圖2.4.2ABC2024/1/23例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）2024/1/23容斥原理的推廣定理2.4.5

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

設(shè)U為全集，A1,A2,…,An是任意n個有限集合，則2024/1/232.4.2鴿籠原理

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

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

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

設(shè)1到10中任意選出六個數(shù)，那么其中有兩個數(shù)的和是11。證明(1)構(gòu)造5個鴿籠：A1={1,10}，A2={2,9}，A3={3,8}，A4={4,7}，A5={5,6}

(2)選出的6個數(shù)為鴿子.根據(jù)鴿籠原理，所選出的6個數(shù)中一定有兩個數(shù)屬于同一個集合，這兩個數(shù)的和為11。2024/1/23定理2.4.5若有n只鴿子住進m(n>m)個鴿籠，則存在一個鴿籠至少住進+1只鴿子。這里，表示小于等于x的最大整數(shù)。2024/1/232.5

離散概率簡介概率(Probability)是17世紀(jì)為分析博弈游戲而發(fā)展起來的學(xué)科，最初計算概率僅有計數(shù)一種方法。本節(jié)主要介紹離散概率的基本概率、基本性質(zhì)和概率計算的簡單例子。2024/1/232.5.1基本概念問題：擲出一個各面同性的骰子，求擲出偶數(shù)的概率。其中“各面同性”是指當(dāng)骰子擲出時，各個面出現(xiàn)的機會均等。定義2.5.1

能生成結(jié)果的過程稱為實驗(experiment)；實驗的結(jié)果或結(jié)果的組合稱為事件(event)，包含所有可能結(jié)果的事件稱為樣本空間(samplespace)。假如骰子的六個面分別標(biāo)記為1,2,3,4,5,6，當(dāng)擲出一個骰子時，一定能擲出6種結(jié)果中的一種，我們稱擲出骰子的過程為實驗，擲出的結(jié)果(假如擲出2)或結(jié)果的組合(假如擲出兩個骰子，一個擲出1，一個擲出3)稱為事件，當(dāng)擲出一個骰子時得到的6種可能1,2,3,4,5,6稱為樣本空間。2024/1/23例2.5.1請舉例說明下列實驗可能發(fā)生的事件，并列出其樣本空間。（1）擲出一個六個面的骰子；（2）從1000個微處理器中隨機抽取5個；（3）在北京人民醫(yī)院選取一個嬰兒。2024/1/23例2.5.1解可能發(fā)生的事件舉例如下：（1）擲出一個六個面的骰子，得到的點數(shù)是4；（2）從1000個微處理器中隨機抽取5個，沒有發(fā)現(xiàn)次品；（3）在北京人民醫(yī)院選取了一個女嬰。各實驗的樣本空間為：（1）1,2,3,4,5,6；（2）從1000個微處理器中選取5個的所有組合；（3）北京人民醫(yī)院的所有嬰兒。2024/1/23定義2.5.2有限樣本空間S中的事件E的概率P(E)定義為：。(2.5.1)其中|E|,|S|分別表示集合E和S的基數(shù)。2024/1/23例2.5.4在福利彩票中，若彩民從1～52個數(shù)中選取的6個數(shù)與隨機生成的中獎數(shù)字相同(不計順序)，則可以贏得大獎。求一張彩票贏得大獎的概率。解從52個數(shù)字中選取6個共有C(52,6)種選法，即|S|=C(52,6)，而得大獎的組合只有一種，即|E|=1，根據(jù)式(2.5.1)，得：P(E)=1/C(52,6)=0.00000004。2024/1/232.5.2離散概率函數(shù)定義2.5.3

如果函數(shù)P將樣本空間S的每一個結(jié)果x映射為實數(shù)P(x)，且對任意的x∈S，滿足（1）0≤P(x)≤1；（2）。則稱函數(shù)P是概率函數(shù)。說明

條件(1)保證一個結(jié)果的概率為非負(fù)數(shù)且不超過1；條件(2)保證所有結(jié)果的概率之和為1，即進行實驗后，必出現(xiàn)某個結(jié)果。2024/1/23概率函數(shù)定義2.5.4

設(shè)E是一個事件，E的概率函數(shù)P(E)定義為。在例2.5.5中，出現(xiàn)奇數(shù)點的概率則為P(1)+P(3)+P(5)=5/8。定理2.5.1

設(shè)E是一個事件，E的補的概率滿足。(2.5.2)2024/1/23例2.2.6生日問題n個人中，求至少有兩個人生日相同(同月同日不計年)的概率。假定出生在某天的概率均等，忽略2月29日。解設(shè)E表示“至少兩個人生日相同”，則表示“沒有兩個人生日相同”，則。從而。事實上，隨著天數(shù)n的增加，至少兩個人生日相同的概率也隨著增加，當(dāng)n≥23時，至少有兩個人生日相同的概率大于1/2。2024/1/23兩個事件并的概率定理2.5.2

設(shè)E1和E2是兩個事件，則

P(E1∪E2)=P(E1)＋P(E2)－P(E1∩E2)

(2.5.3)如果E1∩E2=Φ，即E1與E2為不相交的事件，則有下面的推論。推論2.5.3

設(shè)E1和E2是兩個不相交的事件，則

P(E1∪E2)=P(E1)＋P(E2)

(2.5.4)2024/1/232.6

遞歸關(guān)系遞歸關(guān)系可用于解決一些特定的計數(shù)問題。遞歸關(guān)系是序列中第n個元素與它相鄰前若干個元素之間的關(guān)系。例如第一個數(shù)是5；2、將前一項加3得到后一項。