計(jì)數(shù)原理(chapter

1、第三章 計(jì)數(shù)原理（chapter 3 Counting ）先修知識(shí)：第一章要 求：仔細(xì)閱讀內(nèi)容，做所有的例子。要 點(diǎn)：本章主要介紹常用的計(jì)數(shù)技術(shù)（counting techniques）。（1）掌握加法原理、乘法原理的基本思想并能熟練運(yùn)用；（2）掌握排列、組合的概念，并熟練運(yùn)用；（3）掌握鴿籠原理的基本思想以及構(gòu)造籠子的常用方法；（4）初步了解概率論的一些基本術(shù)語(yǔ)，并能運(yùn)用排列、組合的知識(shí)進(jìn)行簡(jiǎn)單的計(jì)算；（5）掌握遞歸關(guān)系的定義、常系數(shù)遞歸方程的求解方法。重 點(diǎn)：計(jì)數(shù)的基本原理（加法原理、乘法原理）難 點(diǎn)：鴿籠原理的應(yīng)用（構(gòu)造籠子的方法）計(jì)數(shù)技術(shù)在數(shù)學(xué)、計(jì)算機(jī)科學(xué)、尤其在算法分析中都非常重要。

2、3.1排列（Permutation）一、計(jì)數(shù)的乘法原理（multiplication principle）1、問(wèn)題的提出例1：在數(shù)字式的圖像中每一個(gè)亮點(diǎn)的編碼為八位二進(jìn)制數(shù)。問(wèn)：在一點(diǎn)有多少種可能的編碼值？解：八位編碼可以由連續(xù)的八步構(gòu)成：選擇第1位0或1，選擇第2位0或1，選擇第8位0或1，每一位都有兩種選擇，共有 2×2×2×2×2×2×2×2=28=256（種）2、乘法原理定理1. 假設(shè)一個(gè)任務(wù)（活動(dòng)）T由連續(xù)的t步組成，如果完成第一步有n1種方法；完成第二步有n2種方法；完成第一步有nt種方法，則完成任務(wù)T的方法數(shù)為

3、：n1×n2××nt。 （證明略）例2：計(jì)算機(jī)系統(tǒng)的標(biāo)簽識(shí)別碼由一個(gè)字母后跟三個(gè)數(shù)字組成。如果允許重復(fù)（如a111），有多少種標(biāo)簽編碼值？解：四位編碼可以由連續(xù)的四步構(gòu)成：選擇第一位，有26種可能；選擇第2位，有10種可能；選擇第3位，有10種可能；選擇第4位，有10種可能，共有：26×10×10×10=26000（種）例3：設(shè)A 是含n個(gè)元素的集合，A有多少個(gè)子集？解： A的子集數(shù)與A中元素的選擇有關(guān)。如：A=a，b，c，則 A的子集為： a b c a，b a，c b，c a，b，c 元素的出現(xiàn)：000 100 010 001 1

4、10 101 011 111利用集合的特征函數(shù)，可知：若xA的子集，相應(yīng)位為1，否則，為0。由于A有n個(gè)元素，所以A的每一個(gè)子集都可以用一個(gè)n位的0_1序列描述，每一位都有兩種表示方法，共有：2×2×2××2=2n（種）。注：乘法原理可表述為：當(dāng)一項(xiàng)活動(dòng)是由連續(xù)的幾步組成時(shí)，就把每一步的方法數(shù)乘起來(lái)。二、計(jì)數(shù)的加法原理（addition principle）1、問(wèn)題的提出例1：以101或111打頭的八位二進(jìn)制字符串有多少個(gè)？解：因?yàn)椋阂?01打頭的八位二進(jìn)制字符串的后5位的選擇有25 種；以111打頭的八位二進(jìn)制字符串的后5位的選擇也有25種，所以共有2

5、5+25= 26=64種。2、加法原理定理2. 假設(shè)是集合，且（1）| Xi |=mi，（2）XI和XJ （ij時(shí)）兩兩互不相交，則可以從X1，或者X2，或者Xn中選擇元素的可能數(shù)為：| X1X2Xn|=m1+m2+mt 。（證明略）| X1X2Xn| =在一般情形下，集合X1，X2，Xn 可能相交，這時(shí)公式為：請(qǐng)看下面的例子：例2：75名兒童到公園游樂(lè)場(chǎng)，他們可以騎旋轉(zhuǎn)木馬、坐滑行鐵道車(chē)、乘宇宙飛船。已知其中有20人這三種東西都玩過(guò)，有55人至少乘過(guò)其中的兩種，若每樣乘坐一次的費(fèi)用是5元，公園游樂(lè)場(chǎng)的總收入為700元。試確定有多少兒童沒(méi)有乘坐過(guò)其中的任何一種。解：設(shè)A：騎旋轉(zhuǎn)木馬的兒童的集合

