電子科技大學(xué)離散數(shù)學(xué)課程組國(guó)家精品課程

電子科技大學(xué)離散數(shù)學(xué)課程組——國(guó)家精品課程離散數(shù)學(xué)電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院示范性軟件學(xué)院13一月20232023/1/13第一篇預(yù)備知識(shí)第2章計(jì)數(shù)問題2023/1/132.0內(nèi)容提要容斥原理與鴿籠原理3離散概率4乘法原理和加法原理1排列與組合2遞歸關(guān)系52023/1/132.1本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解11乘法原理和加法原理2排列組合的計(jì)算3利用容斥原理計(jì)算有限集合的交與并

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

2023/1/13表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.752023/1/132.2.1乘法原理如果一些工作需要t步完成，第一步有n1種不同的選擇，第二步有n2種不同的選擇，…

，第t步有nt種不同的選擇，那么完成這項(xiàng)工作所有可能的選擇種數(shù)為：2023/1/13例2.2.2Melissa病毒1990年，一種名叫Melissa的病毒利用侵吞系統(tǒng)資源的方法來(lái)破壞計(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/1/13例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/1/132.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/1/13例2.2.4由Alice、Ben、Connie、Dolph、Egbert和Francisco六個(gè)人組成的委員會(huì)，要選出一個(gè)主席、一個(gè)秘書和一個(gè)出納員。（1）共有多少種選法？（2）若主席必須從Alice和Ben種選出，共有多少種選法？（3）若Egbert必須有職位，共有多少種選法？（4）若Dolph和Francisco都有職位，共有多少種選法？2023/1/13例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；2023/1/13例2.2.4解(續(xù))[法二]

若Alice被選為主席，共有5×4=20種方法確定其他職位；若Ben為主席，同樣有20種方法確定其他職位。由于兩種選法得到的集合不相交，所以根據(jù)加法原理，共有20＋20=40種選法；2023/1/13例2.2.4解(續(xù))(3)[法一]

將確定職位分為3步：確定Egbert的職位,有3種方法；確定余下的較高職位人選,有5個(gè)人選；確定最后一個(gè)職位的人選,有4個(gè)人選。根據(jù)乘法原理，共有3×5×4=60種選法；2023/1/13例2.2.4解(續(xù))[法二]

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

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

給Francisco指定職位，有2個(gè)職位可選；

確定最后一個(gè)職位的人選，有4個(gè)人選。根據(jù)乘法原理，共有3×2×4=24種選法。2023/1/132.3排列與組合Zeke、Yung、Xeno和Wilma四個(gè)候選人競(jìng)選同一職位。為了使選票上人名的次序不對(duì)投票者產(chǎn)生影響，有必要將每一種可能的人名次序打印在選票上。會(huì)有多少種不同的選票呢？從某個(gè)集合中有序的選取若干個(gè)元素的問題，稱為排列問題。2023/1/132.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/1/13例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/1/13定理2.3.1對(duì)滿足r≤n的正整數(shù)n和r有第r位第r-1位第3位第2位第1位nn-1n-2……n-(r-2)圖2.3.1n-(r-1)2023/1/13推論2.3.2n個(gè)不同元素的排列共有n！種，其中

2023/1/13例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/1/13例2.3.36個(gè)人圍坐在圓桌上，有多少種不同的坐法？通過轉(zhuǎn)圈得到的坐法視為同一種坐法。解6個(gè)人圍坐在圓桌上，有120種不同的坐法。

圖2.3.2AEFBDCn個(gè)人圍坐圓桌上，有(n-1)！種不同的坐法，我們稱這種排列為環(huán)排列，從n個(gè)人中選出r個(gè)人為圓桌而坐稱為環(huán)形r-排列。2023/1/13定理2.3.3含n個(gè)不同元素的集合的環(huán)形r-排列數(shù)Pc(n,r)是。(2.3.3)2023/1/13例2.3.4求滿足下列條件的排列數(shù)。(1)10個(gè)男孩和5個(gè)女孩站成一排，無(wú)兩個(gè)女孩相鄰。(2)10個(gè)男孩和5個(gè)女孩站成一圓圈，無(wú)兩個(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/1/13例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/1/132.3.2組合問題定義2.3.2

從含有n個(gè)不同元素的集合S中無(wú)序選取的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/1/13定理2.3.4對(duì)滿足0<r≤n的正整數(shù)n和r有，即

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

2023/1/13例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/1/13例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/1/13例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/1/132.4

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

定義2.4.1

所謂容斥，是指我們計(jì)算某類物體的數(shù)目時(shí)，要排斥那些不應(yīng)包含在這個(gè)計(jì)數(shù)中的數(shù)目，但同時(shí)要包容那些被錯(cuò)誤地排斥了的數(shù)目，以此補(bǔ)償。這種原理稱為容斥原理(ThePrincipleofInclusion-exclusion)，又稱為包含排斥原理。2023/1/13定理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是任意有限集合，則2023/1/13例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/1/13三個(gè)集合的情形定理2.4.3

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

(2.4.3)推論2.4.4

設(shè)U為全集，A，B和C是任意有限集合，則(2.4.4)2023/1/13例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/1/13例2.4.2解

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

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

設(shè)U為全集，A1,A2,…,An是任意n個(gè)有限集合，則2023/1/13例2.4.3對(duì)24名科技人員進(jìn)行掌握外語(yǔ)情況的調(diào)查，其統(tǒng)計(jì)資料如下：會(huì)英、日、德、法語(yǔ)的人數(shù)分別為13、5、10和9。其中同時(shí)會(huì)英語(yǔ)、日語(yǔ)的人數(shù)為2；同時(shí)會(huì)英語(yǔ)和德語(yǔ)、同時(shí)會(huì)英語(yǔ)和法語(yǔ)、同時(shí)會(huì)德語(yǔ)和法語(yǔ)兩種語(yǔ)言的人數(shù)均為4；會(huì)日語(yǔ)的人既不會(huì)法語(yǔ)也不會(huì)德語(yǔ)。試求(1)只會(huì)一種語(yǔ)言的人數(shù)各為多少？(2)同時(shí)會(huì)英、德、法語(yǔ)的人數(shù)為多少？2023/1/13例2.4.3解設(shè)A、B、C、D分別為會(huì)英、日、德、法語(yǔ)的人的集合，由已知條件可知：?|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/1/13例2.4.3解（續(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ì)英、德、法語(yǔ)的只有1人。2023/1/13例2.4.3解（續(xù)）設(shè)只會(huì)英、日、德、法語(yǔ)的人數(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/1/132.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/1/13例2.4.4抽屜里有3雙手套，問從中至少取多少只，才能保證配成一雙？答：4只。2023/1/13例2.4.5

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

(2)選出的6個(gè)數(shù)為鴿子.根據(jù)鴿籠原理，所選出的6個(gè)數(shù)中一定有兩個(gè)數(shù)屬于同一個(gè)集合，這兩個(gè)數(shù)的和為11。2023/1/13定理2.4.5若有n只鴿子住進(jìn)m(n>m)個(gè)鴿籠，則存在一個(gè)鴿籠至少住進(jìn)+1只鴿子。這里，表示小于等于x的最大整數(shù)。2023/1/13例2.4.6如果一個(gè)圖書館里30本離散數(shù)學(xué)書共有12003頁(yè)，那么必然有一本離散數(shù)學(xué)書至少有401頁(yè)。證明設(shè)頁(yè)是鴿子，離散數(shù)學(xué)書是鴿籠，把每頁(yè)分配到它所出現(xiàn)的離散數(shù)學(xué)書中，根據(jù)定理2.4.5，則存在一個(gè)鴿籠至少住進(jìn)即結(jié)論得證。2023/1/132.5

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

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

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

條件(1)保證一個(gè)結(jié)果的概率為非負(fù)數(shù)且不超過1；條件(2)保證所有結(jié)果的概率之和為1，即進(jìn)行實(shí)驗(yàn)后，必出現(xiàn)某個(gè)結(jié)果。2023/1/13例2.5.5一個(gè)一面較重的骰子，2～6以相同的機(jī)會(huì)出現(xiàn)，1出現(xiàn)的機(jī)會(huì)是其他數(shù)字的3倍。試求出1～6的概率函數(shù)值。解設(shè)P(2)=P(3)=P(4)=P(5)=P(6)=a，則P(6)=3a。又因?yàn)镻(1)+P(2)+P(3)+P(4)+P(5)+P(6)=1，所以有5a＋3a=1，即a=1/8。從而P(2)=P(3)=P(4)=P(5)=P(6)=1/8，P(6)=3/8。2023/1/13概率函數(shù)定義2.5.4

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

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

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

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

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

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

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

(2.5.4)2023/1/13例2.5.7擲出兩個(gè)各面同性的骰子，得到“一對(duì)”(兩個(gè)骰子點(diǎn)數(shù)相同)或點(diǎn)數(shù)和為6的概率是多少？解設(shè)E1表示事件“一對(duì)”，E2表示事件“點(diǎn)數(shù)和為6”，則樣本空間大小是36，事件E1的種數(shù)為6,即(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),事件E2的種數(shù)為5，即(1,5),(2,4),(3,3),(4,2),(5,1)。E1∩E2的種數(shù)為1。2023/1/13例2.5.7解（續(xù)）從而P(E1)=1/6

,P(E2)=5/36,P(E1∩E2)=1/36。根據(jù)式(2.5.3)，有

P(E1∪E2)=1/6＋5/36－1/36=5/18

。即得到“一對(duì)”或點(diǎn)數(shù)和為6的概率是5/18。2023/1/132.6

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

5,8,11,14,…遞歸關(guān)系a1=5，an=an-1+3

2023/1/13定義2.6.1對(duì)序列a0,a1,a2,…,an-1,…，用a0,a1,a2,…,an-1中的某些項(xiàng)表示an的等式稱為遞歸關(guān)系(recurrencerelation)。顯示地給出序列a0,a1,a2,…的有限項(xiàng)的值，稱為初始條件(initialcondition)。顯然，遞歸關(guān)系和確定的初始條件一起，才能確定一個(gè)序列。2023/1/13例2.6.1某人投資1000元，每年可收益12％。An表示他在第n年末的總資產(chǎn)。求出定義序列{An}的遞歸關(guān)系和初始條件。解序列{An}的遞歸關(guān)系和初始條件分別為：An=An-1＋0.12×An

-1=1.12An

-1,n≥1,A0=10002023/1/13例2.6.2Sn表示不含子串“111”的n位字符串的個(gè)數(shù)。求出序列{Sn}的遞歸關(guān)系和初始條件。解序列{Sn}的遞歸關(guān)系和初始條件分別為：

Sn=Sn-1＋Sn-2＋Sn-3，n≥4,S1=2,S2=4,S3=7。2023/1/132.7計(jì)數(shù)問題的應(yīng)用例2.7.17個(gè)科學(xué)工作者從事一項(xiàng)機(jī)密的技術(shù)研究，他們的工作室裝有電子鎖，每位科學(xué)工作者都有打開電子鎖用的“鑰匙”。為了安全起見，必須有4位在場(chǎng)時(shí)才能打開大門。試問該電子鎖至少應(yīng)具備多少個(gè)特征？每位科學(xué)工作者的“鑰匙”至少應(yīng)有多少種特征？解為了使任意3個(gè)人在場(chǎng)時(shí)至少缺少一個(gè)特征而打不開門，該電子鎖至少應(yīng)具備C(7,3)=35種特征；每個(gè)科學(xué)工作者的“鑰匙”至少要有C(6,3)=20種特征。2023/1/13例2.7.2某一制造鐵盤的工廠，由于設(shè)備和技術(shù)的原因只能將生產(chǎn)盤子的重量控制在a克到（a+0.1）克之間。現(xiàn)需要制成重量相差不超過0.005克的兩鐵盤來(lái)配制一架天平，問該工廠至少要生產(chǎn)多少鐵盤才能得到一對(duì)符合要求的鐵盤。2023/1/13例2.7.2解將鐵盤按重量分類，所有a克到a+0.005克的分為第一類；a+0.005克到a+0.01克的分為一類；a+0.01克到a+0.015克的又為一類，….，最后，a+0.095克到a+0.1克為一類，共計(jì)20類，由鴿籠原理知，若該工廠生產(chǎn)21個(gè)鐵盤，那么就能得知有兩個(gè)鐵盤屬于同一類，因而它們之間的重量差將不超