離散數(shù)學(xué)12省公開課一等獎全國示范課微課金獎?wù)n件

1離散數(shù)學(xué)DiscreteMathematics

汪榮貴教授合肥工業(yè)大學(xué)軟件學(xué)院專用課件.04第1頁第三章計數(shù)技術(shù)

第2頁學(xué)習(xí)內(nèi)容3.1TheBasicofCounting計數(shù)基礎(chǔ)3.2ThePigeonholePrinciple鴿巢原理3.3PermutationsandCombinations排列與組合3.4RecurrenceandDivide-and-Conquer遞推與分治3.5GeneratingFunction生成函數(shù)3.6Inclusion-exclusionprinciples容斥原理第3頁計數(shù)基礎(chǔ)TheBasicofCounting

BasiccountingPrinciple基本計數(shù)原理Theinclusion-exclusionprinciples容斥原理TreeDiagrams樹圖第4頁在這一節(jié)我們將引入基本計數(shù)技術(shù)。這些方法是幾乎全部計數(shù)技術(shù)基礎(chǔ)。BasicCountingPrinciples

基本計數(shù)原理（1）TheProductRule乘積法則

（2）TheSumRule

求和法則基本計數(shù)原理（BasiccountingPrinciple

）第5頁Example丟一個銅板和一個骰子共有多少可能結(jié)果？銅板正反面結(jié)果和骰子點數(shù)結(jié)果互不影響，我們將整個工作分成丟銅板和丟骰子兩個子工作，先丟銅板時有2種可能，不論銅板是正面還是反面，擲出來骰子點數(shù)都有6種可能，則能夠知道總可能結(jié)果有2*6=12種，如圖所表示，先擲骰子情況下可能情況數(shù)也是一樣，不論是先丟銅板還是先丟骰子都有結(jié)果2×6=6×2種結(jié)果。第6頁乘積法則(TheProductRule)Definition

Supposethataprocedurecanbebrokendownintotwotasks,Iftherearemwaystodothefirsttaskandnwaystodothesecondtaskafterthefirsttaskhasbeendone,thentherearem*nwaystodotheprocedure.乘積法則定義：假如完成一件事情需要兩個步驟，第一步有m種方法，第二步有n種方法去實現(xiàn)，則完成該件事情共有n*m種方法。NOTE:當(dāng)一個過程由獨立任務(wù)組成時使用乘積法則第7頁Phrasedintermsofsets

(用集合語言描述)IfSandTarefinitesets,thenthenumberofelementsintheCartesianproductofthesesetsistheproductofthenumberofelementsineachset,namely。假如S和T是有窮集，那么在這兩個集合笛卡爾積元素數(shù)是這兩個集合元素數(shù)之積，即

|S

T|=|S|

|T|乘積法則(TheProductRule)第8頁Example1用一個字母和一個不超出100正整數(shù)給禮堂座位編號。那么不一樣編號座位最多有多少？

乘積法則應(yīng)用舉例solution：

整個過程分成兩個任務(wù)組成，即從26個字母中先選出一個字母分配給這個座位，然后在從100個正整數(shù)中選擇一個整數(shù)分配給它。由乘積法則表明一個座位能夠有26*100=2600種不一樣編號。第9頁Example2某個計算機中心有32臺微機，每臺微機有24個端口。問在這個中心里有多少個不一樣單機端口？solution：選擇端口過程包含兩個部分：首先挑一臺微機，能夠有32種方式選擇.其次不論選擇了哪臺微機又有24種方式選擇端口.由乘積法則,存在端口數(shù)為32*24=768第10頁【Example】

從波士頓到底特律有4條汽車主干線，而從底特律到洛杉磯有6條。那么從波士頓經(jīng)底特律到洛杉磯汽車主干線有多少？Solution:

整個任務(wù)能夠分成兩個部分：第一步從波士頓到底特律，能夠有4種選擇路線。第二步從底特律到洛杉磯有6種選擇路線。依據(jù)乘積法則可知從波士頓經(jīng)由底特律從到洛杉磯可能汽車主干線條數(shù)為4*6=24第11頁乘積法則擴(kuò)展SupposethataprocedureiscarriedoutbyperformingthetasksT1,

T2,…,Tm.IftaskTicanbedoneinniwaysaftertasksT1,

T2,…,andTi-1havebeendone,thentherearen1n2…nm

waystocarryouttheprocedure.

假設(shè)一個過程由執(zhí)行任務(wù)來完成。假如在完成任務(wù)之后用種方式來完成，那么完成這個過程有Theextendedversionoftheproductrule乘積法則擴(kuò)展第12頁Example3

Howmanydifferentbitstringsoflength7?

有多少個不一樣7位二進(jìn)制串？

0,1Solution:

Theproductruleshowsthatthereareatotalof27=128differentbitstrings.第13頁Example4假如每個車牌由3個字母后跟3個數(shù)字序列組成（任何字母序列都能夠），那么有多少個不一樣有效車牌？solution：3個字母中每一個字母都有26種選擇，對3個數(shù)字中每一個數(shù)字有10種選擇。由乘積法則全部可能車牌數(shù)是26*26*26*10*10*10=17576000第14頁Example5

CountingFunction

（計數(shù)函數(shù)）

Howmanyfunctionsaretherefromasetwithnelementstoonewithmelements?從一個m元集到一個n元集存在多少個函數(shù)？A……B……f:A

BSolution:Bytheproductruletherearen

n

n=nmfunctionsfromasetwithmelementstoonewithnelements第15頁Example6

Howmanyone-to-onefunctionsaretherefromasetwithmelementstoonewithnelements?從一個m元集到一個n元集存在多少個一對一函數(shù)？A……B……第16頁Solution:(1)m>n

