離散數(shù)學第七章計數(shù)

1、離散數(shù)學第七章計數(shù)第七章第七章 計數(shù)計數(shù)離散數(shù)學第七章計數(shù)7.1 基本計數(shù)原理基本計數(shù)原理1.加法原理2.乘法原理離散數(shù)學第七章計數(shù)加法原理加法原理加法原理又稱為和計數(shù)原理，也稱和規(guī)則，存在三種表述形式，其本質是說，整體等于其部分之和。 若集合X是不相交非空子集S1，S2，Sm的并，則|X|= 若E1，E2，Em是彼此互斥事件，并且E1發(fā)生有e1種方式，E2發(fā)生有e2種方式，Em發(fā)生有em種方式，則E1或E2或或Em發(fā)生有e1+e2+em種方式。應該指出的是，事件E1和E2互斥是說，E1和E2發(fā)生但兩者不能同時發(fā)生。 |1miiS離散數(shù)學第七章計數(shù)l 如果選擇事物O1有n1種方法，選擇事物O2

2、有n2種方法，選擇事物Om有nm種方法，并且選擇諸事物方法不重疊，則選取O1或O2或或Om有n1+n2+nm種方法。 離散數(shù)學第七章計數(shù)加法原理加法原理l例例7.1.1 一個學生想選修一門數(shù)學課或一門生物學課，但不能同時選修兩門課。如果該生對5門數(shù)學課和3門生物學課具有選課條件，試問該生有多少方式來選修課程？ 離散數(shù)學第七章計數(shù)乘法原理乘法原理l乘法原理又稱有序計數(shù)原理，也稱積規(guī)則，類似加法原理，也有三種表述形式。l 若S1，S2，Sm是非空集合，則笛卡爾積S1S2Sm的元素個數(shù)是l 若事件E1，E2，Em發(fā)生分別有e1，e2，em種方式，并且諸事件是獨立的，則事件E1或E2或或Em依次發(fā)生有

3、e1e2em種方式。|1miiS離散數(shù)學第七章計數(shù)乘法原理乘法原理l 如果選取事物O1，O2，Om分別有n1，n2，nm種方法，并且選取諸事物方法不重疊，則事物O1與O2與與Om依次選取有n1n2nm種方法。 離散數(shù)學第七章計數(shù)乘法原理乘法原理l例例7.1.2 一個學生要選修兩門課，第一門課在上午4小時內任選1小時，第二門課在下午3小時內也可任選1小時，試問該生有多少種可能的時間安排？ 離散數(shù)學第七章計數(shù)l例例7.1.3 計數(shù)因特網地址。在由計算機的物理網絡互連而構成的因特網中，每臺計算機的網絡連接被分配一個因特網地址。在網際協(xié)議版本IPV4中，一個地址是32位的位串，它以網絡標識netid開

4、始，后跟隨主機標識hostid，該標識把一個計算機認定為某個指定網絡成員。 乘法原理乘法原理離散數(shù)學第七章計數(shù)乘法原理乘法原理l根據(jù)網絡標識和主機標識位數(shù)的不同目前使用3類地址形式：l用于最大規(guī)模網絡的A類地址，由0后跟7位網絡標識和24位的主機標識構成。l用于中等規(guī)模網絡的B類地址，由位串10后跟14位的網絡標識和16位的主機標識構成。l用于最小規(guī)模網絡的C類地址，由位串110后跟21位的網絡標識和8位的主機標識構成。l此外，又規(guī)定位串1111111在A類的網絡標識中是無效的，全0和全1組成的主機標識對任何網絡都是無效的。試計數(shù)因特網上的計算機有多少不同的有效IPV4地址？離散數(shù)學第七章計數(shù)

5、乘法原理乘法原理l令D是因特網上計算機的有效地址數(shù)，DA,DB,DC分別表示A類B類和C類的有效地址，根據(jù)加法原理D= DA+DB+DClA類的網絡標識有27-1=127個（ 1111111無效），主機標識224-2=16777214（全0和全1組成的主機標識無效），根據(jù)乘法原理，DA=127*16777214離散數(shù)學第七章計數(shù)乘法原理乘法原理lB類的網絡標識有214個，主機標識216-2個，根據(jù)乘法原理，DB= 214 * （216-2）lC類的網絡標識有221個，主機標識28-2個，根據(jù)乘法原理，DB= 221 * （28-2）lD= DA+DB+DC=3737091842離散數(shù)學第七章計

