離散數學12省公開課一等獎全國示范課微課金獎課件

1離散數學DiscreteMathematics

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

第2頁學習內容3.1TheBasicofCounting計數基礎3.2ThePigeonholePrinciple鴿巢原理3.3PermutationsandCombinations排列與組合3.4RecurrenceandDivide-and-Conquer遞推與分治3.5GeneratingFunction生成函數3.6Inclusion-exclusionprinciples容斥原理第3頁計數基礎TheBasicofCounting

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

基本計數原理（1）TheProductRule乘積法則

（2）TheSumRule

求和法則基本計數原理（BasiccountingPrinciple

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

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

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

|S

T|=|S|

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

乘積法則應用舉例solution：

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

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

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

T2,…,Tm.IftaskTicanbedoneinniwaysaftertasksT1,

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

waystocarryouttheprocedure.

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

Howmanydifferentbitstringsoflength7?

有多少個不一樣7位二進制串？

0,1Solution:

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

CountingFunction

（計數函數）

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

BSolution:Bytheproductruletherearen

n

n=nmfunctionsfromasetwithmelementstoonewithnelements第15頁Example6

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

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

n

假設定義域中元素是a1a2…am

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

—

—

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

—

—

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

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

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

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)任務，那么循環(huán)執(zhí)行次數就是完成任務T1T2,…,Tm方法數。由乘積法則，這個嵌套循環(huán)執(zhí)行了n1*n2*…*nm次。所以k最終值是n1*n2*…*nm第21頁Example9計數有窮集子集用乘積法則證實一個有窮集S不一樣子集數是2|s|。solution：

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

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

第23頁【example】Choosethreedifferentnumbersfromtheintegersbetween1to300suchthatthesumofthethreeintegerscanbedivisibleby3.Howmanythewaysarethere?在1到300中選三個不一樣數，并且這三個數之和能被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】某種樣式運動服著色由底色和裝飾條紋顏色配成，而且底色和條紋色必須不一樣色。底色可選紅、藍、橙、黃，條紋色可選黑、白，則共有42=8種著色方案。若此例改成底色和條紋都用紅、藍、橙、黃四種顏色話，則，方案數就不是44=16，而只有43=12種。在乘法法則中要注意事件A和事件B相互獨立性。第26頁求和法則(TheSumRule)Definition

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

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

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

求和法則應用Solution:

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

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

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

SupposethatthetasksT1,

T2,…,Tmcanbedoneinn1,

n2,…,nm

ways,respectively,andnotwoofthesetaskscanbedoneatthesametime.Thenthenumberofwaystodooneofthesetasksisn1+

n2+…+nm.假定任務T1,T2,…,Tm

分別有n1,n2

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

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

一個學生能夠從三個表中一個表選擇一個計算機課題。這三個表分別包含23，15，19個可能課題。那么課題選擇可能有多少種？solution：這個學生有23種方式從第一個表中選擇課題，有15種方式從第二個表中選擇課題，有19種方式從第三個表中選擇課題。所以，全部選擇課題方式數共有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)任務。因為第i個循環(huán)被執(zhí)行ni次所以任務Ti能夠用ni種方式完成，而且任何兩個任務不能同時執(zhí)行，使用求和法則得到完成任務Ti（i=1,2,…,m）方式數是n1+n2+…+nm第35頁〖Example〗CountingthenumberofelementsinAA={length10bitstringswith0-streakoflengthexactly5}.

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

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

=26*36-5=931.

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

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

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

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

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

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

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

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

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

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

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

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

【Example】

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

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

個，3位數有93

個，4位數有94

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

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

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

【Example】

求不超出20正整數中為2或3倍數數

分析：

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

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

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

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

thePrincipleofInclusion-Exclusion.

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

令U=

{全部8位二進制字符串}

A=

{以1開始全部8位二進制字符串}

B=

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

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

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

由容斥原理知

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

U=

{1,2,…,100}

A=

{x|xZ+,1

x100,4|x}

B=

{x|xZ+,1

x100,6|x}

第59頁計數基礎TheBasicofCounting

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

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

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

第67頁

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

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

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

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

a）新娘必須在照片中

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

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

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

b）假如字母不能重復且不包含元音字母

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

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

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

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

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

c)從5元素到6元素集合存在6*5*4*3*2=720個一對一函數。d)從5元素到7元素集合存在7*6*5*4*3=2520個一對一函數.第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種結束方式第77頁學習內容3.1TheBasicofCounting

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

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

Theorem1]

ThePigeonholePrinciple

Ifk+1ormoreobjectsareplacedintokboxes,thenthereisAtleastOneboxcontainingtwoormoreoftheobjects.

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

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

，∈A，≠，

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

peoplePigeonholes:366days.Thedirectapplicationofthepigeonholeprinciple

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

Solution：

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

Pigeons:27

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

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

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

Pigeons:the30

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

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

b1mod5=b2mod5。Proof:

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

Theorem2]

TheGeneralizedPigeonholePrinciple廣義鴿巢原理IfNobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingatleast

N/k

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

N/k

個物體Phrasedintermsoffunctions:,If,then

theremustexistelementssuchthatTheGeneralizedPigeonholePrinciple

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

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

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

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

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

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

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

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

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

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

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

5/2

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

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

—

—

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

25/8

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

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

最小整數N這么最小整數是N=21250*1+1=21251.

于是21251是使得同一個存放柜最少有2個產品最少產品數.第106頁Example10Duringamonthwith30daysfootballgameswillbeheldatleast1gameaday,butatmost45games.Showthattheremustbeaperiodofsomenumberofconsecutivedaysduringwhichexactly14gamesmustbeplayed.

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

第107頁Solution：

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

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

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

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

Solution：

把n+1個整數

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

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

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

第111頁Proof：

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