Therearenoone-to-onefunctionsfromasetwithmelementstoonewithnelements.在含有m個元素集合和含有n個元素集合之間不存在一對一函數(shù)。(2)m

n

假設(shè)定義域中元素是a1a2…am

。自變量為a1函數(shù)取值有n種情況，又因為函數(shù)是一對一，所以自變量為a2函數(shù)取值有n-1種情況…依次類推，總共情況有n(n-1)(n-2)…(n-m+1)第17頁Example7電話編碼計劃在北美，電話號碼格式是由一個編號計劃要求，一個電話號碼由10個數(shù)字組成，這些數(shù)字由一個3位地域碼，一個3位局代碼以及一個4位話機代碼組成。出于信號考慮，一些數(shù)字上有某種限制，為了要求允許格式，令X表示0到9之間任意一個數(shù)字，N表示能夠在2到9之間選取數(shù)字，而Y表示必須取0或1數(shù)字分別成為新計劃和老計劃。在老計劃和新計劃下分別有多少個不一樣北美電話號碼？第18頁

—

—

areacodeNYXofficecodeNNXstationcodeXXXXN:2-9X:0–9Y:0/1老計劃新計劃

—

—

areacodeNXXofficecodeNXXstationcodeXXXXN:2-9X:0–9第19頁solution：由乘積法則，格式為NYX地域代碼個數(shù)有8*2*10=160格式為NXX地域代碼有8*10*10=800類似地，由乘積法則，格式為NNX局代碼有

8*8*10=640由乘積法則得到格式為XXXX話機代碼有10*10*10*10=10000

所以，再次使用乘積法則，結(jié)果在老計劃下存在不一樣北美有效電話號碼有

160*640*10000=1024000000同時在新計劃下存在不一樣電話號碼有

800*800*10000=6400000000第20頁Example8在下面代碼被執(zhí)行后k值是什么？Solution:

k初值為0。這個嵌套循環(huán)每執(zhí)行一次，k就加1.令Ti表示執(zhí)行第i個循環(huán)任務(wù)，那么循環(huán)執(zhí)行次數(shù)就是完成任務(wù)T1T2,…,Tm方法數(shù)。由乘積法則，這個嵌套循環(huán)執(zhí)行了n1*n2*…*nm次。所以k最終值是n1*n2*…*nm第21頁Example9計數(shù)有窮集子集用乘積法則證實一個有窮集S不一樣子集數(shù)是2|s|。solution：

設(shè)S是有窮集。按任意次序?qū)元素列成一個表?？紤]到在S子集和長為|S|二進(jìn)制之間存在著一對一對應(yīng)，即假如表第i個元素在這個子集里，即該子集對應(yīng)二進(jìn)制串第i位為1，不然為0.由乘積法則，存在著2|S|個長為|S|二進(jìn)制串。所以

|P(S)|=2|S|第22頁乘積法則也慣用集合語言描述以下：假如A1,A2,…,Am是有窮集，那么在這些集合笛卡爾積中元素數(shù)是每個集合元素數(shù)之積。為把這種表述何乘積法則聯(lián)絡(luò)起來，注意到在笛卡爾積中選一個元素任務(wù)時經(jīng)過在A1中選一個元素，A2中選一個元素,…來完成。由乘積法則得到

第23頁【example】Choosethreedifferentnumbersfromtheintegersbetween1to300suchthatthesumofthethreeintegerscanbedivisibleby3.Howmanythewaysarethere?在1到300中選三個不一樣數(shù)，并且這三個數(shù)之和能被3整除，問有多少種方式？第24頁Solution:A=

{x|1

x300,x(mod3)=1}

B=

{x|1

x300,x(mod3)=2}C=

{x|1

x300,x(mod3)=0}|A|

=|B|

=|C|

=100(1)AllofthethreenumbersarechosenformthesetAAllofthethreenumbersarechosenformthesetBAllofthethreenumbersarechosenformthesetCChoseonenumberformthesetA,B,C第25頁【Example】某種樣式運動服著色由底色和裝飾條紋顏色配成，而且底色和條紋色必須不一樣色。底色可選紅、藍(lán)、橙、黃，條紋色可選黑、白，則共有42=8種著色方案。若此例改成底色和條紋都用紅、藍(lán)、橙、黃四種顏色話，則，方案數(shù)就不是44=16，而只有43=12種。在乘法法則中要注意事件A和事件B相互獨立性。第26頁求和法則(TheSumRule)Definition

Ifafirsttaskcanbedoneinn1waysandasecondtaskinn2ways,andifthesetaskscannotbedoneatthesametime,thentherearen1+n2waystodoeithertask.定義：假如完成第一項任務(wù)有n1種方式，完成第二項任務(wù)有n2種方式，而且這些任務(wù)不能同時完成，那么完成第一或第二項任務(wù)有n1+n2種方法。第27頁使用集合語言，加法原理則能夠描述為：設(shè)有限集合A有m個元素，B有n個元素，且A與B不相交，則A與B并共有m+n個元素，即

|A∪B|=|A|+|B|IfAandBaredisjointsetsthen|A∪B|=|A|+|B|.求和法則只適合用于兩集合不相交情況。求和法則(TheSumRule)第28頁Example10

假定要選一個數(shù)學(xué)學(xué)院教師或數(shù)學(xué)專業(yè)學(xué)生作為校委會代表。假如有37位數(shù)學(xué)學(xué)院教師和83位數(shù)學(xué)專業(yè)學(xué)生，那么這個代表有多少種不一樣選擇？

求和法則應(yīng)用Solution:

完成第一個任務(wù)即選出一位數(shù)學(xué)學(xué)院教師，能夠有37種方式。完成第二項任務(wù)，選出一位數(shù)學(xué)專業(yè)學(xué)生有83種式。依據(jù)求和法則，挑選這個代表全部可能方式數(shù)為37+83=120第29頁【Example】Supposestatementlabels(語句標(biāo)號)inaprogramminglanguagemustbeasingleletterorasingledecimaldigit.Determinethenumberofstatementlabels.假設(shè)程序語言中語句標(biāo)號必須是單個字母或者是單個十進(jìn)制數(shù)字。確定語句標(biāo)號個數(shù)。Solution:

Sincealabelcannotbebothatthesametimethenumberoflabels=thenumberofletters+thenumberofdecimaldigits=26+10=36.

第30頁推廣求和法則Wecanextendthesumruletomorethantwotasks.把求和法則推廣到多于兩項任務(wù)情況。

SupposethatthetasksT1,

T2,…,Tmcanbedoneinn1,

n2,…,nm

ways,respectively,andnotwoofthesetaskscanbedoneatthesametime.Thenthenumberofwaystodooneofthesetasksisn1+

n2+…+nm.假定任務(wù)T1,T2,…,Tm

分別有n1,n2

，…，nm種完成方式，而且任何兩項任務(wù)都不能同時做，那么完成其中一項任務(wù)式數(shù)是

n1+n2+…+nm第31頁推廣求和法則使用集合語言描述以下：假如A1,A2,…,Am是不相交集合。令Ti是從Ai（i=1,2,…,m）種選取一個元素任務(wù)。有|Ai|種方式做Ti，因為任何兩個任務(wù)不可能同時做，依據(jù)求和法則，從其中某個集合選擇一個元素方式數(shù)，即在并集中元素數(shù)是使用數(shù)學(xué)歸納法可證實得到上面結(jié)論。推廣求和法則第32頁Example11

一個學(xué)生能夠從三個表中一個表選擇一個計算機課題。這三個表分別包含23，15，19個可能課題。那么課題選擇可能有多少種？solution：這個學(xué)生有23種方式從第一個表中選擇課題，有15種方式從第二個表中選擇課題，有19種方式從第三個表中選擇課題。所以，全部選擇課題方式數(shù)共有23+15+19=57第33頁Example12

在下面代碼被執(zhí)行后k值是什么？

第34頁solution：

k初值是0.這個代碼由m個不一樣循環(huán)組成，循環(huán)中每次執(zhí)行k都要加1，令Ti是執(zhí)行第i個循環(huán)任務(wù)。因為第i個循環(huán)被執(zhí)行ni次所以任務(wù)Ti能夠用ni種方式完成，而且任何兩個任務(wù)不能同時執(zhí)行，使用求和法則得到完成任務(wù)Ti（i=1,2,…,m）方式數(shù)是n1+n2+…+nm第35頁〖Example〗CountingthenumberofelementsinAA={length10bitstringswith0-streakoflengthexactly5}.

計算集合A中元素個數(shù)。A={含有連續(xù)5個0全部10位字符串}第36頁Solution:

SincethesetAcanbebreakupintothefollowingcase.

A1={000001****}A2={1000001***}

A3={*1000001**}A4={**1000001*}

A5={***1000001}A6={****100000}(*iseither0or1)Applythesumrule:|A|=|A1|

+|A2|

+|A3|

+|A4|

+|A5|+|A6|

第37頁ManycountingproblemscannotbesolvedusingjustthesumruleorjusttheproductRule.howevermanycomplicatedcountingproblemscanbesolvedusingbothoftheserules.許多計數(shù)問題不能僅僅使用求和法則或是乘積法則來求解。對于一些復(fù)雜計數(shù)問題可使用這兩種法則結(jié)合來處理。比較復(fù)雜計數(shù)問題第38頁Example13在計算機語言BASIC某個版本中，變量名字是含有一個或兩個字符符號串，其中大寫和小寫字母是不加區(qū)分（一個字符或者取自26個英文字母，或者取自10個數(shù)字）。另外，變量名必須以字母作為開始，而且必須和兩個字符組成用于程序設(shè)計5個保留字相區(qū)分。在BASIC這個版本中有多少個不一樣變量名？第39頁Solution：

令V等于在這個BASIC版本中不一樣變量名個數(shù)，V1是單字符變量名個數(shù)，V2是兩個字符變量名個數(shù)。那么由求和法則，V=V1+V2因為單字符變量名必須是字母，故V1=26，又依據(jù)乘積法則存在26*36個以字母打頭以字母數(shù)字結(jié)尾2位字符串。其中有5個不包含在內(nèi)，所以V2

=26*36-5=931.

從而在這個BASIC版本中存在不一樣變量名數(shù)為V=V1+V2=26+931=957第40頁Example14

計算機系統(tǒng)每個用戶有一個6到8個字符組成登錄密碼，其中每個字符是一個大寫字母或者數(shù)字，且每個密碼必須最少包含一個數(shù)字，問有多少可能密碼？第41頁Solution:

設(shè)P表示可能密碼總數(shù)，且P6，P7，P8分別表示6，7或8位可能密碼數(shù)。由求和法則P=P6+P7+P8。我們現(xiàn)在找P6，P7，P8，直接找P6是很困難,而找6個大寫字母和數(shù)字組成字符串?dāng)?shù)是輕易，其中包含那些沒有數(shù)字串在內(nèi)，然后減去沒有數(shù)字串?dāng)?shù)就得到P6,由乘積法則，6個字符串?dāng)?shù)是366，而沒有數(shù)字字符串?dāng)?shù)是266。所以，P6=366-266。類似能夠得到P7=367-267，P8=368-268.從而，P=P6+P7+P8第42頁Example15計數(shù)因特網(wǎng)網(wǎng)址在由計算機物理網(wǎng)絡(luò)互連而組成因特網(wǎng)中，每臺計算機被分配一個因特網(wǎng)地址。當(dāng)前正在使用因特網(wǎng)協(xié)議版本（IPv4）中，一個地址是一個32位二進(jìn)制串。它以網(wǎng)絡(luò)標(biāo)識開始，后面跟隨者主機標(biāo)識，該標(biāo)識把一個計算機認(rèn)定為某個指定網(wǎng)絡(luò)組員。依據(jù)網(wǎng)絡(luò)標(biāo)識和主機標(biāo)識位數(shù)不一樣，使用3種地址形式。用于最大網(wǎng)絡(luò)A類地址，由0后跟7位網(wǎng)絡(luò)標(biāo)識和24位主機標(biāo)識組成。用于中等規(guī)模網(wǎng)絡(luò)B類地址，由10后跟14位網(wǎng)絡(luò)標(biāo)識和16位主機標(biāo)識組成。用于最小網(wǎng)絡(luò)C類地址，由110后跟21位網(wǎng)絡(luò)標(biāo)識和8位主機標(biāo)識組成.第43頁

