12基本的组合计数公式.ppt

前言 组合数学是一个古老而又年轻的数学分支。 据传说，大禹在4000多年前就观察到神龟背上的幻方…... 前言 幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。 前言 贾宪 北宋数学家（约11世纪） 著有《黄帝九章细草》、《算法斅古集》斅 音“笑（“古算法导引”）都已失传。杨辉著《详解九章算法》（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（William Geoge Horner，1786—1837）的方法（1819年）早770年。 前言 1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。 前言 组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。 前言 组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。 但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。 计数问题 计数问题是组合数学研究的主要问题之一。西班牙数学家Abraham ben Meir ibn Ezra(1092～1167)和法国数学家、哲学家、天文学家Levi ben Gerson(1288～1344)是排列与组合领域的两位早期研究者。另外，法国数学家Blaise Pascal还发明了一种机械计算器，这种计算器非常类似于20世纪40年代在数字电子计算机发明之前使用的一种机械计算器。同时，计数技术在数学和计算机科学中是很重要的，特别是在《数据结构》、《算法分析与设计》等后续课程中有非常重要的应用。 内容提要 本章学习要求 组合问题的处理技巧 一一对应 数学归纳法 上下界逼近 一一对应与上下界逼近 12.1加法法则与乘法法则 乘法法则 如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，… ，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为： 例1 Melissa病毒 1990年，一种名叫Melissa的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址本中找出前50个地址，并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四次转发，共有多少个接收者？ 例2 在一幅数字图像中，若每个像素点用8位进行编码，问每个点有多少种不同的取值。 分析 用8位进行编码可分为8个步骤：选择第一位，选择第二位，… ，选择第八位。每一个位有两种选择，故根据乘法原理，8位编码共有2×2×2×2×2×2×2×2 = 28 = 256种取值。 解 每个点有256( = 28) 种不同的取值。 加法法则 假定X1, X2, …, Xt均为集合，第i个集合Xi有ni个元素。如{X1, X2, …, Xt}为两两不相交的集合，则可以从X1, X2, …, Xt中选出的元素总数为： n1 + n2 + … + nt。 例3 由Alice、Ben、Connie、Dolph、Egbert和Francisco六个人组成的委员会，要选出一个主席、一个秘书和一个出纳员。 （1）共有多少种选法？ （2）若主席必须从Alice和Ben种选出，共有多少种选法？ （3）若Egbert必须有职位，共有多少种选法？ （4）若Dolph和Francisco都有职位，共有多少种选法？ 例3 解 （1）根据乘法法则，可能的选法种数为6×5×4= 120； （2）[法一] 根据题意，确定职位可分为3个步骤：确定主席有2种选择；主席选定后，秘书有5个人选；主席和秘书都选定后，出纳有4个人选。根据乘法法则，可能的选法种数为2×5×4 = 40； [法二]若Alice被选为主席，共有5×4 = 20种方法确定其他职位；若Ben为主席，同样有20种方法确定其他职位。由于两种选法得到的集合不相交，所以根据加法法则，共有20＋20 = 40种选法； 例3 解(续) (3)[法一] 将确定职位分为3步：确定Egbert的职位,有3种方法；确定余下的较高职位人选, 有5个人选；确定最后一个职位的人选, 有4个人选。根据乘法法则，共有3×5×4 = 6