离散数学第12章基本的组合计数公式

1、离 散 数 学第12章基本的组合计数公式25 七月 2022前言 组合数学是一个古老而又年轻的数学分支。 据传说，大禹在4000多年前就观察到神龟背上的幻方.前言幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486前言 贾宪 北宋数学家（约11世纪） 著有黄帝九章细草、算法斅古集斅 音“笑（“古算法导引”）都已失传。杨辉著详解九章算法（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（William Geoge

2、Horner，17861837）的方法（1819年）早770年。前言 1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。前言 组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。前言 组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。 但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。计数问题 计数问题是组合数学研究的主要问题之一。西班牙数学家Abraha

3、m ben Meir ibn Ezra(10921167)和法国数学家、哲学家、天文学家Levi ben Gerson(12881344)是排列与组合领域的两位早期研究者。另外，法国数学家Blaise Pascal还发明了一种机械计算器，这种计算器非常类似于20世纪40年代在数字电子计算机发明之前使用的一种机械计算器。同时，计数技术在数学和计算机科学中是很重要的，特别是在数据结构、算法分析与设计等后续课程中有非常重要的应用。 内容提要二项式定理与组合恒等式3多项式定理4加法法则与乘法法则1排列与组合2 本章学习要求重点掌握一般掌握了解11加法法则和原理法则2排列组合的计算 31 离散概率2 离

4、散概念的计 算公式及性质 2二项式定理与组合恒等式计算 组合问题的处理技巧一一对应数学归纳法上下界逼近一一对应与上下界逼近例1 在允许移动被切割的物体的情况下，最少用多少次切割可以将 333 的立方体切成 27个单位边长的立方体？ 中间的小立方体的6个面都是切割产生的面，每次切割至多产生一个面，至少需要6次切割。存在一种切割方法恰好用 6 次切割。例2 100个选手淘汰赛，为产生冠军至少需要多少轮比赛？ 方法1：50+25+12+6+3+2+1=99 方法2：比赛次数与淘汰人数之间存在一一对应，总计淘汰99人，因此至少需要99场比赛.加法法则与乘法法则开胃食品主食饮料种类价格(元)种类价格种类