因為特定用途，對地址有著一些限制：1111111在A類網(wǎng)絡(luò)網(wǎng)絡(luò)標(biāo)識中是無效，全0和全1組成主機標(biāo)識對任何網(wǎng)絡(luò)都是無效。因特網(wǎng)上一臺計算機有一個A類地址、B類地址或C類地址。下列圖顯示了IPv4編址。問因特網(wǎng)上計算機有多少不一樣有效IPv4地址？第44頁Solution：

令x是因特網(wǎng)上計算機有效地址數(shù)，xA、xB和xC分別表示A類、B類和C類有效地址數(shù)。由求和法則x=xA+xB+xC

為了找到xA,因為1111111是無效，故存在A類網(wǎng)絡(luò)標(biāo)識數(shù)為27-1=127對于每一個網(wǎng)絡(luò)標(biāo)識，存在224-2個主機標(biāo)識，這是因為全0和全1組成主機標(biāo)識是無效。所以，xA=127*（224-2）=2130706178第45頁

為了找到xB和xC，首先注意到存在214個B類網(wǎng)絡(luò)標(biāo)識和221個C類網(wǎng)絡(luò)標(biāo)識。對每個B類網(wǎng)絡(luò)標(biāo)識存在主機標(biāo)識數(shù)為216-2=65534而對每個C類網(wǎng)絡(luò)標(biāo)識存在主機標(biāo)識為28-2=254這也是考慮到全0和全1組成主機標(biāo)識是無效。因而，xB=1073709056，xC=532676608我們能夠得到IPv4有效地址總數(shù)是x=xA+xB+xC=3737091842

第46頁【Example】假設(shè)學(xué)號后四位是數(shù)字，那么這四位數(shù)字中有多少種情況是以4或5開頭？Solution:

可將以4開頭情況和以5開頭情況分開考慮，而且這兩種情況并沒有交集。首先計算以4開頭可能情況數(shù)。第一個數(shù)字我們必須選擇4，所以只有一個情況，接下來3個數(shù)字，每一個數(shù)字都有10種可能選擇情況。所以，依據(jù)法則全部可能情況共有

1×10×10×10=1000同理我們也能夠得出以5開頭4位數(shù)可能情況也有1000種。依據(jù)求和法則，全部以4或5開頭可能情況數(shù)是1000+1000=第47頁【Example】HowmanylicenseplatescanbemadeusingeithertwoLettersfollowedbyfourdigitsortwodigitsfollowedbyfourletters?用2個字母后跟4個數(shù)字或者2個數(shù)字后跟4個字母可組成多少種車牌？Solution:

兩個字母后跟4個數(shù)字情況下，可能車牌數(shù)是26×26×10×10×10×10=6760000

兩個數(shù)字后跟4個字母情況下，可能車牌數(shù)是10×10×26×26×26×26=45697600全部可能不一樣車牌數(shù)共有6760000+45697600=52457600第48頁

【Example】

1)求小于10000含1正整數(shù)個數(shù)2)求小于10000含0正整數(shù)個數(shù)另:全部4位數(shù)有10個,不含1四位數(shù)有9個,含14位數(shù)為兩個差:104

－94=3439個Solution：1)小于10000不含1正整數(shù)可看做4位數(shù),但0000除外.故有9×9×9×9－1＝6560個.含1有：9999－6560=3439個第49頁2)“含0”和“含1”不可直接套用。比如0019含1但不含0。在組合習(xí)題中有許多類似隱含要求，要尤其留神。不含01位數(shù)有9個，2位數(shù)有92

個，3位數(shù)有93

個，4位數(shù)有94

個，不含0且小于10000正整數(shù)有9+92+93+94=(95

－1)/(9－1)=7380個含0且小于10000正整數(shù)有9999－7380=2619第50頁計數(shù)基礎(chǔ)TheBasicofCounting

BasiccountingPrinciple基本計數(shù)原理Theinclusion-exclusionprinciples容斥原理TreeDiagrams樹圖第51頁容斥原理容斥原理是計數(shù)中慣用一個方法，先舉一例說明以下。

【Example】

求不超出20正整數(shù)中為2或3倍數(shù)數(shù)

分析：

因為不超出20數(shù)中2倍數(shù)有10個：2,4,6,8,10,12,14,16,18,20不超出20數(shù)中3倍數(shù)有6個：3,6,9,12,15,18但其中為2或3倍數(shù)數(shù)只有13個，而不是10+6=16即2,3,4,6,8,9,10,12,14,15,16,18,20其中6,12,18同時為2和3倍數(shù)。若計算10+6=16，則重復(fù)計算了一次6，12，18。第52頁我們知道加法原理是指時

若時，會怎樣？使用容斥原理可回答這個問題。如上面例子中把計算了兩次，所以