6、數(shù)7.2 鴿洞原理鴿洞原理l若n+1只鴿子入住n個鴿洞，則至少有1個鴿洞里至少有2只鴿子。l例例7.2.1 在任意一群366人中，至少有2人生日相同。l例例7.2.2 抽屜里有3副手套，隨意抽出4只手套，則其中至少有一副手套。 離散數(shù)學第七章計數(shù)鴿洞原理鴿洞原理l例例7.2.3 一個學生用37天準備考試。根據(jù)以往的經驗他知道需要復習的時間不超過60個小時，他打算每天至少復習1小時，證明不管他如何安排學習時間表（假定每天學習時數(shù)為整數(shù)），必存在相繼的若干天，他恰好共學習13小時。離散數(shù)學第七章計數(shù)鴿洞原理鴿洞原理l設t1是第一天學習的時數(shù)，t2是前2天學習時數(shù)，t3是前3天學習時數(shù)l因為每天至少

7、學習1小時，所以t11,數(shù)列t1,t2,t37是嚴格單調遞增的：t1t2t37l復習的時間不超過60個小時,所以t3760l數(shù)列t1+13,t37+13也是嚴格遞增的，并且t37+13 73離散數(shù)學第七章計數(shù)鴿洞原理鴿洞原理l因此74個數(shù)t1,t2,t37,t1+13,t37+13都位于1和73之間，根據(jù)鴿洞原理，它們之中必有兩個數(shù)相等l由于前37個數(shù)和后37個數(shù)都是彼此不相等的，故存在兩個數(shù)i和j，使得ti=tj+13l于是j+1，j+2，i這些天中，該生恰好學習13小時離散數(shù)學第七章計數(shù)鴿洞原理的推廣鴿洞原理的推廣l設m1,m2,mn是正整數(shù)，并有m1+m2+mn-n+1只鴿子住進n個鴿洞

8、，則或者 第1個鴿洞至少有m1只鴿子，或者第2個鴿洞至少有m2只鴿子，或者第n個鴿洞至少有mn只鴿子。l證明：反證法。假設第一個鴿洞住進的鴿子數(shù)少于m1只，第2個鴿洞住進鴿子數(shù)少于m2只于是，鴿子總數(shù)不超過（m1-1）+（m2-1）+（mn-1)=m1+m2+mn-n與m1+m2+mn-n+1只鴿子矛盾離散數(shù)學第七章計數(shù)7.3 容斥原理容斥原理有限集合中的容斥定理,在無限集合中不一定成立.l2個集合的情形：|AB| = |A| + |B| |AB|l3個集合的情形：|ABC| = |A| + |B|+|C| |AB| |AC| |BC|+ |ABC|l一般情形：|) 1(|21111121nn

9、nkjikjinjijiniinAAAAAAAAAAAA離散數(shù)學第七章計數(shù)設S為全集，又因為則有|)1(|211112121nnnkjikjinjijiniinnAAAAAAAAASAAASAAA|ASA2個集合的情形： = |S| (|A| + |B|) + |AB|3個集合的情形： = |S| (|A| + |B|+|C|) + (|AB| + |AC| + |BC|) |ABC|BA|CBA離散數(shù)學第七章計數(shù)例 一個班里有50個學生，在第一次考試中有26人得5分，在第二次考試有21人得5分如果兩次考試中都沒得5分的有17人，那么兩次考試都得5分的有多少人？解 設A，B分別表示在第一次和第

10、二次考試中得5分的學生的集合，那么有|S|=50, |A|=26, |B|=21, =17由 = |S| (|A| + |B|) + |AB|，得|AB| = |S| + (|A| + |B|) = 17 50 + 26 + 21=14有14人兩次考試都得5分|BA|BA|BA離散數(shù)學第七章計數(shù)7.4 排列與組合排列與組合 我們以前討論的排列稱為線排列更為確切，因為它隱含著將所選擇的r元素排成在一直線上，若使線排列的首末元素相鄰就得了“圓排列”。定義定義7.4.2 從n元集S中有序選擇r個元素并排成一個圓周稱為S的一個r圓排列，不同的r圓排列總數(shù)記為K(n，r)或 。 rnK離散數(shù)學第七章計數(shù)

11、 由于在圓排列中重要的是元素彼此間相對位置，因此一個圓排列經過旋轉后得到的仍是同一個圓排列，而線排列則不然了，只要有一個元素的位置發(fā)生變化便得到不同的排列?？紤]到對每一個固定的n個元素取r個的圓排列均恰有r種不同方式展成r個不同線排列，不同的圓排列展成的線排列彼此也必不同，全部圓排列展出的恰好就是全部線排列，因此線排列數(shù)是圓排列數(shù)的r倍，于是K(n，r)=P(n，r)/r特別當r=n時，K(n，n)=P(n，n)/n=(n-1)!離散數(shù)學第七章計數(shù)l例例7.4.2 6顆顏色不同的鉆石，可穿成幾種鉆石圈? l圓排列就是在P（6，6）的基礎上，本來在這里面ABCDEFG和BCDEFGA是不同的，但