6、；B：坐滑行鐵道車(chē)的兒童的集合；C：乘宇宙飛船的兒童的集合。依題有：|ABC|=20，|A|+|B|+|C|=700/5=140所以，僅乘坐過(guò)兩種的兒童數(shù)為：55-20=35。根據(jù)分析，我們有：35=| AB |+|AC|+|BC|-3×|ABC|，| AB |+|AC|+|BC|=35+60=95|ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC| = 140-95+20=65于是，沒(méi)有乘坐過(guò)其中的任何一種的兒童數(shù)為：75-65=10（人）加法原理和乘法原理統(tǒng)稱(chēng)為計(jì)數(shù)的基本原理 。三、排列（permutations）1、n個(gè)不同元素的全排列1）問(wèn)題的提出例1

7、. 四個(gè)候選人A、B、C和D競(jìng)選同一個(gè)職務(wù)，為使選票上人名的位置不影響選民的選舉，有必要在印制選票時(shí)以各種可能的順序排列名字。應(yīng)有多少種不同的選票？解：根據(jù)乘法原理，一張選票可以由連續(xù)的四步來(lái)構(gòu)造：選擇第一個(gè)名字，有4種選法；選擇第二個(gè)名字，有3種選法；選擇第三個(gè)名字，有2種選法；選擇最后一個(gè)名字，有1種選法；共有 4×3×2×1= 24=4?。ǚN）由上可知：排列即事物的有序化。下面我們給出n個(gè)元素排列的定義：定義1：n個(gè)不同元素x1，x2，xn 的一個(gè)排列就是這n個(gè)元素x1，x2，xn 的一個(gè)次序（序列）。2）n個(gè)不同元素的排列數(shù)定理3：n個(gè)不同的元素有n！個(gè)排

8、列。（證明略）2、n個(gè)不同元素的r排列有時(shí)我們要考慮從n個(gè)不同的元素中選出r個(gè)元素的次序，請(qǐng)看下例：1）問(wèn)題的提出 例2.（圓桌問(wèn)題）（如果一種坐法可以由另一種坐法的每個(gè)人都逆時(shí)針移動(dòng)n個(gè)位置而得到，則這兩種坐法是相同的。）解：用A、B、C、D、E、F表示六個(gè)人，根據(jù)約定，我們可以讓A任意坐，其余的5個(gè)人按逆時(shí)針安排就坐（如CDBFE定義了一種坐法），因?yàn)?個(gè)元素的排列有5！=120種，所以六個(gè)人圍坐在一張圓桌前有120種坐法。結(jié)論：n個(gè)人圍坐在一張圓桌前有（n-1）！坐法。例3. 銀行儲(chǔ)戶(hù)的密碼由4位數(shù)字組成。（1）允許重復(fù)有多少種可能的密碼？（2）如果不允許重復(fù)又有多少種密碼？解：由乘法原

9、理可知：（1）共有10×10×10×10=104=10000 （種）（10個(gè)元素取4個(gè)的可重復(fù)排列）（2）共有10×9×8×7=5040（種）（10個(gè)元素取4個(gè)的不重復(fù)排列）下面我們給出n個(gè)不同元素的一個(gè)r - 排列的定義：定義. n個(gè)不同元素x1，x2，xn 的一個(gè)r - 排列就是這x1，x2，xn 的一個(gè)r元子集的排序。下面我們通過(guò)定理的形式給出求排列的計(jì)算公式：2）n個(gè)元素中一次選r（1rn）個(gè)的排列數(shù)定理4. 設(shè)A是一個(gè)含n個(gè)不同元素的集合且1rn，則由A的元素可形成允許重復(fù)的長(zhǎng)為r的序列數(shù)為nr。 （證明略）定理5. 設(shè)A是

10、一個(gè)含n個(gè)不同元素的集合且1rn，則由A的元素可形成不允許重復(fù)的長(zhǎng)為r的序列數(shù)為n（n-1）（n-2）（n-r+1），記為nPr（或P（n，r） （證明略）特別地，當(dāng)r=n時(shí)，n個(gè)元素中一次選取n個(gè)形成不允許重復(fù)的序列數(shù)為n（n-1）（n-2）1，即n！。而當(dāng)rn，我們也可將nPr表示成階乘的形式，即nPr= n（n-1）（n-2）（n-r+1）= n（n-1）（n-2）（n-r+1）（n-r）1/ （n-r）1=n！/（n-r）?。s定0！=1）于是，我們可以將求排列的公式統(tǒng)一寫(xiě)成階乘的形式，如下所示：例4. 單詞“MAST”中的字母可形成多少個(gè)不允許重復(fù)的3字詞？解：由定理4可知，共有：4