第53頁容斥原理容斥原理(TheInclusion-ExclusionPrinciple

)當(dāng)同時做兩個任務(wù)時，為了正確計數(shù)完成其中一個任務(wù)方式，我們先把完成每個任務(wù)方式數(shù)加起來，然后再減去完成公共任務(wù)方式數(shù)，這種技術(shù)即為容斥原理。whentotaskscanbedoneatthesametime,tocorrectlyCountthenumberofwaystodooneofthetwotasks,weaddThenumberofwaystodoeachofthetwotasksandthensubtractThenumberofwaystodobothtasksthistechniqueiscalled

thePrincipleofInclusion-Exclusion.

第54頁使用集合描述為：令A(yù)1和A2是集,T1是從A1選擇一個元素任務(wù)，T2是從A2選擇一個元素任務(wù)，完成T1或T2方式數(shù)是完成T1方式數(shù)與完成T2方式數(shù)之和減去同時完成T1，T2兩個任務(wù)方式數(shù)。容斥原理集合形式Wecanphrasethiscountingprincipleintermsofsets.LetA1,AndA2besets,LetT1bethetaskofchoosinganelementfromA1andT2thetaskofchoosinganelementfromA2,thenumberofwaystodoeitherT1orT2isthesumofthenumberofwaystodoT1andThenumberofwaystodoT2,minusthenumberofwaystodobothT1andT2.A1A1∩A2A2第55頁Example16以1開始或者以00結(jié)尾8位二進(jìn)制符號串有多少個？容斥原理應(yīng)用Solution：

令U=

{全部8位二進(jìn)制字符串}

A=

{以1開始全部8位二進(jìn)制字符串}

B=

{以00結(jié)尾全部8位二進(jìn)制字符串}={以1開始而且以00結(jié)尾全部8位二進(jìn)制字符串}由第56頁Example17離散數(shù)學(xué)班每個學(xué)生都是計算機科學(xué)或數(shù)學(xué)專業(yè)，或者是同時修這兩個專業(yè)。假如有38個事計算機科學(xué)專業(yè)（包含同時修兩個專業(yè)），23個事數(shù)學(xué)專業(yè)（包含同時修兩個專業(yè)），7個同時修兩個專業(yè)，那么這個班有多少個學(xué)生？第57頁Solution:

令：A為該班級中計算機科學(xué)專業(yè)學(xué)生集合；

B為該班級中數(shù)學(xué)專業(yè)學(xué)生集合；由題意

由容斥原理知

即這個班共有54人第58頁〖Example〗Howmanypositiveintegersnotexceeding100aredivisiblebyneither4nor6?不超出100正整數(shù)中既不能被4也不能被6整除個數(shù)有多少？Solution:

U=

{1,2,…,100}

A=

{x|xZ+,1

x100,4|x}

B=

{x|xZ+,1

x100,6|x}

第59頁計數(shù)基礎(chǔ)TheBasicofCounting

BasiccountingPrinciple基本計數(shù)原理Theinclusion-exclusionprinciples容斥原理TreeDiagrams樹圖第60頁612024/4/13樹圖TreeDiagrams樹圖

treeTousetreesincounting,weuseabranchtorepresenteachpossiblechoice.Werepresentthepossibleoutcomesbytheleaves.為了在計數(shù)中使用樹，我們用一個分支表示每個可能選擇，用樹葉表示可能結(jié)果。第61頁Example17有多少不含連續(xù)兩個14位二進(jìn)制串？使用樹圖處理計數(shù)問題由樹圖能夠看出存在8個不含連續(xù)兩個14位二進(jìn)制串。第62頁Example18Aplayoffbetweentwoteamsconsistsofatmostfivegameswinstheplayoff,inhowmanydifferentwayscantheplayoffoccur?在兩個隊（隊1和隊2）之間決賽之多由5次比賽組成，先勝3次隊贏得決賽權(quán)，決賽可能出現(xiàn)多少種不一樣方式？第63頁Solution:thereare

20differentwaysfortheplayofftooccur.我們看出存在20種不一樣決賽方式。注意：用樹圖求解計數(shù)問題時，抵達(dá)一片樹葉所作選擇個數(shù)可能是不一樣。第64頁Example19假設(shè)“我愛新澤西”T恤衫有5種不一樣規(guī)格：S、M、L、XL、XXL。又知道XL規(guī)格只有三種顏色，紅色、綠色和黑色，XXL規(guī)格只有綠色和黑色。除此之外，其它規(guī)格有四種顏色，白色、紅色、綠色和黑色。假如每種規(guī)格和顏色T恤最少有一件，一個紀(jì)念品商店必須庫存多少件不一樣T恤衫？第65頁Solution：以上樹圖給出了全部規(guī)格和顏色配對。從中可知這個紀(jì)念品商店老板必須庫存17件不一樣T恤衫。第66頁【Example】連丟五次銅板，其中沒有出現(xiàn)連續(xù)兩次正面結(jié)果有幾個？依據(jù)題意畫出樹圖結(jié)構(gòu)可知，共有13種可能結(jié)構(gòu)。思索：該題可否用乘積法則來處理？

第67頁

不可。若把整個過程分成5個任務(wù)，即第一次丟銅板，第二次丟銅板,…,第五次丟銅板。這5個任務(wù)之間不是相互獨立，下一次丟銅板結(jié)果要受上一次結(jié)果影響即每次任務(wù)不是相互獨立，故不能夠使用乘積法則來求解.第68頁【Example】畫出由X、Y、Z所組成長度為3字符串樹圖，其中Z后面不能夠跟著Y.解：由下面樹圖結(jié)構(gòu)可知，共有21種可能字符串。第69頁【練習(xí)】1.