5、价格玉米片(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表1 乘法法则 如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择， ，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：例1 Melissa病毒1990年，一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址本中找出前50个地址，并将病毒转发给他们。用户接收到这些被转发的附件并将字处

6、理文档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四次转发，共有多少个接收者？解 根据Melissa病毒的扩散原理，经过四次转发，共有50505050+505050+5050+ 50 +1= 6377551个接收者。例2在一幅数字图像中，若每个像素点用8位进行编码，问每个点有多少种不同的取值。分析 用8位进行编码可分为8个步骤：选择第一位，选择第二位， ，选择第八位。每一个位有两种选择，故根据乘法原理，8位编码共有22222222 = 28 = 256种取值。解 每个点有256( = 28) 种

7、不同的取值。 加法法则 假定X1, X2, , Xt均为集合，第i个集合Xi有ni个元素。如X1, X2, , Xt为两两不相交的集合，则可以从X1, X2, , Xt中选出的元素总数为：n1 + n2 + + nt。即集合X1X2Xt含有n1 + n2 + + nt个元素。例3由Alice、Ben、Connie、Dolph、Egbert和Francisco六个人组成的委员会，要选出一个主席、一个秘书和一个出纳员。（1）共有多少种选法？（2）若主席必须从Alice和Ben种选出，共有多少种选法？（3）若Egbert必须有职位，共有多少种选法？（4）若Dolph和Francisco都有职位，共有

8、多少种选法？例3 解（1）根据乘法法则，可能的选法种数为654= 120；（2）法一 根据题意，确定职位可分为3个步骤：确定主席有2种选择；主席选定后，秘书有5个人选；主席和秘书都选定后，出纳有4个人选。根据乘法法则，可能的选法种数为254 = 40；法二若Alice被选为主席，共有54 = 20种方法确定其他职位；若Ben为主席，同样有20种方法确定其他职位。由于两种选法得到的集合不相交，所以根据加法法则，共有2020 = 40种选法；例3 解(续)(3)法一 将确定职位分为3步：确定Egbert的职位,有3种方法；确定余下的较高职位人选, 有5个人选；确定最后一个职位的人选, 有4个人选。

9、根据乘法法则，共有354 = 60种选法；法二 根据(1)的结论，如果Egbert为主席，有20种方法确定余下的职位；若Egbert为秘书，有20种方法确定余下的职位；若Egbert为出纳员，也有20种方法确定余下的职位。由于三种选法得到的集合不相交，根据加法法则，共有202020 = 60种选法； 例3 解(续)（4）将给Dolph、Francisco和另一个人指定职位分为3步： 给Dolph指定职位，有3个职位可选； 给Francisco指定职位，有2个职位可选； 确定最后一个职位的人选，有4个人选。 根据乘法法则，共有324 = 24种选法。12.2 排列与组合 Zeke、Yung、Xe

10、no和Wilma四个候选人竞选同一职位。为了使选票上人名的次序不对投票者产生影响，有必要将每一种可能的人名次序打印在选票上。会有多少种不同的选票呢？ 从某个集合中有序的选取若干个元素的问题，称为排列问题。排列问题定义 （1） 从含n个不同元素的集合S中有序选取的r个元素叫做S的一个r -排列，不同的排列总数记为P(n, r)。如果r = n，则称这个排列为S的一个全排列，简称为S的排列。显然，当rn时，P(n, r) = 0。 例1从含3个不同元素的集合S中有序选取2个元素的排列总数。解 从含3个元素的不同集合S中有序选取2个元素的排列总数为6种。如果将这3个元素记为A、B和C，则6个排列为A

11、B, AC, BA, BC, CB, CA。定理对满足rn的正整数n和r有第r位第r-1位第3位第2位第1位nn-1n-2 n-(r-2)n-(r-1)注意：n个不同元素的排列共有n！种，其中 例2 A,B,C,D,E,F组成的排列中， （1）有多少含有DEF的子串？（2）三个字母D、E和F相连的有多少种？解 (1)将DEF看成一个对象，根据定理，满足条件的排列为A,B,C,DEF的全排列，共有4！=24种；（2）根据题意，满足该条件的排列分为两步：第一步确定D, E和F三个字母的全排列，有3！种排列，第二步将已排序的D, E和F看成一个整体，与A, B和C共4个元素构造出A, B, C, D

12、, E, F的全排列，有4！种排列。又根据乘法原理，满足条件的排列总数有3！4！=144。例36个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。解 6个人围坐在圆桌上，有120种不同的坐法。AEFBDCn个人围坐圆桌上，有(n-1)！种不同的坐法，我们称这种排列为环排列，从n个人中选出r个人为圆桌而坐称为环形r -排列。推论1含n个不同元素的集合的环形r-排列数Pc(n,r)是例4求满足下列条件的排列数。(1)10个男孩和5个女孩站成一排，无两个女孩相邻。(2)10个男孩和5个女孩站成一圆圈，无两个女孩相邻.解 (1)根据定理，10个男孩的全排列为10!，5个女孩插入到

13、10个男孩形成的11个空格中的插入方法数为P(11, 5)。根据乘法法则，10个男孩和5个女孩站成一排，没有两个女孩相邻的排列数为：10! P(11, 5) =（10!11!)/6! 。例4 解（续）（2） 根据定理，10个男孩站成一个圆圈的环排列数为9！，5个女孩插入到10男孩形成的10个空中的插入方法数为P(10, 5)。根据乘法原理，10个男孩和5个女孩站成一个圆圈，没有两个女孩相邻的排列法为： 9! P(10, 5) =（9!10!)/5!。 组合问题定义（2） 从含有n个不同元素的集合S中无序选取的r个元素叫做S的一个r -组合，不同的组合总数记为C(n, r)。当nr = 0时，规

14、定C(n, r) = 1。显然，当rn时，C(n, r) = 0。定理（2）对满足0 500; 200个是 5 的倍数， 40个是 25 的倍数（多加 40 个 5）， 8个是 125 的倍数（再多加 8 个 5）， 1个是 625 的倍数（再多加 1 个 5）i = 200+40+8+1 = 249. min(i, j)=249. 例2 求1000！的末尾有多少个0？基本计数公式的应用(续)例3 设A为 n 元集，问(1) A上的自反关系有多少个？(2) A上的反自反关系有多少个？(3) A上的对称关系有多少个？(4) A上的反对称关系有多少个？(5) A上既不对称也不是反对称 的关系有多少个？多重集的排列定理12.2 多重集S=n1a1, n2a2, , nkak，0 ni + (1) 全排列 r = n, n1 + n2 + + nk = n 证明：分步选取. 先放a1, 有C(n,n1) 种方法；再放a2, 有C(n n1,n2)种方法, . , 放ak,有C(nn1n2 nk1,nk) 种方法 (2) 若r ni 时，每个位置都有 k 种选法，得