组合数学课

2020/6/221组合数学2020/6/22组合数学-上海理工大学2教材组合数学（第四版），卢开澄卢华明著，清华大学出版社，2008本书共分8章，内容包括:排列与组合递推关系与母函数容斥原理与鸽巢原理Burnside引理与Polya定理区组设计线性规划编码简介组合算法简介考试时间：第九周课内形式：闭卷内容：上课例题为主成绩：平时+试卷成绩2020/6/22组合数学-上海理工大学32020/6/22组合数学-上海理工大学41666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。1646.7.1.—1716.11.14.）德国最重要的自然科学家、数学家、物理学家、历史学家和哲学家，一个举世罕见的科学天才，和牛顿同为微积分的创建人。•1664年1月，莱布尼茨完成了论文《论法学之艰难》，获哲学硕士学位。•1665年，莱布尼茨向莱比锡大学提交了博士论文《论身份》，1666年，审查委员会以他太年轻(年仅20岁)而拒绝授予他法学博士学位，1667年2月，阿尔特多夫大学授予他法学博士学位，还聘请他为法学教授。•1700年2月，他还被选为法国科学院院士。至此，当时全世界的四大科学院：英国皇家学会、法国科学院、罗马科学与数学科学院、柏林科学院都以莱布尼次作为核心成员。2020/6/22组合数学-上海理工大学5始创微积分高等数学上的众多成就计算机科学贡献1673年莱布尼茨特地到巴黎去制造了一个能进行加、减、乘、除及开方运算的计算机率先为计算机的设计，系统提出了二进制的运算法则，为计算机的现代发展奠定了坚实的基础丰硕的物理学成果充分地证明了“永动机是不可能”的观点哲学贡献单子论多才多艺1693年，莱布尼茨发表了一篇关于地球起源的文章，后来扩充为《原始地球》一书1677年，他写成《磷发现史》，对磷元素的性质和提取作了论述在气象学方面。他曾亲自组织人力进行过大气压和天气状况的观察1691年，莱布尼茨致信巴本，提出了蒸汽机的基本思想。1677年，莱布尼茨发表《通向一种普通文字》，以后他长时期致力于普遍文字思想的研究，对逻辑学、语言学做出了一定贡献。今天，人们公认他是世界语的先驱……………………2020/6/22组合数学-上海理工大学6组合数学概述组合数学（combinatorialmathematics），又称为离散数学。狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面问题。组合数学主要内容有组合计数、组合设计、组合矩阵、组合优化等。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学即算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。2020/6/22组合数学-上海理工大学7典型问题地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。任务分配问题（也称婚配问题）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？这是线性规划的问题。2020/6/22组合数学-上海理工大学8第一章排列与组合主要内容：一、排列与组合二、排列组合的生成算法三、组合意义的解释与应用举例2020/6/22组合数学-上海理工大学9一、排列与组合1.加法法则和乘法法则2.一一对应3.排列、组合4.圆周排列5.可重排列6.可重组合7.不相邻的组合2020/6/22组合数学-上海理工大学101.加法法则与乘法法则加法法则：设具有性质A的事件有m个，具有性质B的事件有n个，则具有性质A或B的事件有m+n个。若|A|=m,|B|=n,A∩B=,则|A∪B|=m+n。集合论语言：基本假设：性质A和性质B是无关的两类。2020/6/22组合数学-上海理工大学11例1某班选修企业管理的有18人，不选的有10人，则该班共有18+10=28人。例2假设要从北京坐飞机或者火车或者客车到上海。北京每天到达上海的飞机有5个航班，火车有7趟，客车有10趟，则每天由北京到达上海的旅行方式有5+7+10=22种。2020/6/22组合数学-上海理工大学12乘法法则：设具有性质A的事件有m个，具有性质B的事件有n个，则具有性质A和B的事件有mn个。若|A|=m,|B|=n,AB={(a,b)|aA,bB},则|AB|=mn。集合论语言：例3从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6条道路。加法法则：得到事件通过两种不同的方法。乘法法则：得到事件通过两个步骤。2020/6/22组合数学-上海理工大学13例4某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是44=16，而只有43=12种。2020/6/22组合数学-上海理工大学14例5(1)求小于10000的含1的正整数的个数；(2)求小于10000的含0的正整数的个数。(1)小于10000的不含1的正整数可看做4位数，但0000除外.故有9×9×9×9－1＝6560个。含1的有：9999－6560=3439个，另：全部4位数有104个，不含1的四位数有94个，含1的4位数为两个的差：104－94=3439个。2020/6/22组合数学-上海理工大学159999－7380=2619.9+9+9+9=(9－1)/(9－1)=73802345(2)“含0”和“含1”不可直接套用。0019含1但不含0。不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个。不含0小于10000的正整数有含0小于10000的正整数有2020/6/22组合数学-上海理工大学16(1)4×3×5＝60；(2)6×3＝18个位数有5种取法，千位数有8种取法，百位，十位各有8，7种取法。5×8×8×7＝2240。例6(1)n=73*112*134，求除尽n的数的个数；(2)n=73*142，求除尽n的数的个数；例7在1000和9999之间有多少每位上的数字均不同的奇数？40;20,3013117kjikji2020/6/22组合数学-上海理工大学17例8由a,b,c,d,e这5个字符，从中取6个构成字符串，要求(1)第1，6个字符必为子音字符b，c，d；(2)每个字符串必有两个母音字符a或e，且两个母音字符不相邻；(3)相邻的两个子音字符必不相同。求满足这样的条件的字符串的个数。由条件(1)，两个母音字符的位置不能在1，6，又由条件(2)，位置只能是(2,4),(2,5)和(3,5)之一。对每种格式，母音2×2，相邻子音3×2，其他两个子音3×3。因此答案为3×（2×2×3×2×3×3）=648。课堂练习2020/6/22组合数学-上海理工大学18abcde1b/c/d32a/e23b/c/d34a/22526b/c/d31b/c/d3223a/e24a/b/c35a/e26b/c/d31b/c/d32a/e23b/c/d3425a/e26b/c/d32020/6/22组合数学-上海理工大学19如我们说A集合有n个元素|A|=n，无非是建立了将A中元与[1,n]元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换。比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。2.一一对应“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。2020/6/22组合数学-上海理工大学20一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。例9在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？2020/6/22组合数学-上海理工大学21可以先计算对角线的个数，然后计算交点，但是存在在多边形内无交点的情形，比较复杂。可以考虑对应关系：多边形内交点to多边形四个顶点。可以证明这是一一映射（映射，单且满）。例10设凸n边形的任意三条对角线不共点，求对角线在多边形内交点的个数。2020/6/22组合数学-上海理工大学22一一对应例CnH2n+2是碳氢化合物,随着n的不同有下列不同的枝链：H|H—C—H|HH|H—C—H|H—C—H|HH|H—C—H|H—C—H|H—C—H|Hn=1甲烷n=2乙烷n=3丙烷2020/6/22组合数学-上海理工大学23一一对应H|H—C—H|H—C—H|H—C—H|H—C—H|HH|HH—CH||H—C—C—H||H—CH|HHn=4丁烷n=4异丁烷这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。构造化合物转化为图论问题，计算符合上述条件的树的数目，便可确定对应的不同化合物的数目2020/6/22组合数学-上海理工大学241.2一一对应例(Cayley定理)n个有标号的顶点的树的数目等于。两个顶点的树是唯一的。1－2n＝3时，数的数目3。1－2－3，1－3－2，2－1－3思路：n点树《一一对应》长度n-2序列n个字母的长度n-2序列的数目是2nn2nn2020/6/22组合数学-上海理工大学25一一对应⑦⑥||②—③—①—⑤—④41253逐个摘去标号最小的叶子，叶子的相邻顶点(不是叶子，是内点)形成一个序列，序列的长度为n-2例给定一棵有标号的树边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边)第一次摘掉②，③为②相邻的顶点，得到序列的第一个数3以此类推，消去23465，得到序列31551,长度为7－2=5，这是由树形成序列的过程。2020/6/22组合数学-上海理工大学26一一对应（复杂）由序列形成树的过程：由序列31551得到一个新序列111233455567•生成的过程是首先将31551排序得到11355，•因为序列31551的长度为5，•得到按升序排序的序列1234567，•序列的长度为5+2(即n)，•然后将11355按照大小插入到序列1234567中，•得到111233455567然后将两个序列排在一起315511112334555672020/6/22组合数学-上海理工大学27一一对应31551111233455567②—③15511113455567①—③55111455567④—⑤51115567⑤—⑥11157①—⑤17第一步推导：将上下两个序列同时去掉上行序列的第一个元素3(用蓝色表示)，去掉下行序列的第一个无重复的元素2(用红色表示)。生成一条边(②—③)。由上序列确定3（蓝色），再确定2（红色），在下序列最小无重元，于是生成边23。（并消除红蓝色点。）依此类推，减到下面剩最后两个元素，这两个元素形成最后一条边。最后形成树。（生成边的序列23，13，45，56，15，17）2020/6/22组合数学-上海理工大学281.2一一对应上述算法描述：给定序列b=(b1b2…bn-2)设a=(123…n-1n)将b的各位插入a,得a’,对()做操作。a’是2n-2个元的可重非减序列。ba’操作是从a’中去掉最小无重元，设为