11、P3=4×3×2=4！/（4-3）！=24（種）在大多數(shù)實(shí)例中，集合A中的元素允許重復(fù)，如單詞“MISSISSIPPI” 中的字母可形成多少個(gè)不同的序列？因?yàn)樽帜冈试S重復(fù)，答案就不再是11！，而是比11！小的某個(gè)數(shù)，這就是我們要介紹的第三個(gè)問(wèn)題：3、廣義排列1）問(wèn)題的提出例5. 單詞“MISSISSIPPI” 中的字母可形成多少個(gè)不同的序列？解：在單詞“MISSISSIPPI”中，I出現(xiàn)4次，S出現(xiàn)4次，P出現(xiàn)2次，將重復(fù)的字母用下標(biāo)編號(hào)為 MI1S1S2I1S3S4I3P1P2I4，依題意即求11個(gè)不同的元素的全排列，于是有：11！種。在此編號(hào)下，序列MI1S1S2I1S

12、3S4I3P1P2I4和MI1S1S2I1S3S4I3P2 P1I4是不同的，可去掉下標(biāo)后卻是一樣的，由于P1、P2的排列數(shù)為2！種，故應(yīng)有11！/2！種；類(lèi)似地：MI1S1S2I1S3S4I3P1P2I4、MI1S2 S1I1S3S4I3P1P2I4、MI1S1S2I1S4 S3I3P1P2I4、MI1S1S2I1S3S4I3P1P2I4和MI1S1 S4I1S3 S2I3P1P2I4等在去掉下標(biāo)后都是相同的，應(yīng)該在計(jì)數(shù)過(guò)程中除去，由于S1、S2 、S3、S4的全排列數(shù)為4！，所以應(yīng)有11！/（2！4！），根據(jù)同樣的理由，最后應(yīng)有 11！/（2！4！4?。┓N不同的排列。考慮到M出現(xiàn)了1次，可

13、將結(jié)果寫(xiě)成11！/（2！4！4！1?。?。2）n個(gè)元素中有重復(fù)的排列數(shù)定理6. 設(shè)n個(gè)物體中，第一個(gè)物體出現(xiàn)k1次，第二個(gè)物體出現(xiàn)k2次，第n個(gè)物體出現(xiàn)kt次，則不同的排列數(shù)為：n！/（k1！k2！kt！）。練習(xí)：p 77793.2 組合乘法原理和排列的計(jì)數(shù)方法都要求有序。本節(jié)我們將討論無(wú)序的計(jì)數(shù)問(wèn)題，即不考慮順序的對(duì)象的選取。如A=1，2，3，考慮順序的3-排列有：123，132，213，231，312，321；而不考慮順序時(shí)，上述6種是一樣的。一、問(wèn)題的提出設(shè)A是含n個(gè)不同元素的任意集合a1，a2，an，1rn。A中有多少個(gè)不同的含r 個(gè)元素的子集？這個(gè)問(wèn)題習(xí)慣上稱(chēng)為：組合問(wèn)題二、含n個(gè)不同

14、元素組合的定義設(shè)A是含n個(gè)不同元素的集合a1，a2，an，（1）A的一個(gè)r-組合就是A的包含r個(gè)元素的一個(gè)無(wú)序選擇。（2）一個(gè)包含n個(gè)不同元素的集合的r-組合數(shù)記為nCr（或C（n，r），稱(chēng)為n個(gè)物體中一次選取r的組合數(shù)。例1. 設(shè)A=1，2，3，4，A的3-元子集有四個(gè)，分別為：1，2，3，1，2，4，1，3，4和2，3，4。這和排列不同，4個(gè)元素的3-排列有：4P3=4！/（4-3）！=4！=24=4×3?。ǚN），而4個(gè)元素的3-組合卻只有4種，但兩者之間卻有著某種聯(lián)系：即4C3=4P3/3！。下面我們給出nCr的推導(dǎo)。三、組合計(jì)數(shù)公式nCr（或C（n，r）設(shè)A是含n個(gè)不同元素的

15、任意集合a1，a2，an，1rn，A中一次選取r個(gè)的排列可以由下面兩步構(gòu)成： 任務(wù)1：選取A的含r個(gè)元素的子集B。任務(wù)2：構(gòu)造B的全排列。對(duì)任務(wù)1，記C為n個(gè)不同元素中選取r個(gè)元素的方法數(shù)；對(duì)任務(wù)2，有r！種不同的全排列，因此，完成整個(gè)任務(wù)的方法數(shù)為：C×r！= nPr=n！/（n-r）！，所以，C= nPr / r！= n！/r?。╪-r）！。下面的定理說(shuō)明了這一結(jié)論，并給出了n C r的其它表示方式：定理1. 設(shè)A是任一集合且|A|=n，1rn，則A中一次選取r個(gè)元素的組合數(shù)為：n C r =n！/r?。╪-r）！注：A中一次選取r個(gè)元素的組合數(shù)與A無(wú)關(guān)，僅與n和r有關(guān)。例2.

