離散數(shù)學(xué)12省公開(kāi)課一等獎(jiǎng)全國(guó)示范課微課金獎(jiǎng)?wù)n件

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

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

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

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

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

（2）TheSumRule

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

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

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

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

|S

T|=|S|

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

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

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

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

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

T2,…,Tm.IftaskTicanbedoneinniwaysaftertasksT1,

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

waystocarryouttheprocedure.

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

Howmanydifferentbitstringsoflength7?

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

0,1Solution:

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

CountingFunction

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

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

BSolution:Bytheproductruletherearen

n

n=nmfunctionsfromasetwithmelementstoonewithnelements第15頁(yè)Example6

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

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

n

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

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

—

—

areacodeNYXofficecodeNNXstationcodeXXXXN:2-9X:0–9Y:0/1老計(jì)劃新計(jì)劃

—

—

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

8*8*10=640由乘積法則得到格式為XXXX話(huà)機(jī)代碼有10*10*10*10=10000

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

160*640*10000=1024000000同時(shí)在新計(jì)劃下存在不一樣電話(huà)號(hào)碼有

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

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

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

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

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

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

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

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

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

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

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

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

SupposethatthetasksT1,

T2,…,Tmcanbedoneinn1,

n2,…,nm

ways,respectively,andnotwoofthesetaskscanbedoneatthesametime.Thenthenumberofwaystodooneofthesetasksisn1+

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

分別有n1,n2

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

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

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

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

第34頁(yè)solution：

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

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

SincethesetAcanbebreakupintothefollowingcase.

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

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

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

+|A2|

+|A3|

+|A4|

+|A5|+|A6|

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

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

=26*36-5=931.

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

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

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

因?yàn)樘囟ㄓ猛?，?duì)地址有著一些限制：1111111在A類(lèi)網(wǎng)絡(luò)網(wǎng)絡(luò)標(biāo)識(shí)中是無(wú)效，全0和全1組成主機(jī)標(biāo)識(shí)對(duì)任何網(wǎng)絡(luò)都是無(wú)效。因特網(wǎng)上一臺(tái)計(jì)算機(jī)有一個(gè)A類(lèi)地址、B類(lèi)地址或C類(lèi)地址。下列圖顯示了IPv4編址。問(wèn)因特網(wǎng)上計(jì)算機(jī)有多少不一樣有效IPv4地址？第44頁(yè)Solution：

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

為了找到xA,因?yàn)?111111是無(wú)效，故存在A類(lèi)網(wǎng)絡(luò)標(biāo)識(shí)數(shù)為27-1=127對(duì)于每一個(gè)網(wǎng)絡(luò)標(biāo)識(shí)，存在224-2個(gè)主機(jī)標(biāo)識(shí)，這是因?yàn)槿?和全1組成主機(jī)標(biāo)識(shí)是無(wú)效。所以，xA=127*（224-2）=2130706178第45頁(yè)

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

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

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

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

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

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

【Example】

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

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

個(gè)，3位數(shù)有93

個(gè)，4位數(shù)有94

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

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

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

【Example】

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

分析：

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

若時(shí)，會(huì)怎樣？使用容斥原理可回答這個(gè)問(wèn)題。如上面例子中把計(jì)算了兩次，所以

第53頁(yè)容斥原理容斥原理(TheInclusion-ExclusionPrinciple

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

thePrincipleofInclusion-Exclusion.

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

令U=

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

A=

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

B=

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

令：A為該班級(jí)中計(jì)算機(jī)科學(xué)專(zhuān)業(yè)學(xué)生集合；

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

由容斥原理知

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

U=

{1,2,…,100}

A=

{x|xZ+,1

x100,4|x}

B=

{x|xZ+,1

x100,6|x}

第59頁(yè)計(jì)數(shù)基礎(chǔ)TheBasicofCounting

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

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

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

第67頁(yè)

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

Eachlockerinanairportislabeledwithanuppercaseletterfollowedbythreedigits.Howmanydifferentlabelsforlockersarethere?機(jī)場(chǎng)中儲(chǔ)物柜是使用一個(gè)大寫(xiě)子母后跟3位數(shù)字來(lái)標(biāo)識(shí)，問(wèn)一共能夠有多少個(gè)不一樣標(biāo)簽？第70頁(yè)2.

Howmanydifferentlicenseplatescanbemadeifeachlicenseplateconsistsofthreelettersfollowedbythreedigitsorfourlettersfollowedbytwodigits?假如每一個(gè)車(chē)牌號(hào)碼是由3個(gè)字母后跟3個(gè)數(shù)字或是4個(gè)字母后跟2個(gè)數(shù)字組成，問(wèn)一共有多少不一樣車(chē)牌號(hào)？第71頁(yè)3.從5元素集合到含有下述元素?cái)?shù)集合有多少一對(duì)一函數(shù)？

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

a）新娘必須在照片中

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

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

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

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

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

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

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

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

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

c)從5元素到6元素集合存在6*5*4*3*2=720個(gè)一對(duì)一函數(shù)。d)從5元素到7元素集合存在7*6*5*4*3=2520個(gè)一對(duì)一函數(shù).第75頁(yè)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頁(yè)6一共有8種結(jié)束方式第77頁(yè)學(xué)習(xí)內(nèi)容3.1TheBasicofCounting

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

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

Theorem1]

ThePigeonholePrinciple

Ifk+1ormoreobjectsareplacedintokboxes,thenthereisAtleastOneboxcontainingtwoormoreoftheobjects.

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

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

，∈A，≠，

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

peoplePigeonholes:366days.Thedirectapplicationofthepigeonholeprinciple

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

Solution：

因?yàn)橛⑽淖帜副碇兄挥?6個(gè)字母，所以由鴿巢原理可知在在27個(gè)英文單詞中一定最少有2個(gè)單詞以同一個(gè)字母開(kāi)始

Pigeons:27

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

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

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

Pigeons:the30

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

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

b1mod5=b2mod5。Proof:

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

Theorem2]

TheGeneralizedPigeonholePrinciple廣義鴿巢原理IfNobjectsareplacedintokboxes,thenthereisatleastoneboxcontainingatleast

N/k

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

N/k

個(gè)物體Phrasedintermsoffunctions:,If,then

theremustexistelementssuchthatTheGeneralizedPigeonholePrinciple

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

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

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

有800萬(wàn)個(gè)形如NXX-XXXX不一樣電話(huà)號(hào)碼。所以，由廣義鴿巢原理，在2500萬(wàn)個(gè)電話(huà)號(hào)碼中，一定至少有

個(gè)一樣電話(huà)號(hào)碼。因而，最少需要4個(gè)地域代碼來(lái)確保全部10位號(hào)碼是不一樣。

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

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

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

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

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

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

5/2

=3Heneedstoselect13ballsAtmost10ofthemarered,soatleastthreeareblue.第102頁(yè)【Example】

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

—

—

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

25/8

=4ofthemmusthaveidenticalnumbers.Hence,atleast4areacodesarerequiredto.第104頁(yè)【Example】

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

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

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

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

第107頁(yè)Solution：

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

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

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

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

Solution：

把n+1個(gè)整數(shù)

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

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

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

第111頁(yè)P(yáng)roof：

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