離散數(shù)學課件：第2章 計數(shù)問題

2022/11/3第一篇預備知識第2章計數(shù)問題2022/11/32.0內(nèi)容提要容斥原理與鴿籠原理3離散概率4乘法原理和加法原理1排列與組合2遞歸關系52022/11/32.1本章學習要求重點掌握一般掌握了解11乘法原理和加法原理2排列組合的計算3利用容斥原理計算有限集合的交與并

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

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

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

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

若Alice被選為主席，共有5×4=20種方法確定其他職位；若Ben為主席，同樣有20種方法確定其他職位。由于兩種選法得到的集合不相交，所以根據(jù)加法原理，共有20＋20=40種選法；2022/11/32.3.1排列問題定義2.3.1

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

2022/11/3定理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)2022/11/3例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。2022/11/32.3.2組合問題定義2.3.2

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

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

2022/11/32.4

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

定義2.4.1

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

設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

設U為全集，A和B是任意有限集合，則2022/11/3例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成立；2022/11/3三個集合的情形定理2.4.3

設A，B和C是任意三個有限集合，有

(2.4.3)推論2.4.4

設U為全集，A，B和C是任意有限集合，則(2.4.4)2022/11/3例2.4.2

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

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

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

設U為全集，A1,A2,…,An是任意n個有限集合，則2022/11/32.4.2鴿籠原理

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

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

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

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