Eachlockerinanairportislabeledwithanuppercaseletterfollowedbythreedigits.Howmanydifferentlabelsforlockersarethere?機場中儲物柜是使用一個大寫子母后跟3位數(shù)字來標(biāo)識，問一共能夠有多少個不一樣標(biāo)簽？第70頁2.

Howmanydifferentlicenseplatescanbemadeifeachlicenseplateconsistsofthreelettersfollowedbythreedigitsorfourlettersfollowedbytwodigits?假如每一個車牌號碼是由3個字母后跟3個數(shù)字或是4個字母后跟2個數(shù)字組成，問一共有多少不一樣車牌號？第71頁3.從5元素集合到含有下述元素數(shù)集合有多少一對一函數(shù)？

a）4b）5c）6d）74.在一個婚禮上攝影師從10個人中安排6個人在一排拍照，其中新娘和和新郎也在這10個人中，假如滿足下述條件，有多少種安排方式？

a）新娘必須在照片中

b）新娘和新郎必須在照片中

c）新娘和新郎恰好一個在照片中第72頁5.由8個英語字母可組成多少個串？

a）假如字母能夠重復(fù)且不包含元音字母

b）假如字母不能重復(fù)且不包含元音字母

c）假如字母能夠重復(fù)且以元音字母開始

d）假如字母不能重復(fù)且以元音字母開始

e）假如字母能夠重復(fù)且最少包含一個元音字母

f）假如字母能夠重復(fù)且包含恰好一個元音字母6.第73頁6.Agameconsistingofflippingacoinendswhentheplayergetstwoheadsinarow,twotailsinarow,orflipsthecoinfourtimes.(a)Drawatreediagramtoshowthewaysinwhichthegamecanend.(b)Inhowmanywayscanthegameend?進(jìn)行擲硬幣游戲，當(dāng)連續(xù)出現(xiàn)兩次正面（head）向上，反面（tail）向上或是一共擲四次硬幣時結(jié)束游戲，問（a）使用樹圖顯示游戲可能結(jié)束全部方式（b）比賽結(jié)束一共有多少方式？第74頁【解答】一共有26*10*10*10=26000個不一樣標(biāo)簽。一共有263*103+264*102=63273600個不一樣車牌號。a)從5元素集合到4元素集合不存在一對一函數(shù)。

b)從5元素到5元素集合存在5*4*3*2*1=120個一對一函數(shù)。

c)從5元素到6元素集合存在6*5*4*3*2=720個一對一函數(shù)。d)從5元素到7元素集合存在7*6*5*4*3=2520個一對一函數(shù).第75頁4.a)9*8*7*6*5=15120b)8*7*6*5=1680c)9*8*7*6*5*2=30240a)218b)21*20*19*18*17*16*15*14=8204716800c)5*26*25*24*23*22*21*20=16576560000d)5*25*24*23*22*21*20*19=12113640000e)268-218f)5*217第76頁6一共有8種結(jié)束方式第77頁學(xué)習(xí)內(nèi)容3.1TheBasicofCounting

計數(shù)基礎(chǔ)3.2ThePigeonholePrinciple鴿巢原理3.3PermutationsandCombinations排列與組合3.4RecurrenceandDivide-and-Conquer遞推與分治3.5GeneratingFunction生成函數(shù)3.6inclusion-exclusion容斥原理應(yīng)用第78頁鴿巢原理第79頁鴿巢原理IntroductionThepigeonholeprincipleandtheInclusion-Exclusionprinciplearetwobasiccountingprinciple.鴿巢原理與容斥原理是兩個基本計數(shù)原理。Thepigeonholeprinciplestatesthatiftherearemorepigeonsthanpigeonholes,thentheremustbeatleastonepigeonholewithatleasttwopigeonsinit.鴿巢原理表明鴿子多于鴿巢時，最少有一個鴿巢里面有兩個或兩個以上鴿子。ThepigeonholeprincipleisalsocalledtheDirichletdrawerprinciple.鴿巢原理也叫做狄利克萊抽屜原理。第80頁Proof:

SupposethatnoneofthekboxescontainsmorethanOneobject.ThenthetotalnumberofobjectswouldbeatmostkThisisacontradiction,sincethereareatleastk+1objects.假定k個盒子中沒有一個盒子包含物體多于1個，那么物體總數(shù)至多是k，這與最少有k+1個物體矛盾。鴿巢原理[

Theorem1]

ThePigeonholePrinciple

Ifk+1ormoreobjectsareplacedintokboxes,thenthereisAtleastOneboxcontainingtwoormoreoftheobjects.

假如K＋1個或更多物體放入K個盒子，那么最少有一個盒子包含了2個或更多物體。第81頁Theformalstatementofthepigeonholeprinciple

鴿巢原理普通形式IffisafunctionforAtoB,whereAandBarefinitesetswith,thenthereareelements,inA(≠)suchthat.假如f是A到B函數(shù)且A和B是有窮集，那么A一定存在兩個不相等元素a1和a2,有f(a1)=f(a2)成立。Proof:

，∈A，≠，

If,then.第82頁Example1Amonganygroupof367people,theremustbeatleasttwowiththesamebirthday.在一組367個人中一定最少有2個人有相同生日。Solution：Pigeons:the367

peoplePigeonholes:366days.Thedirectapplicationofthepigeonholeprinciple

鴿巢原理應(yīng)用第83頁Example2在27個英文單詞中一定最少有2個單詞以同一個字母開始。

Solution：

因為英文字母表中只有26個字母，所以由鴿巢原理可知在在27個英文單詞中一定最少有2個單詞以同一個字母開始

Pigeons:27

個英文單詞Pigeonholes:26個英文字母首個字母第84頁Example3假如考試給分時從0到100，班上必須有多少個學(xué)生才能確保在這次期末考試中最少有2個學(xué)生得到相同分?jǐn)?shù)？Solution：