16、恰好包含四個(gè)1的八位二進(jìn)制字符串有多少個(gè)？解：8C4 =8！/4?。?-4）！=8！/（4！4！）=70（種）例3.（1）從一副52張普通的紙牌中任選5張（無(wú)序）的方法數(shù)有多少種？（2）從一副52張普通的紙牌中任選5張同一花色（無(wú)序）的方法數(shù)有多少種？（3）從一副52張普通的紙牌中任選5張，三張等值，另兩張等值（無(wú)序）的方法數(shù)有多少種？解：（1）52C5=52！/5！（52-5）！=2598960（種） （2）4C1*13C5=4*13！/5！（13-5）！=5148（種） （3）選取三張等值，另兩張等值的5張牌可以經(jīng)過(guò)以下四步完成：選擇第一種面值，有13種選法；選擇第二種面值，有12種選法，

17、選擇第一種面值的3張牌，有4C3種選法，選擇第二種面值的2張牌，有4C2種方法。根據(jù)乘法原理，共有：13×12×4C3×4C2=3744（種）以上我們討論了n個(gè)不同的元素中任選r個(gè)不重復(fù)且無(wú)序的組合問(wèn)題，下面我們考慮允許重復(fù)的無(wú)序選擇的計(jì)數(shù)問(wèn)題：四、廣義組合 1. 問(wèn)題的提出例1. 假設(shè)有三種書(shū)：計(jì)算機(jī)、物理和歷史，圖書(shū)館至少有每本書(shū)的6本復(fù)印本，選取6本書(shū)的方法數(shù)有多少種？分析：用J表示計(jì)算機(jī)書(shū)，W表示物理書(shū)，L表示歷史書(shū)，問(wèn)題是從集合J，W，L中無(wú)序地選取6本，且允許重復(fù)。如JJJWWL、WWWWLL等等。為解決問(wèn)題方便起見(jiàn)，我們引入符號(hào)|作為間隔符，對(duì)于JJ

18、JWWL可表示成JJJ|WW|L；而對(duì)于WWWWLL可表示成|WWWW|LL，于是可將問(wèn)題轉(zhuǎn)化成：在8個(gè)位置中放置2個(gè)“|”的方法數(shù)，即8C2=28（種） 2. 廣義組合的計(jì)數(shù)公式定理2. 從n個(gè)物體中無(wú)序地選取k個(gè)且允許重復(fù)（假設(shè)n個(gè)物體中的每一個(gè)都有k個(gè)重復(fù)）的方法數(shù)為（n+k-1）Ck 。對(duì)上例，n=3，k=6 ，（n+k-1）Ck =（3+6-1）C6 =8C6=28（種）結(jié)論：8C6=8C2定理2的另一種形式：從n個(gè)物體中重復(fù)地選取k個(gè)無(wú)序元素的方法數(shù)是（n+k-1）Ck=（n+k-1）Cn-1例2. 假設(shè)一個(gè)有效的計(jì)算機(jī)密碼由7個(gè)符號(hào)組成，第一個(gè)符號(hào)從集合A，B，C，D，E，F(xiàn)，G

19、中選取，其余6個(gè)符號(hào)是字母或數(shù)字。有多少種不同的密碼？解：密碼的構(gòu)造可以通過(guò)以下兩步完成：第一步：從所給的集合中選擇一個(gè)字符串，有7C1=7種。第二步：選擇允許重復(fù)的字母和數(shù)字序列，有366種.根據(jù)乘法原理，共有7×366種。例3. 7人委員會(huì)由3女4男組成。從20個(gè)婦女和30個(gè)男人中產(chǎn)生7人委員會(huì)的方法數(shù)有多少？解：產(chǎn)生7人委員會(huì)可由以下兩步完成：第一步：從20個(gè)婦女中任選3位，有20C3=1140種第二步：從30個(gè)男人中任選4位，有30C4=27405種.根據(jù)乘法原理，共有1140×2740531241700種不同的委員會(huì)。五、常用的組合恒等式 1. （n+k-1）Ck

20、 =k-1Ck-1 +kCk-1 +（n+k-2）Ck-1 2. n+ 1Ck =nCk-1 +nCk 1kn 3. n+ 1Ck+1 =kCk +k+1Ck +nCk練習(xí)：p 81823.3 鴿籠原理鴿籠原理（也稱(chēng) Dirichlet 抽屜原理或者鞋盒原理）一般用于解決下面的問(wèn)題：具有給定性質(zhì)的項(xiàng)是否存在？原理只是告訴我們對(duì)象的存在，而沒(méi)有給出如何找到他們。一、鴿籠原理的第一種形式定理1. 如果有n只鴿子，m只籠子，且m<n，則至少有一只籠子里面有2只或2只以上的鴿子。證明：假設(shè)每一只籠子里最多有一只鴿子，最多安排了m只，由于m<n，則并非所有的鴿子都在籠子中，矛盾。故：至少有一

