离散数学课程组国家精品课程，国家双语教学示范课程离 散 数 学电子科技大学计算机科学与工程学院示 范 性 软 件 学 院2012年2月28日星期二离散数学课程组国家精品课程，国家双语教学示范课程78-22012/2/28第2章 计数问题计数问题是组合数学研究的主要问题之一。西班牙数 学家Abraham ben Meir ibn Ezra(10921167)和法国数学 家、哲学家、天文学家Levi ben Gerson(12881344)是排 列与组合领域的两位早期研究者。另外，法国数学家Blaise Pascal还发明了一种机械计 算器，这种计算器非常类似于20世纪40年代在数字电子计 算机发明之前使用的一种机械计算器。同时，计数技术在数学和计算机科学中是很重要的， 特别是在数据结构、算法分析与设计等后续课程 中有非常重要的应用。 离散数学课程组国家精品课程，国家双语教学示范课程78-32012/2/282.0 内容提要容斥原理与鸽笼原理3离散概率4乘法原理和加法原理1排列与组合2递归关系5离散数学课程组国家精品课程，国家双语教学示范课程78-42012/2/281.1 本章学习要求重点掌握一般掌握了解11乘法原理和加法 原理 2排列组合的计算 3利用容斥原理计 算有限集合的交 与并 31 离散概率 2 离散概念的计 算公式及性质 3 递归关系 4 递归关系的建 立和计算 21 鸽笼原理 2 鸽笼原理的简 单应用离散数学课程组国家精品课程，国家双语教学示范课程78-52012/2/28例2.2.1开胃食品主食饮料种类价格(元)种类价格种类价格玉米片(Co)2.15汉堡(H)3.25茶水(T)0.70色拉(Sa)1.90三明治(S)3.65牛奶(M)0.85鱼排(F)3.15可乐(C)0.75啤酒(B)0.75下表是某快餐店的菜单，问包含一种主食 和一种饮料的午餐有多少种不同的选择？ 表2.2.1离散数学课程组国家精品课程，国家双语教学示范课程78-62012/2/28解：将所以可能包含一种主食和一种饮料的午餐选 择列出：HT,HM,HC,HB;ST,SM,SC,SB;FT,FM,FC,FB。即为12种选择，即午餐可选择的种数恰为主食种类 与饮料种类的乘积，即3*4=12。例2.2.1(续）离散数学课程组国家精品课程，国家双语教学示范课程78-72012/2/282.2.1 乘法原理如果一些工作需要t步完成，第一步有n1种 不同的选择，第二步有n2种不同的选择， ， 第t步有nt种不同的选择，那么完成这项工作所 有可能的选择种数为：离散数学课程组国家精品课程，国家双语教学示范课程78-82012/2/28例2.2.2 用一个字母和一个不超过100的正整数给礼堂的座 位编号。那么不同编号的座位最多有多少？解 给一个座位编号的过程由两个任务组成，即从 26个字母中先选择一个字母分配给这个座位，然后 再从100个正整数中选择一个整数分配给它。乘积法则表明一个座位可以有：26*100=2600中不 同的编号方式。因此，不同编号的座位数至多是2600。离散数学课程组国家精品课程，国家双语教学示范课程78-92012/2/28某个计算机中心有32台微机，每台微机有24个端 口。问这个中心里有多少个不同的单机端口？解 选择一个端口的过程由两个任务组成。首先挑一台微机，然后在这台微机上挑一个端口。因为有32中方式选择微机，而不管选择了哪台微机 ，又有24种方式选择端口，由乘积法则：存在32*24=768个端口。例2.2.3 离散数学课程组国家精品课程，国家双语教学示范课程78-102012/2/28如果每个车牌由3个字母后跟3个数字的序列构成 （任何字母的序列都允许），那么有多少个不同的 有效车牌？解 对3个字母中的每个字母有26种选择，对3个数 字中的每个数字有10种选择。因此，由乘积法则总 共有26*26*26*10*10*10=17 576 000个可能的车 牌。例2.2.4 离散数学课程组国家精品课程，国家双语教学示范课程78-112012/2/28例2.2.5在一幅数字图像中，若每个像素点用8位进行编码 ，问每个点有多少种不同的取值。分析 用8位进行编码可分为8个步骤：选择第一位 ，选择第二位， ，选择第八位。每一个位有两 种选择，故根据乘法原理，8位编码共有 22222222 = 28 = 256种取值。解 每个点有256( = 28) 种不同的取值。 离散数学课程组国家精品课程，国家双语教学示范课程78-122012/2/28例2.2.6执行下面的代码以后k的值是什么？ K:=0 for i1:=1 to n1for i2:=1 to n2for im:=1 to nmk:=k+1解 k的初值是0。这个嵌套的循环每执行一次，k就加1。令Ti表示执行第i个循环的任务，那么循环执行的次数就是完成任务 T1,T2,Tm的方法数。因为对每个整数ij，1ijnj，第j个循环都执行一次，执行任务Tj（ j=1,2,m）的方法数就是nj。由乘法法则，这个嵌套的循环执行了n1n2nm次。因此k最后的值是n1n2nm。离散数学课程组国家精品课程，国家双语教学示范课程78-132012/2/282.2.2 加法原理假定X1, X2, , Xt均为集合，第i个集合Xi有ni 个元素。如X1, X2, , Xt为两两不相交的集合， 则可以从X1, X2, , Xt中选出的元素总数为：n1 + n2 + + nt。即集合即集合X X1 1XX2 2XXt t含有含有n n1 1+ n + n2 2+ + + n + nt t个元素。个元素。离散数学课程组国家精品课程，国家双语教学示范课程78-142012/2/28例2.2.7假定要选一位数学学院的教师或数学专业的学生作 为校委会的代表。如果有37位数学学院的教师和83 位数学专业的学生，那么这个代表有多少种不同的 选择？解 完成第一项任务，选一位数学学院的教师，可 以有37种方式；完成第二项任务，选一位数学专业的学生，有83中 方式。根据加法原理，结果有37+83=120种可能的方式来 挑选这个代表。离散数学课程组国家精品课程，国家双语教学示范课程78-152012/2/28例2.2.8一个学生可以从三个表中的一个表选择一个计算机 课题。这三个表分别包含23、15和19个可能的课 题。那么课题的选择可能有多少种？解 这个学生有23中方式从第一个表中的选择课题 ，有15种方式从第二个表中选择课题，有19种方式 从第三个表中选择课题。因此，共有23+15+19=57 种选择课题的方式。离散数学课程组国家精品课程，国家双语教学示范课程78-162012/2/28例2.2.9在下面的代码执行后k的值是什么？ K:=0 for i1:=1 to n1k:=k+1for i2:=1 to n2k:=k+1for im:=1 to nmk:=k+1 解 k的初值为0。这个代码块由m个不同的循环构成。 循环中的每次执行，k都要加1。 令Ti是执行第i个循环任务。 因为第i个循环被执行ni次，所以任务Ti可以用ni种方式完成。 由于任何两个任务不能同时执行，加法原理证明k的最后值。 即完成任务Ti(i=1,2,m)的方式数是n1+n2+nm。离散数学课程组国家精品课程，国家双语教学示范课程78-172012/2/28例2.2.10由Alice、Ben、Connie、Dolph、Egbert和 Francisco六个人组成的委员会，要选出一个主 席、一个秘书和一个出纳员。（1）共有多少种选法？（2）若主席必须从Alice和Ben种选出，共有多少 种选法？（3）若Egbert必须有职位，共有多少种选法？（4）若Dolph和Francisco都有职位，共有多少种 选法？离散数学课程组国家精品课程，国家双语教学示范课程78-182012/2/28例2.2.10 解（1）根据乘法原理，可能的选法种数为654= 120；（2）法一 根据题意，确定职位可分为3个步骤 ：确定主席有2种选择；主席选定后，秘书有5个人 选；主席和秘书都选定后，出纳有4个人选。根据 乘法原理，可能的选法种数为254 = 40；法二若Alice被选为主席，共有54 = 20种方法 确定其他职位；若Ben为主席，同样有20种方法确 定其他职位。由于两种选法得到的集合不相交，所 以根据加法原理，共有2020 = 40种选法；离散数学课程组国家精品课程，国家双语教学示范课程78-192012/2/28例2.2.10 解(续)(3)法一 将确定职位分为3步：确定Egbert的职 位,有3种方法；确定余下的较高职位人选, 有5个 人选；确定最后一个职位的人选, 有4个人选。根 据乘法原理，共有354 = 60种选法； 法二 根据(1)的结论，如果Egbert为主席，有20 种方法确定余下的职位；若Egbert为秘书，有20种 方法确定余下的职位；若Egbert为出纳员，也有20 种方法确定余下的职位。由于三种选法得到的集合 不相交，根据加法原理，共有 202020 = 60种选法； 离散数学课程组国家精品课程，国家双语教学示范课程78-202012/2/28例2.2.10 解(续)（4）将给Dolph、Francisco和另一个人指定职位 分为3步：给Dolph指定职位，有3个职位可选；给Francisco指定职位，有2个职位可选；确定最后一个职位的人选，有4个人选。根据乘法原理，共有324 = 24种选法。离散数学课程组国家精品课程，国家双语教学示范课程78-212012/2/282.3 排列与组合Zeke、Yung、Xeno和Wilma四个候选人竞选同一 职位。为了使选票上人名的次序不对投票者产生影 响，有必要将每一种可能的人名次序打印在选票 上。会有多少种不同的选票呢？ 从某个集合中有序的选取若干个元素的问题，称为 排列问题。离散数学课程组国家精品课程，国家双语教学示范课程78-222012/2/282.3.1 排列问题定义2.3.1 从含n个不同元素的集合S中有序选取 的r个元素叫做S的一个r-r-排列排列，不同的排列总数记 为P(n,r)。如果r=n，则称这个排列为S的一个全排全排 列列，简称为S的排列。显然，当当rnrn时，时，P(n,r) = 0P(n,r) = 0。 离散数学课程组国家精品课程，国家双语教学示范课程78-232012/2/28例2.3.1从含3个不同元素的集合S中有序选取2个元素的排 列总数。解 从含3个元素的不同集合S中有序选取2个元素 的排列总数为6种。如果将这3个元素记为A、B和C，则6个排列为AB, AC, BA, BC, CB, CA。离散数学课程组国家精品课程，国家双语教学示范课程78-242012/2/28定理2.3.1对满足rn的正整数n和r有第r位第r-1位第3位第2位第1位nn-1n-2 n-(r-2)n-(r-1)离散数学课程组国家精品课程，国家双语教学示范课程78-252012/2/28推论2.3.2n个不同元素的排列共有n！种，其中 10个不同元素的排列共有：10！=10*9*8*7*6*5*4*3*2*1=3 628 800种离散数学课程组国家精品课程，国家双语教学示范课程78-262012/2/28例2.3.2A,B,C,D,E,F组成的排列中， （1）有多少含有DEF的子串？（2）三个字母D、E和F相连的有多少种？解 (1)将DEF看成一个对象，根据推论2.3.2，满足条件 的排列为A,B,C,DEF的全排列，共有4！=24种；（2）根据题意，满足该条件的排列分为两步