期末考試有101個分?jǐn)?shù)。鴿巢原理證實在102個學(xué)生中一定最少有2個學(xué)生含有相同分?jǐn)?shù)。Pigeons:102個學(xué)生Pigeonholes：101個分?jǐn)?shù)第85頁Example4證實對每個整數(shù)n，存在一個數(shù)是n倍數(shù)，且在它十進(jìn)制表示中只出現(xiàn)0和1.Solution：

令n是正整數(shù)?？紤]n個整數(shù)1,11,111,…,11…1(在這個數(shù)表中，最終一個整數(shù)十進(jìn)制表示中含有n+1個1)。注意到當(dāng)一個整數(shù)被n整除時存在n個可能余數(shù)。因為這個數(shù)表中有n+1個整數(shù)，由鴿巢原理必有兩個整數(shù)在除以n時有相同余數(shù)。這兩個整數(shù)之差十進(jìn)制表示中只含有0和1，且它能被n整除。第86頁【Example】Showthatifthereare30studentsinaclass,thenatleast2havelastnamesthatbeginwiththesameletter.在一個有30個學(xué)生班級里，最少有2名學(xué)生姓是以同一個字母開頭。

Pigeons:the30

studentsPigeonholes:26letters.第87頁【example】Showthatamonganygroupoffive(notnecessarilyconsecutive)integers,therearetwowiththesameremainderwhendividedby4.證實在任意5個整數(shù)中（不一定是連續(xù)）有2個整數(shù)被4除余數(shù)相同。Proof:

當(dāng)一個整數(shù)被4整除時所得到余數(shù)有4種，分別為0,1,2,3由鴿巢原理可知假如有5個整數(shù)被4整除得到5個余數(shù)中最少有2個余數(shù)是相同。Pigeons:5Pigeonholes:4第88頁【example】最少需要多少個有序?qū)?a,b)才能確保存在兩個有序?qū)?a1,b1)和(a2,b2)，使得a1mod5=a2mod5而且

b1mod5=b2mod5。Proof:

有序?qū)?a,b)整除5能夠得到余數(shù)能夠組成以下25個整數(shù)對：(0,0),(0,1),(0,2),…,(4,4)這些數(shù)對其中沒有任何兩對是相同，由鴿巢原理可知最少需要26個有序?qū)r能夠確保存在兩個有序?qū)κ窍嗤?。?9頁[

Theorem2]

TheGeneralizedPigeonholePrinciple廣義鴿巢原理IfNobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingatleast

N/k

objects.假如N個物體放入k個盒子，那么最少有一個盒子包含了最少

N/k

個物體Phrasedintermsoffunctions:,If,then

theremustexistelementssuchthatTheGeneralizedPigeonholePrinciple

廣義鴿巢原理第90頁Example5在100個人中最少有個人生在同一個月廣義鴿巢原理應(yīng)用Example6假如有5個可能成績ABCDF，那么在一個離散數(shù)學(xué)班里最少要多少個學(xué)生才能確保最少6個學(xué)生得到相同分?jǐn)?shù)。第91頁Solution：

為確保最少有6個學(xué)生得到相同分?jǐn)?shù)，所需最少學(xué)生數(shù)是使得最小整數(shù)N。這么最小整數(shù)是N=5*5+1=26.假如只有25個學(xué)生，可能是沒5個學(xué)生得到一樣分?jǐn)?shù)，而沒有6個學(xué)生得到一樣分?jǐn)?shù)。于是，26是確保最少6個學(xué)生得到相同分?jǐn)?shù)所需最少學(xué)生數(shù)。第92頁Example7a）從一副標(biāo)準(zhǔn)52張牌中必須選多少張牌才能確保選出牌中最少有3張石一樣花色？b）必須選多少張牌才能確保選出牌中最少有3張是紅心？第93頁Solution：a）假設(shè)存在四個盒子保留四種花色牌，選中牌放在同種花色盒子里。使用廣義鴿巢原理。假如選了N張牌，那么最少有一個盒子含有最少張牌。所以假如，我們知道最少選了3張同花色牌。使得最小整數(shù)N是N=2*4+1=9所以9張牌就足夠了。注意到假如選8張牌，可能每種花色2張牌。因而必須選9張牌才能確保選出牌中最少3張是一樣花色。想到這一點一個好方法就是注意到選了8張牌以后沒有方法防止出現(xiàn)3張一樣花色牌。第94頁

b）我們不用廣義鴿巢原理回答這個問題。因為我們要確保存在3張紅心而不但僅是3張一樣花色牌。注意到在最壞情況下，選一張紅心以前可能選了全部黑桃、方塊、梅花，總共39張牌，下面選3張牌將都是紅心。所以為得到3張紅心，可能需要選42張牌。第95頁Example8為確保一個州2500萬個電話又不一樣10位電話號碼，所需地域代碼最小數(shù)是多少？（假定電話號碼是NXX-NXX-XXXX形式，其中前3位是地域代碼，N表示從2到9包含十進(jìn)制數(shù)字，X表示任何十進(jìn)制數(shù)字）。第96頁Solution：

有800萬個形如NXX-XXXX不一樣電話號碼。所以，由廣義鴿巢原理，在2500萬個電話號碼中，一定至少有

個一樣電話號碼。因而，最少需要4個地域代碼來確保全部10位號碼是不一樣。

第97頁Example9假設(shè)計算機科學(xué)試驗室有15臺工作站和10臺服務(wù)器。能夠用一條電纜直接把工作站連到服務(wù)器。同一時刻只有一條道服務(wù)器直接連接是有效。我們想確保在任何時刻任何一組不超出10個工作站能夠經(jīng)過直接連接同時訪問不一樣服務(wù)器。盡管我們能夠經(jīng)過將每臺工作站直接連接到每臺服務(wù)器（用150條連線）來做到這一點，到達(dá)這個目標(biāo)所需要最少直接連線數(shù)目是多少？第98頁Solution：