21、只籠子里有2只或2只以上的鴿子。例1. 任選8個(gè)人，至少有2個(gè)人是在一星期的同一天出生的。解：這里將人視為鴿子，一星期中的7天是籠子。根據(jù)鴿籠原理，至少有2個(gè)人是在一星期的同一天出生的。例2. 在18的整數(shù)中任取5個(gè)，有兩個(gè)數(shù)之和為9。解：構(gòu)造四個(gè)籠子1，8、2，7、3，6、4，5，在這四個(gè)籠子中任取5個(gè)數(shù)，由鴿籠原理可知：至少有兩個(gè)數(shù)同屬于一個(gè)籠子，根據(jù)籠子的特征，這兩個(gè)數(shù)之和為9。例3. 從集合1，2，3，20中任選11個(gè)數(shù)，則一個(gè)將是另一個(gè)的倍數(shù)。解：從20個(gè)數(shù)中選11個(gè)數(shù)，按鴿籠原理應(yīng)構(gòu)造10個(gè)籠子，且籠子中的數(shù)應(yīng)滿(mǎn)足所要求的性質(zhì)：即一個(gè)將是另一個(gè)的倍數(shù)。利用120中有10個(gè)奇數(shù)，構(gòu)造

22、籠子如下：M1=1*20，1*21，1*22，1*23，1*24，M2=3*20，3*31，3*22，M3=5*20，5*21，5*22，M4=7*20，7*21，M5=9*20，9*21，M6=11*20，M7=13*20，M8=15*20，M9=17*20，M10=19*20，可以看出，這20個(gè)數(shù)無(wú)一遺漏且不重復(fù)地分屬不同的集合，即M1M2 M3M4M5M6M7M8M9M21，2，20，且MkMj（kj）。根據(jù)鴿籠原理，在這10個(gè)籠子中任取11個(gè)數(shù)，至少有兩個(gè)數(shù)屬于同一個(gè)籠子，大數(shù)是小數(shù)的倍數(shù)。例4. 邊長(zhǎng)為1 的正六邊形如下所示。證明：在其中任取7個(gè)點(diǎn)，至少有兩個(gè)點(diǎn)的距離1。 16 2

23、5 3 4 解：依題應(yīng)將該正六邊形劃分成相等的6個(gè)區(qū)域，如圖所示。根據(jù)鴿籠原理：在六個(gè)正三角形（邊長(zhǎng)均為1）中任意放置7個(gè)點(diǎn)，至少有2個(gè)點(diǎn)同屬于一個(gè)三角形，這兩個(gè)點(diǎn)的距離不會(huì)超過(guò)1。例5. 20個(gè)保齡球競(jìng)賽聯(lián)合會(huì)的隊(duì)員身穿編號(hào)120的襯衫。從中任選3個(gè)人組成一個(gè)球隊(duì)，該競(jìng)賽聯(lián)合會(huì)將用這3個(gè)數(shù)字之和作為該隊(duì)的代碼。證明：如果在這20個(gè)數(shù)中任取8個(gè)，至少可以形成兩個(gè)代碼相同的球隊(duì)。解：因?yàn)?個(gè)數(shù)字中任取3個(gè)可組成8C3 =56個(gè)球隊(duì)，依題這56個(gè)球隊(duì)有兩個(gè)代碼相同，因此需要構(gòu)造55個(gè)籠子，每個(gè)籠子形如x+y+z，即：1+2+3，1+3+4，1+4+5，18+19+20，只有52個(gè)不同的數(shù)（也即籠子

24、），最小的是6，最大的是57。根據(jù)鴿籠原理，至少有兩個(gè)球隊(duì)有相同的代碼。二、鴿籠原理的第二種形式定理2. 如果有n只鴿子，m只籠子，且m<n，則有一只籠子里面至少（n-1）/m+1只鴿子。證明：（反證）如果每個(gè)籠子包含的鴿子數(shù)（n-1）/m，則最多有m×（n-1）/m m×（n-1）/m=n-1，矛盾。因此，其中一只籠子必須至少包含（n-1）/m+1只鴿子。例6.（例1的擴(kuò)充）證明：任意選取30個(gè)人，其中必有5個(gè)人在一星期中的同一天出生。解：這里n=30，m=7，根據(jù)鴿籠原理的第二種形式，必有（30-1）/7+1=5個(gè)人（只鴿子）在一星期中的同一天（籠子）出生。例7.

