离散数学12省公开课一等奖全国示范课微课金奖课件

1离散数学DiscreteMathematics

汪荣贵教授合肥工业大学软件学院专用课件.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页在这一节我们将引入基本计数技术。这些方法是几乎全部计数技术基础。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.

假设一个过程由执行任务来完成。假如在完成任务之后用种方式来完成，那么完成这个过程有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在下面代码被执行后k值是什么？Solution:

k初值为0。这个嵌套循环每执行一次，k就加1.令Ti表示执行第i个循环任务，那么循环执行次数就是完成任务T1T2,…,Tm方法数。由乘积法则，这个嵌套循环执行了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

假定要选一个数学学院教师或数学专业学生作为校委会代表。假如有37位数学学院教师和83位数学专业学生，那么这个代表有多少种不一样选择？

求和法则应用Solution:

完成第一个任务即选出一位数学学院教师，能够有37种方式。完成第二项任务，选出一位数学专业学生有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

在下面代码被执行后k值是什么？

第34页solution：

k初值是0.这个代码由m个不一样循环组成，循环中每次执行k都要加1，令Ti是执行第i个循环任务。因为第i个循环被执行ni次所以任务Ti能够用ni种方式完成，而且任何两个任务不能同时执行，使用求和法则得到完成任务Ti（i=1,2,…,m）方式数是n1+n2+…+nm第35页〖Example〗CountingthenumberofelementsinAA={length10bitstringswith0-streakoflengthexactly5}.

计算集合A中元素个数。A={含有连续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某个版本中，变量名字是含有一个或两个字符符号串，其中大写和小写字母是不加区分（一个字符或者取自26个英文字母，或者取自10个数字）。另外，变量名必须以字母作为开始，而且必须和两个字符组成用于程序设计5个保留字相区分。在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位主机标识组成。用于中等规模网络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离散数学班每个学生都是计算机科学或数学专业，或者是同时修这两个专业。假如有38个事计算机科学专业（包含同时修两个专业），23个事数学专业（包含同时修两个专业），7个同时修两个专业，那么这个班有多少个学生？第57页Solution:

令：A为该班级中计算机科学专业学生集合；

B为该班级中数学专业学生集合；由题意

由容斥原理知

即这个班共有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有多少不含连续两个14位二进制串？使用树图处理计数问题由树图能够看出存在8个不含连续两个14位二进制串。第62页Example18Aplayoffbetweentwoteamsconsistsofatmostfivegameswinstheplayoff,inhowmanydifferentwayscantheplayoffoccur?在两个队（队1和队2）之间决赛之多由5次比赛组成，先胜3次队赢得决赛权，决赛可能出现多少种不一样方式？第63页Solution:thereare

20differentwaysfortheplayofftooccur.我们看出存在20种不一样决赛方式。注意：用树图求解计数问题时，抵达一片树叶所作选择个数可能是不一样。第64页Example19假设“我爱新泽西”T恤衫有5种不一样规格：S、M、L、XL、XXL。又知道XL规格只有三种颜色，红色、绿色和黑色，XXL规格只有绿色和黑色。除此之外，其它规格有四种颜色，白色、红色、绿色和黑色。假如每种规格和颜色T恤最少有一件，一个纪念品商店必须库存多少件不一样T恤衫？第65页Solution：以上树图给出了全部规格和颜色配对。从中可知这个纪念品商店老板必须库存17件不一样T恤衫。第66页【Example】连丢五次铜板，其中没有出现连续两次正面结果有几个？依据题意画出树图结构可知，共有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?进行掷硬币游戏，当连续出现两次正面（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个整数中（不一定是连续）有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个服务器。总共60条直接连线。很清楚，在任何时刻任何一组不超出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】

一个企业在仓库存放产品，仓库中存放柜由它们通道，在通道中位置和货架来指定。整个仓库有50个通道，每个通道85个水平位置每个位置5个货架。企业产品数最少是多少才能使得在同一个存放柜中最少有2个产品？第105页Solution：仓库存放柜个数为50*85*5=21250个，为在同一个存放柜中最少有2个产品所需最少产品数是使得

最小整数N这么最小整数是N=21250*1+1=21251.

于是21251是使得同一个存放柜最少有2个产品最少产品数.第106页Example10Duringamonthwith30daysfootballgameswillbeheldatleast1gameaday,butatmost45games.Showthattheremustbeaperiodofsomenumberofconsecutivedaysduringwhichexactly14gamesmustbeplayed.

在30天一个月里，某棒球队一天最少打一场比赛，但至多打45场。证实一定有连续若干天内这个对恰好打了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