资源描述：
《离散数学课件-第3章-1,2.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、1离散数学DiscreteMathematics汪荣贵教授合肥工业大学软件学院专用课件2010.04第三章计数技术学习内容3.1TheBasicofCounting计数的基础3.2ThePigeonholePrinciple鸽巢原理3.3PermutationsandCombinations排列与组合3.4RecurrenceandDivide-and-Conquer递推与分治3.5GeneratingFunction生成函数3.6Inclusion-exclusionprinciples容斥原理计数的基础TheBasicofCountingBas
2、iccountingPrinciple基本的计数原理Theinclusion-exclusionprinciples容斥原理TreeDiagrams树图在这一节我们将引入基本的计数技术。这些方法是几乎所有计数技术的基础。BasicCountingPrinciples基本的计数原理（1）TheProductRule乘积法则（2）TheSumRule求和法则基本的计数原理（BasiccountingPrinciple）Example丢一个铜板和一个骰子共有多少可能的结果？铜板的正反面结果和骰子的点数结果互不影响，我们将整个工作分成丢铜板和丢骰子两个子工
3、作，先丢铜板时有2种可能，无论铜板是正面还是反面，掷出来的骰子点数都有6种可能，则可以知道总的可能结果有2*6=12种，如图所示，先掷骰子的情况下可能的情况数也是一样的，无论是先丢铜板还是先丢骰子都有结果2×6=6×2种结果。乘积法则(TheProductRule)DefinitionSupposethataprocedurecanbebrokendownintotwotasks,Iftherearemwaystodothefirsttaskandnwaystodothesecondtaskafterthefirsttaskhasbeendone,
4、thentherearem*nwaystodotheprocedure.乘积法则定义：如果完成一件事情需要两个步骤，第一步有m种方法，第二步有n种方法去实现，则完成该件事情共有n*m种方法。NOTE:当一个过程由独立的任务组成时使用乘积法则Phrasedintermsofsets(用集合语言描述)IfSandTarefinitesets,thenthenumberofelementsintheCartesianproductofthesesetsistheproductofthenumberofelementsineachset,namely。如果
5、S和T是有穷集，那么在这两个集合的笛卡尔积的元素数是这两个集合的元素数之积，即
6、ST
7、=
8、S
9、
10、T
11、乘积法则(TheProductRule)Example1用一个字母和一个不超过100的正整数给礼堂的座位编号。那么不同编号的座位最多有多少？乘积法则应用举例solution：整个过程分成两个任务组成，即从26个字母中先选出一个字母分配给这个座位，然后在从100个正整数中选择一个整数分配给它。由乘积法则表明一个座位可以有26*100=2600种不同的编号。Example2某个计算机中心有32台微机，每台微机有24个端口。问在这个中心里有多少个不同的
12、单机端口？solution：选择端口的过程包括两个部分：首先挑一台微机，可以有32种方式选择.其次不管选择了哪台微机又有24种方式选择端口.由乘积法则,存在的端口数为32*24=768【Example】从波士顿到底特律有4条汽车主干线，而从底特律到洛杉矶有6条。那么从波士顿经底特律到洛杉矶的汽车主干线有多少？Solution:整个任务可以分成两个部分：第一步从波士顿到底特律，可以有4种选择路线。第二步从底特律到洛杉矶有6种选择路线。根据乘积法则可知从波士顿经由底特律从到洛杉矶的可能的汽车主干线条数为4*6=24乘积法则的扩展Supposethata
13、procedureiscarriedoutbyperformingthetasksT1,T2,…,Tm.IftaskTicanbedoneinniwaysaftertasksT1,T2,…,andTi-1havebeendone,thentherearen1n2…nmwaystocarryouttheprocedure.假设一个过程由执行任务来完成。如果在完成任务之后用种方式来完成，那么完成这个过程有Theextendedversionoftheproductrule乘积法则的扩展Example3Howmanydifferentbitstrings
14、oflength7?有多少个不同的7位二进制串？0,1Solution:Theproductruleshow