25、 證明：如果30本字典有61327頁(yè)，則有一本字典至少有2045頁(yè)。解：這里n=61327，m=30，根據(jù)鴿籠原理的第二種形式，必有（61327-1）/30+1=2045頁(yè)（只鴿子）在一本字典（籠子）中。練習(xí)：p 85863.4概率基礎(chǔ)一、樣本空間（Sample Spaces）概率實(shí)驗(yàn)（probabilistic）：重復(fù)進(jìn)行多次實(shí)驗(yàn)不會(huì)產(chǎn)生完全一樣的結(jié)果。如：拋擲骰子，無(wú)法知道6個(gè)數(shù)字哪一面朝上；再如：拋硬幣，你也無(wú)法知道是正面（head）朝上還是反面（tail）朝上。這種實(shí)驗(yàn)稱(chēng)為概率實(shí)驗(yàn)。定數(shù)實(shí)驗(yàn)（deterministic）：如果在多次實(shí)驗(yàn)中，產(chǎn)生的結(jié)果是相同的，稱(chēng)為定數(shù)實(shí)驗(yàn)（determ

26、inistic）實(shí)驗(yàn)的樣本空間（Sample Spaces）：包含實(shí)驗(yàn)中所有結(jié)果的集合。例1. 假設(shè)將一枚5分鎳幣和一枚2角5分的輔幣拋向空中，描述三種可能的與這次實(shí)驗(yàn)相關(guān)的樣本空間。（1）如果觀察者要將觀察到的正面（head）的次數(shù)作為結(jié)果來(lái)記錄的話(huà)，則樣本空間是A=0，1，2。因?yàn)樵谝淮螌?shí)驗(yàn)中，兩枚硬幣的正面出現(xiàn)的可能是：都沒(méi)出現(xiàn)（0次）、只出現(xiàn)一個(gè)正面（1次）和出現(xiàn)兩個(gè)正面（2次）（2）如果觀察者決定記錄所觀察到的正面（H）和反面（T）的序列的話(huà)（先寫(xiě)5分鎳幣后寫(xiě)2角5分的輔幣），則樣本空間為A=HH，HT，TH，TT（3）如果觀察者決定記錄兩枚硬幣的匹配（M：同為正面或同為反面）和不匹

27、配（N），則樣本空間A=M，N注：1. 樣本空間與觀察者希望記錄的結(jié)果有關(guān)。2. 樣本空間可以是有限的也可以是無(wú)限的，本章僅討論有限的樣本空間。例2. 確定拋擲2次骰子的樣本空間，記錄每次拋擲后頂面出現(xiàn)的數(shù)字序列。解：實(shí)驗(yàn)結(jié)果可以用一個(gè)有序?qū)Γ╪，m）表示，其中：n和m可以是1，2，3，4，5，6。根據(jù)乘法原理，樣本空間包含了6*6=36個(gè)元素。例3. 一次實(shí)驗(yàn)由連續(xù)地從裝有4枚便士（P）和5枚銀幣（D）的盒子中拋擲三枚硬幣組成，記錄結(jié)果序列。確定這次實(shí)驗(yàn)的樣本空間。解：結(jié)果為長(zhǎng)為3的序列，如PPD、PPP等。所以樣本空間A=PPP，PPD，PDP，PDD，DPP，DPD，DDP，DDD二、事

28、件（Events）1、事件（Events）：是關(guān)于一次實(shí)驗(yàn)的結(jié)果的陳述句，它對(duì)于特殊的結(jié)果具有真或假值。例如：對(duì)于例2，語(yǔ)句“所記錄的每一個(gè)數(shù)字<3”和“所記錄的數(shù)字之和是4”都是描述事件的。由事件的集合，其元素均使語(yǔ)句為真。如：由語(yǔ)句“所記錄的每一個(gè)數(shù)字<3”產(chǎn)生的集合為E=（1，1），（1，2），（2，1），（2，2），而語(yǔ)句“所記錄的數(shù)字之和是4” 產(chǎn)生的集合為E=（1，3），（2，2），（3，1）注：可以看出，事件所描述的集合是樣本空間的子集。例4. 對(duì)例2中的實(shí)驗(yàn)，確定由下列語(yǔ)句（陳述句）所描述的事件。（a）所記錄的頂面數(shù)字之和是8。（b）所記錄的頂面數(shù)字之和至少是10。

29、 解：（a）事件為（2，6），（3，5），（4，4），（5，3），（6，2）（b）事件為（4，6），（5，5），（5，6），（6，6），（6，5），（6，4）2、必然事件（certain event）：如果A是一次實(shí)驗(yàn)的樣本空間，則A就是一個(gè)事件，稱(chēng)為必然事件；A的空集就稱(chēng)為不可能事件（impossible event）由于事件都是一些集合，我們就可以通過(guò)集合的并、交和補(bǔ)運(yùn)算來(lái)構(gòu)造新的事件。樣本空間A就是全集U。假設(shè)E和F是事件，則：EF的含義為：實(shí)驗(yàn)結(jié)果或?qū)儆贓，或?qū)儆贔。EF的含義為：實(shí)驗(yàn)結(jié)果既屬于E又屬于F。當(dāng)EF為空時(shí)，則稱(chēng)事件E和F是相互排斥的（mutually exclusive）

