離散數(shù)學(xué)第七章計數(shù).ppt

第七章 計數(shù),7.1 基本計數(shù)原理,1.加法原理 2.乘法原理,加法原理,加法原理又稱為和計數(shù)原理，也稱和規(guī)則，存在三種表述形式，其本質(zhì)是說，整體等于其部分之和。 若集合X是不相交非空子集S1，S2，Sm的并，則|X|= 若E1，E2，Em是彼此互斥事件，并且E1發(fā)生有e1種方式，E2發(fā)生有e2種方式，Em發(fā)生有em種方式，則E1或E2或或Em發(fā)生有e1+e2+em種方式。 應(yīng)該指出的是，事件E1和E2互斥是說，E1和E2發(fā)生但兩者不能同時發(fā)生。, 如果選擇事物O1有n1種方法，選擇事物O2有n2種方法，選擇事物Om有nm種方法，并且選擇諸事物方法不重疊，則選取O1或O2或或Om有n1+n2+nm種方法。,加法原理,例7.1.1 一個學(xué)生想選修一門數(shù)學(xué)課或一門生物學(xué)課，但不能同時選修兩門課。如果該生對5門數(shù)學(xué)課和3門生物學(xué)課具有選課條件，試問該生有多少方式來選修課程？,乘法原理,乘法原理又稱有序計數(shù)原理，也稱積規(guī)則，類似加法原理，也有三種表述形式。 若S1，S2，Sm是非空集合，則笛卡爾積S1S2Sm的元素個數(shù)是 若事件E1，E2，Em發(fā)生分別有e1，e2，em種方式，并且諸事件是獨立的，則事件E1或E2或或Em依次發(fā)生有e1e2em種方式。,乘法原理, 如果選取事物O1，O2，Om分別有n1，n2，nm種方法，并且選取諸事物方法不重疊，則事物O1與O2與與Om依次選取有n1n2nm種方法。,乘法原理,例7.1.2 一個學(xué)生要選修兩門課，第一門課在上午4小時內(nèi)任選1小時，第二門課在下午3小時內(nèi)也可任選1小時，試問該生有多少種可能的時間安排？,例7.1.3 計數(shù)因特網(wǎng)地址。在由計算機(jī)的物理網(wǎng)絡(luò)互連而構(gòu)成的因特網(wǎng)中，每臺計算機(jī)的網(wǎng)絡(luò)連接被分配一個因特網(wǎng)地址。在網(wǎng)際協(xié)議版本IPV4中，一個地址是32位的位串，它以網(wǎng)絡(luò)標(biāo)識netid開始，后跟隨主機(jī)標(biāo)識hostid，該標(biāo)識把一個計算機(jī)認(rèn)定為某個指定網(wǎng)絡(luò)成員。,乘法原理,乘法原理,根據(jù)網(wǎng)絡(luò)標(biāo)識和主機(jī)標(biāo)識位數(shù)的不同目前使用3類地址形式： 用于最大規(guī)模網(wǎng)絡(luò)的A類地址，由0后跟7位網(wǎng)絡(luò)標(biāo)識和24位的主機(jī)標(biāo)識構(gòu)成。 用于中等規(guī)模網(wǎng)絡(luò)的B類地址，由位串10后跟14位的網(wǎng)絡(luò)標(biāo)識和16位的主機(jī)標(biāo)識構(gòu)成。 用于最小規(guī)模網(wǎng)絡(luò)的C類地址，由位串110后跟21位的網(wǎng)絡(luò)標(biāo)識和8位的主機(jī)標(biāo)識構(gòu)成。 此外，又規(guī)定位串1111111在A類的網(wǎng)絡(luò)標(biāo)識中是無效的，全0和全1組成的主機(jī)標(biāo)識對任何網(wǎng)絡(luò)都是無效的。試計數(shù)因特網(wǎng)上的計算機(jī)有多少不同的有效IPV4地址？,乘法原理,令D是因特網(wǎng)上計算機(jī)的有效地址數(shù)，DA,DB,DC分別表示A類B類和C類的有效地址，根據(jù)加法原理D= DA+DB+DC A類的網(wǎng)絡(luò)標(biāo)識有27-1=127個（ 1111111無效），主機(jī)標(biāo)識224-2=16777214（全0和全1組成的主機(jī)標(biāo)識無效），根據(jù)乘法原理，DA=127*16777214,乘法原理,B類的網(wǎng)絡(luò)標(biāo)識有214個，主機(jī)標(biāo)識216-2個，根據(jù)乘法原理，DB= 214 * （216-2） C類的網(wǎng)絡(luò)標(biāo)識有221個，主機(jī)標(biāo)識28-2個，根據(jù)乘法原理，DB= 221 * （28-2） D= DA+DB+DC=3737091842,7.2 鴿洞原理,若n+1只鴿子入住n個鴿洞，則至少有1個鴿洞里至少有2只鴿子。 例7.2.1 在任意一群366人中，至少有2人生日相同。 例7.2.2 抽屜里有3副手套，隨意抽出4只手套，則其中至少有一副手套。,鴿洞原理,例7.2.3 一個學(xué)生用37天準(zhǔn)備考試。根據(jù)以往的經(jīng)驗他知道需要復(fù)習(xí)的時間不超過60個小時，他打算每天至少復(fù)習(xí)1小時，證明不管他如何安排學(xué)習(xí)時間表（假定每天學(xué)習(xí)時數(shù)為整數(shù)），必存在相繼的若干天，他恰好共學(xué)習(xí)13小時。,鴿洞原理,設(shè)t1是第一天學(xué)習(xí)的時數(shù)，t2是前2天學(xué)習(xí)時數(shù)，t3是前3天學(xué)習(xí)時數(shù) 因為每天至少學(xué)習(xí)1小時，所以t11,數(shù)列t1,t2,t37是嚴(yán)格單調(diào)遞增的：t1t2t37 復(fù)習(xí)的時間不超過60個小時,所以t3760 數(shù)列t1+13,t37+13也是嚴(yán)格遞增的，并且t37+13 73,鴿洞原理,因此74個數(shù)t1,t2,t37,t1+13,t37+13都位于1和73之間，根據(jù)鴿洞原理，它們之中必有兩個數(shù)相等 由于前37個數(shù)和后37個數(shù)都是彼此不相等的，故存在兩個數(shù)i和j，使得ti=tj+13 于是j+1，j+2，i這些天中，該生恰好學(xué)習(xí)13小時,鴿洞原理的推廣,設(shè)m1,m2,mn是正整數(shù)，并有m1+m2+mn-n+1只鴿子住進(jìn)n個鴿洞，則或者 第1個鴿洞至少有m1只鴿子，或者第2個鴿洞至少有m2只鴿子，或者第n個鴿洞至少有mn只鴿子。 證明：反證法。假設(shè)第一個鴿洞住進(jìn)的鴿子數(shù)少于m1只，第2個鴿洞住進(jìn)鴿子數(shù)少于m2只于是，鴿子總數(shù)不超過（m1-1）+（m2-1）+（mn-1)=m1+m2+mn-n 與m1+m2+mn-n+1只鴿子矛盾,7.3 容斥原理,有限集合中的容斥定理,在無限集合中不一定成立. 2個集合的情形：|AB| = |A| + |B| |AB| 3個集合的情形：|ABC| = |A| + |B|+|C| |AB| |AC| |BC|+ |ABC| 一般情形：,設(shè)S為全集，又因為 則有,2個集合的情形： = |S| (|A| + |B|) + |AB| 3個集合的情形： = |S| (|A| + |B|+|C|) + (|AB| + |AC| + |BC|) |ABC|,例 一個班里有50個學(xué)生，在第一次考試中有26人得5分，在第二次考試有21人得5分如果兩次考試中都沒得5分的有17人，那么兩次考試都得5分的有多少人？ 解 設(shè)A，B分別表示在第一次和第二次考試中得5分的學(xué)生的集合，那么有 |S|=50, |A|=26, |B|=21, =17 由 = |S| (|A| + |B|) + |AB|，得 |AB| = |S| + (|A| + |B|) = 17 50 + 26 + 21=14 有14人兩次考試都得5分,7.4 排列與組合,我們以前討論的排列稱為線排列更為確切，因為它隱含著將所選擇的r元素排成在一直線上，若使線排列的首末元素相鄰就得了“圓排列”。 定義7.4.2 從n元集S中有序選擇r個元素并排成一個圓周稱為S的一個r圓排列，不同的r圓排列總數(shù)記為K(n，r)或 。,由于在圓排列中重要的是元素彼此間相對位置，因此一個圓排列經(jīng)過旋轉(zhuǎn)后得到的仍是同一個圓排列，而線排列則不然了，只要有一個元素的位置發(fā)生變化便得到不同的排列?？紤]到對每一個固定的n個元素取r個的圓排列均恰有r種不同方式展成r個不同線排列，不同的圓排列展成的線排列彼此也必不同，全部圓排列展出的恰好就是全部線排列，因此線排列數(shù)是圓排列數(shù)的r倍，于是 K(n，r)=P(n，r)/r 特別當(dāng)r=n時，K(n，n)=P(n，n)/n=(n-1)!,例7.4.2 6顆顏色不同的鉆石，可穿成幾種鉆石圈? 圓排列就是在P（6，6）的基礎(chǔ)上，本來在這里面ABCDEFG和BCDEFGA是不同的，但是“圓排列”這里因為形成了一個圓圈，所以，ABCDEFG和BCDEFGA是相同的，同樣“CDEFGAB”等和他們也是相同的，可見，一個相同的圓排列在原有的P（6，6）中是被重復(fù)計算了6次，于是圓排列的結(jié)果是：P(6,6)/6=1*2*3*4*5=120 又因為鉆石圈是可以翻轉(zhuǎn)的，也就是在這里“ABCDEF”和“FEDCBA”是一樣的（想象一下手鐲，你平放著，你再翻轉(zhuǎn)一下，還是原來的手鐲，但是你同樣是順時針編號，得出的號碼是正好調(diào)轉(zhuǎn)的），于是在圓排列的基礎(chǔ)上你要除以2，得到P(6,6)/6/2=60種。,例7.4.3 6個人坐成一個圓形,可以有多少種坐法? 你只要考慮“圓排列”了，因為你不能把人底朝天的翻轉(zhuǎn)，于是答案是P（6，6）/6=120種,下面我們主要講解重集的排列與組合 所謂重集是指其元素可以多次出現(xiàn)的集合，某元素ai出現(xiàn)的次數(shù)ni(ni=1，2，)稱為該元素的重復(fù)數(shù)或重復(fù)度。如重集S中有k個元素a1，a2，ak，其重復(fù)數(shù)分別為n1，n2，nk，則S=n1a1，n2an，nkak。 重集的排列 定義：從重集S =n1a1，n2an，nkak中有序選擇r個元素稱為S的一個r排列，當(dāng)r =n1+n2+nk時也稱S的全排列或S的排列。,定理7.4.5 設(shè)重集S=a1，a2，ak，則S的r排列數(shù)是kr。 推論 設(shè)重集S=n1a1，n2a2，nkak，且nir，1ik，則S的r排列數(shù)是kr。 下面我們來看重集的全排列。先看下面這個例子。,例： 1個m，4個i，5個s，2個p全部使用，共能組成多少個單詞？ 解：有12個空格： 把145212個字母全部放進(jìn)這12個格子中即算完成這件事。先從12個格子中選1個放m，再從剩下的12111個格子中選4個放i，再從剩下的12147個格子中選5個格式放s，再從最后121452個格子中選2個放p，由乘法原理知，共有 種方法。,定理7.4.6 設(shè)重集S =n1a1，n2an，nkak，且n1+n2+nk =n,則S的全排列數(shù)是,重集的組合 定義：設(shè)重集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組合。,定理7.4.7 設(shè)重集S = a1，a2，ak，則S的r組合數(shù)是C(k+r-1，r)。,證：S的每個r組合可以用k-1條豎線和r顆星的形式來表示。其中k-1條豎線表示k個不同的單元。當(dāng)集合的第i個元素出現(xiàn)在組合中，第i個單元就包含一顆星。如，4元素集合的一個6組合用3條豎線和6顆星來表示。例如 | | | 表示包含2個第一元素a1 ，1個第二元素a2 ，0個第三元素a3和3個第四元素a4的組合。 所以包含k-1條豎線和r顆星的每一個不同的情況就對應(yīng)于k元素集合的允許重復(fù)的一個r組合。所有這些情況的個數(shù)是 C(k+r-1，r) 。因為每種情況對應(yīng)于從包含r顆星和k-1條豎線共k-1+r個位置中取r個位置來放r顆星的一個選擇。,推論1 設(shè)重集S=n1a1，n2a2，nkak，且nir，1ik，則S的r組合數(shù)是C(k+r-1，r)。 推論2 設(shè)重集S=a1，a2，ak，且rk，則S中每個元素至少選擇一個的r組合數(shù)是C(r-1，k-1)。,例7.4.6 面包店供應(yīng)8種面點。如果一盒裝12個面點，并且面包店有大量（每種至少12個）各種面點，問能供應(yīng)多少不同面點盒？ 解 設(shè)8種面點分別記為a1，a2，a8，所求不同面點盒個數(shù)是重集=a1，a2，a8或=12a1，12a2，12a8的12組合數(shù)，即C(8+12-1,12)C(19,12)C(19,7),7.5 遞推關(guān)系,定義7.5.1 將數(shù)列H(0)，H(1)， H(n)，中任一項H(n)與其前某些項H(i)用相等、小于等于或大于等于聯(lián)結(jié)起來的式子，稱為遞推關(guān)系，其中n0in，這里n0是一個非負(fù)整數(shù)。稱H(0)，H(1)，H(n0)為初始條件。由初始條件和遞推關(guān)系而導(dǎo)出通項的顯示表達(dá)式，稱為遞推公式。也稱遞推公式是遞推關(guān)系的解。,例7.5.1 漢諾塔游戲。它是由安裝在三根固定的柱子上和不同尺寸的n個圓盤組成。開始時，這些圓盤按大小的次序放在第一根柱子上，使大圓盤在底下。游戲的規(guī)則是：每次把1個圓盤從一根柱子移到另一根柱子，但不允許這個圓盤放在比它小的圓盤上面。游戲的目標(biāo)是把所有圓盤按照大小的次序都放到第二根柱子上，并且將最大的圓盤放在底部。 令Hn表示把n個圓盤從一根柱子移到另一根柱子所需要的移動次數(shù)。建立關(guān)于序列Hn的遞推關(guān)系。,這一步實際有Hn-1步,這只需1步,這一步又需要Hn-1步,故移動n個圓盤的總步數(shù)Hn=Hn-1+1+Hn-1 =2Hn-1+1,以“Hn=2Hn-1+1，且H1=1”為例，求通項(遞推公式)的常用方法有： 逐差求和(等差數(shù)列通項的求法) 逐商求積(等比數(shù)列通項的求法) 轉(zhuǎn)化為等差或等比數(shù)列后利用等差或等比數(shù)列的通項公式求得 歸納法 迭代方法 母函數(shù)法(生成函數(shù)法),定義：對于序列an：a1，a2，an，構(gòu)造一函數(shù) G(x)= 稱函數(shù)G(x)是序列an的生成函數(shù)，或母函數(shù)，或形式冪級數(shù)。 例如 (1+x)n是序列 的生成函數(shù)。 如若已知序列an，則對應(yīng)的生成函數(shù)G(x)便可根據(jù)定義確定。反之，如若已求得序列的生成函數(shù)G(x)，則該序列也隨之確定。,使用母函數(shù)法，要用到高數(shù)中有關(guān)級數(shù)的知識。這里我們就不詳細(xì)舉例求解了。 下面我們介紹一類特殊的遞推關(guān)系分而治之遞推關(guān)系。,例7.5.2 分而治之遞推關(guān)系。在算法分析中，會分析一個規(guī)模為n的問題分成a個子問題的處理過程，其中每子問題的規(guī)模是n/b。此外，假設(shè)由于分解而需要額外運算為g(n)。若f(n)為求解該問題所需要的運算次數(shù)，于是得到f(n)滿足的遞推關(guān)系 f(n)=af(n/b)+g(n) 稱上式為分而治之遞推關(guān)系。,定理7.5.1 設(shè)f(n)滿足遞推關(guān)系 f(n)= af(n/b)+ c 的增函數(shù)，其中b|n，a1，b1，c為正實數(shù)，則 下面舉一例說明定理7.5.1的應(yīng)用,例如，分析二分檢索算法。若n為偶數(shù)時，二分檢索算法把對某個元素在長度為n的搜索序列中的搜索轉(zhuǎn)化為