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

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