30、。E的含義為：實(shí)驗(yàn)結(jié)果不屬于E。例5. 見(jiàn)p88。三、事件的概率1、事件E的概率 賦給事件E的一個(gè)數(shù)字，記為P（E）。2、P（E）的計(jì)算 P（E）反映了我們對(duì)事件E將發(fā)生的可能性的估計(jì)。假設(shè)基礎(chǔ)實(shí)驗(yàn)是重復(fù)完成的，n次之后，事件E發(fā)生了nE次，則分?jǐn)?shù)fE=nE/n就稱(chēng)為n次實(shí)驗(yàn)中E出現(xiàn)的頻率。例6. 假設(shè)某實(shí)驗(yàn)進(jìn)行了2000次，事件E的發(fā)生頻率fE在100，500，1000和2000實(shí)驗(yàn)之后記錄如下：48，259，496，1002。于是fE分別為：0.48，0.518，0.496，0.501。見(jiàn)下表。實(shí)驗(yàn)的重復(fù)次數(shù)nEfE=nE/n100480.485002590.51810004960.496

31、200010020.501從計(jì)算結(jié)果可以看出：當(dāng)n增大時(shí)，近似于1/2。3、P（E）的性質(zhì)性質(zhì)1. 因?yàn)槭录﨓是樣本空間A的子集，所以對(duì)A中的每個(gè)E有，P1：0P（E）1性質(zhì)2.由于事件A每次都必須發(fā)生（因?yàn)槊總€(gè)結(jié)果都屬于A），且事件不可能發(fā)生，于是有，P2：P（A）1且P（）0性質(zhì)3.如果事件E1，E2，Ek是相互排斥的，則n（E1E2Ek）nE1nE2nEk，兩邊同時(shí)除以n，于是有，P3：P（E1E2Ek）P（E1）P（E2）P（Ek）滿(mǎn)足P1、P2和P3的所有事件構(gòu)成一個(gè)概率空間（probability space），P1、P2和P3稱(chēng)為概率空間（probability space）的公

32、理（axioms）。例7. 考慮拋擲硬幣的實(shí)驗(yàn)，記錄出現(xiàn)正面（head）還是反面（tail）。事件E：正面朝上，而事件F：反面朝上。這種機(jī)械式的拋擲是不可控制的，假設(shè)P（E）P（F），由于事件E和F是相互排斥的，記AEF，于是1P（A）P（E）P（F）2P（E），所以P（E）=1/2=P（F）。最后，我們將說(shuō)明對(duì)事件賦以概率的問(wèn)題可以轉(zhuǎn)化為對(duì)最簡(jiǎn)單的情況的考慮。設(shè)是有限的樣本空間，即x1，x2，x n。僅含一個(gè)結(jié)果的事件 x k稱(chēng)為基礎(chǔ)事件，記為p k =p（ x k）稱(chēng)為相對(duì)于結(jié)果x k的基礎(chǔ)概率。由于基礎(chǔ)事件是相互排斥的而且并了之后是A ，由概率公理，有： EP1：0p k1，對(duì)所有的k。

33、 EP2：p1p 2p n如果E是A中的任意事件，即E=xi1，xi2，x i k，則可將E寫(xiě)成E=xi1xi2x i k，由公理P2，有P（E）= pi1p i2 pi k 。因此，只要知道了基礎(chǔ)概率，就可以計(jì)算任一事件E的概率。例8. 假設(shè)某實(shí)驗(yàn)的樣本空間A=1，2，3，4，5，6，基礎(chǔ)概率定義如下：p1=1/12，p2=1/12，p3=1/3,p4=1/6,p5=1/4,p6=1/12.設(shè)E是“結(jié)果是偶數(shù)”的事件，計(jì)算P（E）。解：由于E=2，4，6，所以，P（E）= p2+ p4+ p6=1/3。四、可能的相等結(jié)果（等概率）假設(shè)有限樣本空間x1，x2，x n中的所有結(jié)果都是可能相等的結(jié)

34、果，則基礎(chǔ)概率都是相等的，由于p1p 2p n，所以每個(gè)基礎(chǔ)概率是1/n。設(shè)E是包含k的結(jié)果的事件，不妨設(shè)Ex1，x2，x k，我們有：P（E）= p1p2 p k =1/n1/n1/nk/n因?yàn)?，k=|E|，n=|A|，所以：P（E）=|E|/|A|。在等概率情形下，概率的計(jì)算就轉(zhuǎn)化成對(duì)集合中元素的計(jì)算。本章前面所介紹的計(jì)數(shù)方法在此十分有用。例9. 從52張牌中隨機(jī)選取4張牌，在等概率情形下都是K的概率是多少？解：因?yàn)?2C4=270725，視為樣本空間A，事件E：4張都是K，于是|A| =270725，|E|=1，所以，P（E）=1/270725。例10. 一只盒子內(nèi)裝6只紅球和4只綠球，