將工作站標(biāo)識為w1,w2,…,w3，服務(wù)器標(biāo)識為s1,s2,…,s10.假設(shè)對于k=1,2,…,10，我們連接wk到sk，而且w11，w12，w13，w14和w15種每個工作站都連接到全部10個服務(wù)器?？偣?0條直接連線。很清楚，在任何時刻任何一組不超出10個工作站能夠經(jīng)過直接連接同時訪問不一樣服務(wù)器。為看到這一點只要注意到下述事實：假如這個組包含工作站wj，那么wj能夠訪問服務(wù)器sj.對于組里每個工作站wk（k>11），一定存在不在組里工作站wj與之對應(yīng)所以wk能夠訪問服務(wù)器sj（這是因為存在多少個不在組里工作站wj，最少存在一樣多服務(wù)器sj能夠被其它工作站訪問）。第99頁

現(xiàn)在假設(shè)在工作站和服務(wù)器之間直接連線少于60條。那么某個服務(wù)器將至多連接工作站。（假如全部服務(wù)器連接到最少6個工作站，那么將存在最少6*10=60條直接連線）這意味著剩下9個服務(wù)器對于其它10個工作站同時訪問不一樣服務(wù)器就不夠用了所以，最少需要60條直接連線。從而得到答案是60.第100頁1012024/4/13【Example】

Abowlcontains10redballsand10blueballs.Oneselectsballsatrandomwithoutlookingatthem.一個碗里有10個紅球和10個藍(lán)球，任意地選擇幾個球。

Howmanyballsmustheselecttobesureofhavingatleastthreeballsofthesamecolor?選多少個球能確保最少有三個球是一樣顏色？

Howmanyballsmustheselecttobesureofhavingatleastthreeblueballs?選多少個球能確保最少有三個球是藍(lán)球？第101頁Solution:(1)pigeonholes:red,bluecolorpigeon:ballsBythegeneralizedpigeonholeprinciple,

5/2

=3Heneedstoselect13ballsAtmost10ofthemarered,soatleastthreeareblue.第102頁【Example】

Whatistheleastnumberofareacodesneededtoguaranteethatthe25millionphonesinastatehavedistinct10-digittelephonenumbers?為確保一個州2500萬個電話又不一樣10位電話號碼所需地域代碼最小數(shù)是多少？

—

—

N:2-9X:0-9areacodeNXXofficecodeNXXstationcodeXXXX第103頁ThenumberofphonenumbersoftheformNXX-XXXX8106=8,000,000Bythegeneralizedpigeonholeprinciple,among25millionphones,atleast

25/8

=4ofthemmusthaveidenticalnumbers.Hence,atleast4areacodesarerequiredto.第104頁【Example】

一個企業(yè)在倉庫存放產(chǎn)品，倉庫中存放柜由它們通道，在通道中位置和貨架來指定。整個倉庫有50個通道，每個通道85個水平位置每個位置5個貨架。企業(yè)產(chǎn)品數(shù)最少是多少才能使得在同一個存放柜中最少有2個產(chǎn)品？第105頁Solution：倉庫存放柜個數(shù)為50*85*5=21250個，為在同一個存放柜中最少有2個產(chǎn)品所需最少產(chǎn)品數(shù)是使得

最小整數(shù)N這么最小整數(shù)是N=21250*1+1=21251.

于是21251是使得同一個存放柜最少有2個產(chǎn)品最少產(chǎn)品數(shù).第106頁Example10Duringamonthwith30daysfootballgameswillbeheldatleast1gameaday,butatmost45games.Showthattheremustbeaperiodofsomenumberofconsecutivedaysduringwhichexactly14gamesmustbeplayed.

在30天一個月里，某棒球隊一天最少打一場比賽，但至多打45場。證實一定有連續(xù)若干天內(nèi)這個對恰好打了14場。Someelegantapplicationofthepigeonholeprinciple巧妙使用鴿巢原理

第107頁Solution：

令aj是在這個月第j天或第j天之前所打場數(shù)，則

是不一樣正整數(shù)一個遞增序列，其中，從而也是不一樣正整數(shù)一個遞增序列，其中

60個正整數(shù)全都小于等于59，所以由鴿巢原理有兩個正整數(shù)相等。因為整數(shù)aj,j=1,2,…,30都不相同，并aj+14,j=1,2,…,30也不相同，一定存在下標(biāo)i和j滿足ai=aj+14。這意味著從第j+1天到第i天恰好打了14場比賽。第108頁1092024/4/13Example11

證實在不超出2n任意n＋1個正整數(shù)中一定存在一個正整數(shù)被另一個正整數(shù)整除.

Solution：

把n+1個整數(shù)

a1,a2,…,an+1中每一個都寫成2冪與一個奇數(shù)乘積。換句話說，令，j=1,2,…,n+1,其中kj是非負(fù)整數(shù)qj是奇數(shù)。整數(shù)q1,q2,..,qn+1都是小于2n正整數(shù)。第109頁因為只存在n個小于2n正奇數(shù)，由鴿巢原理，q1,q2,..,qn+1中必有兩個相等。于是，存在整數(shù)i和j使得qi=qj。令qi和qj公共值是q，那么因而，若ki<ki,則ai整除aj：若ki>kj,則aj整除ai.第110頁

由前面鴿巢原理巧妙應(yīng)用我們能夠證實在不一樣整數(shù)序列中存在著確定長度遞增或遞減子序列。[

Theorem3]每個由n2＋1個不一樣實數(shù)組成序列都包含一個長為n+1嚴(yán)格遞增子序列或嚴(yán)格遞減子序列.

第111頁Proof：

令a1,a2,…,an2+1是n2