12、是“圓排列”這里因為形成了一個圓圈，所以，ABCDEFG和BCDEFGA是相同的，同樣“CDEFGAB”等和他們也是相同的，可見，一個相同的圓排列在原有的P（6，6）中是被重復計算了6次，于是圓排列的結果是：P(6,6)/6=1*2*3*4*5=120 l又因為鉆石圈是可以翻轉的，也就是在這里“ABCDEF”和“FEDCBA”是一樣的（想象一下手鐲，你平放著，你再翻轉一下，還是原來的手鐲，但是你同樣是順時針編號，得出的號碼是正好調轉的），于是在圓排列的基礎上你要除以2，得到P(6,6)/6/2=60種。離散數(shù)學第七章計數(shù)l例例7.4.3 6個人坐成一個圓形,可以有多少種坐法? l你只要考慮“圓

13、排列”了，因為你不能把人底朝天的翻轉，于是答案是P（6，6）/6=120種 離散數(shù)學第七章計數(shù) 下面我們主要講解重集的排列與組合 所謂重集是指其元素可以多次出現(xiàn)的集合，某元素ai出現(xiàn)的次數(shù)ni(ni=1，2，)稱為該元素的重復數(shù)或重復度。如重集S中有k個元素a1，a2，ak，其重復數(shù)分別為n1，n2，nk，則S=n1a1，n2an，nkak。 l重集的排列 定義：從重集S =n1a1，n2an，nkak中有序選擇r個元素稱為S的一個r排列，當r =n1+n2+nk時也稱S的全排列或S的排列。 離散數(shù)學第七章計數(shù)定理定理7.4.5 設重集S=a1，a2，ak，則S的r排列數(shù)是kr。推論推論 設重

14、集S=n1a1，n2a2，nkak，且nir，1ik，則S的r排列數(shù)是kr。下面我們來看重集的全排列。先看下面這個例子。離散數(shù)學第七章計數(shù) 例： 1個m，4個i，5個s，2個p全部使用，共能組成多少個單詞？ 解：有12個空格： 把145212個字母全部放進這12個格子中即算完成這件事。先從12個格子中選1個放m，再從剩下的12111個格子中選4個放i，再從剩下的12147個格子中選5個格式放s，再從最后121452個格子中選2個放p，由乘法原理知，共有 種方法。! 2! 5! 4! 1!12! 0! 2! 2! 2! 5! 7! 7! 4!11!11! 1!122257411112CCCC離散

15、數(shù)學第七章計數(shù) 定理定理7.4.6 設重集S =n1a1，n2an，nkak，且n1+n2+nk =n,則S的全排列數(shù)是!21knnnn離散數(shù)學第七章計數(shù)l重集的組合 定義：設重集S =n1a1,n2an,nkak ，S中r個元素的子重集稱為S的r組合。 由定義知，若S有n個元素，即n1+n2+nk =n，則S的n組合只有一個，即S自身。若S含有k個不同元素，則存在k個S的1組合。 例如： S=3a, 1b, 2c，則a, a,a, b,a, c,b, c,c, c都是S的2組合。離散數(shù)學第七章計數(shù)定理定理7.4.7 設重集S = a1，a2，ak，則S的r組合數(shù)是C(k+r-1，r)。 證：

16、S的每個r組合可以用k-1條豎線和r顆星的形式來表示。其中k-1條豎線表示k個不同的單元。當集合的第i個元素出現(xiàn)在組合中，第i個單元就包含一顆星。如，4元素集合的一個6組合用3條豎線和6顆星來表示。例如 | | | 表示包含2個第一元素a1 ，1個第二元素a2 ，0個第三元素a3和3個第四元素a4的組合。 所以包含k-1條豎線和r顆星的每一個不同的情況就對應于k元素集合的允許重復的一個r組合。所有這些情況的個數(shù)是 C(k+r-1，r) 。因為每種情況對應于從包含r顆星和k-1條豎線共k-1+r個位置中取r個位置來放r顆星的一個選擇。離散數(shù)學第七章計數(shù)推論推論1 設重集S=n1a1，n2a2，n

17、kak，且nir，1ik，則S的r組合數(shù)是C(k+r-1，r)。推論推論2 設重集S=a1，a2，ak，且rk，則S中每個元素至少選擇一個的r組合數(shù)是C(r-1，k-1)。 離散數(shù)學第七章計數(shù)例例7.4.6 面包店供應8種面點。如果一盒裝12個面點，并且面包店有大量（每種至少12個）各種面點，問能供應多少不同面點盒？ 解 設8種面點分別記為a1，a2，a8，所求不同面點盒個數(shù)是重集=a1，a2，a8或=12a1，12a2，12a8的12組合數(shù)，即C(8+12-1,12)C(19,12)C(19,7)離散數(shù)學第七章計數(shù)7.5 遞推關系定義定義7.5.1 將數(shù)列H(0)，H(1)， H(n)，中任一項H(n)與其前某些項H(i)用相等、小于等于或大于等于聯(lián)結起來的式子，稱為遞推關系，其中n0i1，c為正實數(shù)，則下面舉一例說明定理7.5.1的應用 11loglogaa