35、從中隨機(jī)選取4只，選中2只紅球和2只綠球的概率是多少（在等概率情形下）？解：（1）確定樣本空間A的個(gè)數(shù)： （2）確定事件E的個(gè)數(shù)：15×690（種）所以，P（E）|E|/|A|90/2103/7。例11. 一只骰子拋擲了3次并記錄了拋擲結(jié)果。事件E：3次的數(shù)字相等或3次都不是4的概率是多少？解：假設(shè)在等概率情形下討論。確定樣本空間A中元素的個(gè)數(shù)，|A|=6×6×6=216。設(shè)事件F：3次的數(shù)字相等，于是有|F|6；事件G：3次都不是4，有|G|5×5×5125，則EFG。根據(jù)加法原理：|E|=| FG |=|F|G|FG|61255126。所以

36、，P（E）|E|/|A|126/2167/12。例12. 在例10中，隨機(jī)選取4只球，（a）如果事件E為：紅球不多于2只，計(jì)算E的概率。（b）如果事件F為：紅球不多于3只，計(jì)算F的概率解：樣本空間A的個(gè)數(shù)為：10C42210（種），對(duì)于（a），6C0 × 4C4 6C1 × 4C36C2 × 4C2115所以，P（E）|E|/|A|115/21023/42。對(duì)于（b），6C0 × 4C4 6C1 × 4C36C2 × 4C26C3 × 4C1195，所以，P（F）|F|/|A|195/21013/14。例13. 在長(zhǎng)為10的

37、數(shù)組中查找關(guān)鍵字，記錄查找的次數(shù)。假設(shè)關(guān)鍵字是等概率出現(xiàn)在數(shù)組的任一位置上，這個(gè)實(shí)驗(yàn)的期望值是：1×1/102×1/1010×1/1055/105.5即：我們可以期望在5.5步之內(nèi)找到關(guān)鍵字。說(shuō)明：本題在求解過(guò)程中采用的查找算法是“順序查找法”。如果所查找的關(guān)鍵字是數(shù)組的第一個(gè)元素，比較一次即可，作為事件E1；當(dāng)所查找的關(guān)鍵字是數(shù)組的第二個(gè)元素，比較兩次即可，視為事件E2；，當(dāng)所查找的關(guān)鍵字是數(shù)組的第十個(gè)元素，則需比較十次，即事件E10。E1E10是相互排斥的，事件E的概率 P（E1E2E10）P（E1）P（E2）P（E10）|E1|/|A|E2|/|A|E10|

38、/|A|5.5。練習(xí)：p93-95術(shù)語(yǔ)：（1）樣本空間：實(shí)驗(yàn)結(jié)果的集合，記為A。 （2）事 件：樣本空間A的子集，記為E。 （3）必然事件：E=A（樣本空間本身） （4）不可能事件：E= （5）互斥事件：兩個(gè)事件的交集為空 （6）基礎(chǔ)事件：僅含一個(gè)結(jié)果的事件 （7）事件E的概率：P（E）=n E /n，n E事件E發(fā)生的次數(shù)，n為實(shí)驗(yàn)次數(shù)。 （8）概率空間：滿(mǎn)足性質(zhì)P1、P2和P3的所有事件。P1、P2和P3是公理。 （9）可能相等的結(jié)果：樣本空間A的結(jié)果是可能相等發(fā)生的3.5 遞歸關(guān)系一、遞歸關(guān)系的定義遞歸關(guān)系：用遞歸方式定義或描述一個(gè)序列時(shí)所使用的公式。（遞歸定義的公式）初始條件：用于確定

39、序列最初幾項(xiàng)的公式。例1. a1=1，a2=1，an=an-1+an-2，定義了Fibonacci 序列1，1，2，3，5，8，這里an=an-1+an-2為遞歸關(guān)系，a1=1，a2=1是序列的初始條件。例2. 設(shè)A=0，1，給出A*上長(zhǎng)為n且不含相鄰 “0” 的字符串?dāng)?shù)C n的遞歸關(guān)系。解：當(dāng)n=1時(shí)，滿(mǎn)足要求的字符串有兩個(gè)0和1，所以C1=2；當(dāng)n=2時(shí)，滿(mǎn)足要求的字符串有三個(gè)01、10和11，所以C2=3；當(dāng)n=3時(shí)，滿(mǎn)足要求的字符串有兩個(gè)010、011、101、110、和111，所以C3=5；一般地，假設(shè)長(zhǎng)為n-2且滿(mǎn)足條件的字符串?dāng)?shù)有Cn-2，長(zhǎng)為n-1且滿(mǎn)足條件的字符串?dāng)?shù)有Cn-1，則C n的構(gòu)造如下：對(duì)任意的長(zhǎng)為n-2且不含相鄰“0”的字符串w，無(wú)論其首字符和末字符是否為“0