《组合数学157页资料》由会员分享，可在线阅读，更多相关《组合数学157页资料（157页珍藏版）》请在金锄头文库上搜索。
1、组合数学,前言,组合数学是一个古老而又年轻的数学分支。 据传说，大禹在4000多年前就观察到神龟背上的幻方.,前言,幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。,5,1,9,3,7,2,4,8,6,前言,1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。,前言,组合数学是一个迷人的数学分支, 它起源于古代的游戏和美学鉴赏. 在现代科学技术的发展中, 人们会面临各种各样的组合数学问题. 组合数学在计算机科学中发挥着出极为重要的作用.,前言,组合数学的蓬勃发展则是在计算机问世和普
2、遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。,前言,组合数学的基本内容 组合数学关心的事情是要按照一定方式“配置”一组事物，主要考虑以下几方面的问题. 存在性： (2) 计数与分类：主要内容 (3) 构造算法：部分内容 (4) 算法优化：,前言,组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换。 但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。,前言,内容:高等数学(微积分,高等代数) 计算机数学(离散数学,组合数学) 意义:方法(用于编程), 素质(全面
3、,细致) 难点:方法的应用, 例题的题型和思路 教材:4版为主 讲课:听课为主, 课件较完整, 板书和说明 多种思路的分析，实例的直观理解,第一章 排列组合,1.1 加法法则与乘法法则,1.1 加法法则与乘法法则,假设：A和B是性质无关的两类事件。 加法法则 设事件A有m种产生方式， 事件B有n种产生方式，则事件A或B之一 有m+n种产生方式。 集合论语言： 若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。,1.1 加法法则与乘法法则, 例 某班选修企业管理的有 18 人，不选 的有 10 人，则该班共有 18 + 10 = 28 人。 例 北京每天直
4、达上海的客车有 5 次，客 机有 3 次， 则每天由北京直达上海的旅行 方式有 5 + 3 = 8 种。 例 某班选音乐的有 5人，选美术的有 7人，则至少选其中之一的 有7到12 人。,1.1 加法法则与乘法法则, 乘法法则 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有 m n种产生方式。 集合论语言： 若 |A| = m , |B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n 。,1.1 加法法则与乘法法则,例 某种字符串由两个字符组成，第一个字符可选自a，b，c，d，e，第二个字符可选自1，2，3，则这种字符串共有5 3 = 15 个
5、。 例 从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6 条道路。 例 某班选音乐的有 5人，选美术的有 7人，则同时选二者的 有0到5人。,1.1 加法法则与乘法法则,例 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42 = 8种着色方案。 若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是4 4 = 16， 而只有 4 3 = 12 种。 在乘法法则中要注意事件 A 和 事件 B 的相互独立性。,1.1 加法法则与乘法法则,例1-2 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的
6、正整数的个数 1)小于10000的不含1的正整数可看做4位数, 但0000除外. 故有999916560个. 含1的有：99996560=3439个 另: 全部4位数有 个,不含1的四位数有 个, 含1的4位数为两个的差: = 3439个 要点：含1的总数不含1的,1.1 加法法则与乘法法则,1)小于100的不含1的正整数可看做2位数, 但00除外. 故有99180个. (00,02,09, 20,22,29, 30,99) 含1的有：9980=19个 (01,11,21,91, 10,12,13,19),2)“含0”和“含1”不可直接套用。0019 含1但不含0。 直接套用, 含0的(?)有
7、：9980=19个 (00,10,20,90, 01,02,03,09) 其中:黄色的10个不是含0的. 因此,修改计算方法为: 不含0的1位数有9个，(1,2,9) 2位数有 个，(11,12,19, 21,99) 不含0小于100的正整数有81+9=90 含0小于100的正整数有9990=9个 (10,20,90),2)“含0”和“含1”不可直接套用。0019 含1但不含0。 在组合的习题中有许多类似的隐含规定，要特别留神。 不含0的1位数有9个，2位数有 个， 3位数有 个，4位数有 个 不含0小于10000的正整数有 含0小于10000的正整数有 99997380=2619个,1.1
8、加法法则与乘法法则,例1-3 长度为n的0，1符号串的数目为 设 由乘法规则 例如：n3，有8个 000,001,010,011,100,101,110,111,1.1 加法法则与乘法法则,例1-6 求除尽n的整数的个数. 除尽n的整数是 除尽n的整数的个数是,1.1 加法法则与乘法法则,例1-7 有a,b,c,d,e这5个字,从中取6个构成一组字符串,要求: (1)第1个和第6个必须是子音b,c,d; (2)每一字符串必有a,e两个母音,且a,e不相邻; (3)相邻两子音不允许相同. 求字符串数目. 解:格式(2,4): 子 母 子 母 子 子 格式(2,5): 子 母 子 子 母 子 格式
9、(3,5): 子 子 母 子 母 子,1.1 加法法则与乘法法则,解:格式(2,4): 子 母 子 母 子 子 格式(2,5): 子 母 子 子 母 子 格式(3,5): 子 子 母 子 母 子 格式(2,4): 格式(2,5): 格式(3,5): 由加法: 注意:条件(2)应改为:每个字符串恰好有不相邻的两位是母音a或e. 否则,理解为这两位分别为a和e.,1.1 加法法则与乘法法则,例1-8 有5本不同的日文书，7本不同的英文书，10本不同的中文书。 1)取2本不同文字的书； 2)取2本相同文字的书； 3)任取两本书,1.1 加法法则与乘法法则,解 注意：加法和乘法 1) 57+510+7
10、10=155; 2) C(5,2)+C(7,2)+C(10,2) =10+21+45=76; 3) 155+76=231= =C(5+7+10,2)=C(22,2) (注意:C(5,2)= 54/2=10. 是从5个取2个的组合，第一步5个选择，第二步4个选择，选a,b和b,a是同一组合),1.2 一一对应,“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。 如我们说A集合有n个元素 |A|=n，无非是建立了将A中元与1,n元一一对应的关系。 在组合计数时往往借助于一一对应实现模型转换。 比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对
11、应。,1.2 一一对应,例1-10 CnH2n+2是碳氢化合物,随着n的不同有下列不同的枝链：,H | H C H | H,H | H C H | H C H | H,H | H C H | H C H | H C H | H,n=1甲烷 n=2 乙烷 n=3 丙烷,1.2 一一对应,H | H C H | H C H | H C H | H C H | H,H | H H C H | | H C C H | | H C H | H H,n=4 丁烷 n=4异丁烷,这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树， 其中n个顶点关联的边数为4； 其它2n+2个顶点是叶子。 对于这样结构
12、的每一棵树，就对应有一种特定的化合物。,从而可以通过研究具有上述性质的 树找到不同的碳氢化合物CnH2n+2.,1.2 一一对应,例 在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？ 解 一种常见的思路是按轮计场，费事。 各轮场数502512632199 剩余选手数目:25, 13, 7, 4, 2, 1 另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。,1.2 一一对应,例 (Cayley定理) n个有标号的顶点的树的数目等于 。 两个顶点的树是唯一的。12 n3时，数的数目3。 123，132，213 思路：n点树一一对应
13、长度n-2序列 n个字母的长度n-2序列的数目是,1.2 一一对应, | | ,4 1 2 5 3,逐个摘去标号最小的叶子，叶子的相邻 顶点(不是叶子，是内点)形成一个序列， 序列的长度为n-2,例-12,给定一棵有标号的树,边上的标号表示摘去叶 的顺序。(摘去一个叶子 相应去掉一条边),第一次摘掉，为相邻的顶点， 得到序列的第一个数3 以此类推，消去23465，得到序列31551, 长度为72 = 5，这是由树形成序列的过程。,1.2 一一对应,由序列形成树的过程：,由序列31551得到一个新序列111233455567,生成的过程是首先将31551排序得到11355， 因为序列31551的
14、长度为5， 得到按升序排序的序列1234567， 序列的长度为5+2(即n)， 然后将11355按照大小插入到序列1234567中， 得到111233455567,然后将两个序列排在一起,31551 111233455567,1.2 一一对应,31551 111233455567,1551 1113455567,551 11455567,51 115567,1 1157,17,第一步推导：将上下两个序列同时去掉上 行序列的第一个元素3(用黄色表示)，去掉 下行序列的第一个无重复的元素2(用红色 表示)。生成一条边()。,由上序列确定3（黄色）， 再确定2（红色），在下序列最小无重元， 于是生成
15、边23。（并消除红黄色点。） 依此类推，减到下面剩最后两个元素，这 两个元素形成最后一条边。最后形成树。 （生成边的序列23，13，45，56，15，17）,1.2 一一对应,上述算法描述：,给定序列b=(b1b2bn-2) 设a=(123n-1 n)将b的 各位插入a,得a,对( )做操作。 a是2n-2个元的可重非减序列。,b a,操作是从a中去掉最小无重元，设为a1, 再从b和a中各去掉一个b中的第一个元素，设为b1， 则无序对(a1,b1)是一条边。 重复这一操作，得n-2条边，最后a中还剩一条边， 共 n-1条边，正好构成一个树。 b中每去掉一个元，a中去掉2个元。,1.2 一一对应,由算法知由树T得b=(b1b2bn-2) ， 反之，由b可得T。 即 f：Tb 是一一对应。 由序列确定的长边过程是不会形成回路的。 因任意长出的边 (u , v) 若属于某回路，此回路中必有一条最早生成的边，不妨就设为 (u , v) ，必须使u,v都在长出的边中重复出现，但照算法u,v之一从下行消失，不妨设为u，从而不可能再生成与u有关的边了，故由
