第一章 排列与组合.ppt

《第一章 排列与组合.ppt》由会员分享，可在线阅读，更多相关《第一章 排列与组合.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/4/91组合数学组合数学郝聚涛郝聚涛计算机系2023/4/9组合数学-上海理工大学2教材n组合数学（第四版），卢开澄 卢华明 著，清华大学出版社，2008n本书共分8章，内容包括:n排列与组合排列与组合n递推关系与母函数递推关系与母函数n容斥原理与鸽巢原理容斥原理与鸽巢原理nBurnside引理与引理与Polya定理定理n区组设计区组设计n线性规划线性规划n编码简介编码简介n组合算法简介组合算法简介 考试n时间：第九周课内n形式：闭卷n内容：上课例题为主n成绩：平时+试卷成绩2023/4/9组合数学-上海理工大学32023/4/9组合数学-上海理工大学4 1666年莱布尼兹所著组合学

2、论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。1646.7.1.1716.11.14.）德国最重要的自然科学家、数学家、物理学家、历史学家和哲学家，一个举世罕见的科学天才，和牛顿同为微积分的创建人。1664年1月，莱布尼茨完成了论文论法学之艰难，获哲学硕士学位。1665年，莱布尼茨向莱比锡大学提交了博士论文论身份，1666年，审查委员会以他太年轻(年仅20岁)而拒绝授予他法学博士学位，1667年2月，阿尔特多夫大学授予他法学博士学位，还聘请他为法学教授。1700年2月，他还被选为法国科学院院士。至此，当时全世界的四大科学院：英国皇家学会、法国科

3、学院、罗马科学与数学科学院、柏林科学院都以莱布尼次作为核心成员。2023/4/9组合数学-上海理工大学5n始创微积分始创微积分n高等数学上的众多成就高等数学上的众多成就 n计算机科学贡献计算机科学贡献n1673年莱布尼茨特地到巴黎去制造了一个能进行加、减、乘、年莱布尼茨特地到巴黎去制造了一个能进行加、减、乘、除及开方运算的计算机除及开方运算的计算机n率先为计算机的设计，系统提出了二进制的运算法则，为计率先为计算机的设计，系统提出了二进制的运算法则，为计算机的现代发展奠定了坚实的基础算机的现代发展奠定了坚实的基础 n丰硕的物理学成果丰硕的物理学成果 n充分地证明了充分地证明了“永动机是不可能永动

4、机是不可能”的观点的观点 n哲学贡献单子论哲学贡献单子论n多才多艺多才多艺 n1693年，莱布尼茨发表了一篇关于地球起源的文章，后来扩年，莱布尼茨发表了一篇关于地球起源的文章，后来扩充为充为原始地球原始地球一书一书 n1677年，他写成年，他写成磷发现史磷发现史，对磷元素的性质和提取作了，对磷元素的性质和提取作了论述论述 n在气象学方面。他曾亲自组织人力进行过大气压和天气状况在气象学方面。他曾亲自组织人力进行过大气压和天气状况的观察的观察 n1691年，莱布尼茨致信巴本，提出了蒸汽机的基本思想。年，莱布尼茨致信巴本，提出了蒸汽机的基本思想。n1677年，莱布尼茨发表年，莱布尼茨发表通向一种普通

5、文字通向一种普通文字，以后他长时，以后他长时期致力于普遍文字思想的研究，对逻辑学、语言学做出了一期致力于普遍文字思想的研究，对逻辑学、语言学做出了一定贡献。今天，人们公认他是世界语的先驱定贡献。今天，人们公认他是世界语的先驱 n2023/4/9组合数学-上海理工大学6组合数学概述n组合数学（combinatorial mathematics），又称为离散数学。狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面问题。n组合数学主要内容有组合计数、组合设计、组合矩阵、组合优化等。n组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学即算法的科学，而计算机所

6、处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。2023/4/9组合数学-上海理工大学7典型问题n地图着色问题地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论图论的问题。n船夫过河问题船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划线性规划的问题。n中国邮差问题中国邮差问题：由中国组合数学家管梅谷管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路

7、程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径欧拉路径算法求解。这也是图论图论的问题。n任务分配问题任务分配问题（也称婚配问题婚配问题）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？这是线性规划线性规划的问题。2023/4/9组合数学-上海理工大学8第一章第一章 排列与组合排列与组合主要内容：主要内容：一、一、排列与组合排列与组合二、二、排列组合的生成算法排列组合的生成算法三、三、组合意义的解释与应用举例

8、组合意义的解释与应用举例2023/4/9组合数学-上海理工大学9一、一、排列与组合排列与组合1.加法法则和乘法法则加法法则和乘法法则2.一一对应一一对应3.排列、组合排列、组合4.圆周排列圆周排列5.可重排列可重排列6.可重组合可重组合7.不相邻的组合不相邻的组合2023/4/9组合数学-上海理工大学101.加法法则与乘法法则加法法则与乘法法则加法法则：加法法则：设具有性质设具有性质A的事件有的事件有m个，具有性个，具有性质质B的事件有的事件有n个，则具有性质个，则具有性质A或或B的事件有的事件有m+n个个。若若|A|=m,|B|=n,AB=,则则|A B|=m+n。集合论语言：集合论语言：基

9、本假设：性质基本假设：性质A和性质和性质B是是无关无关的两类。的两类。2023/4/9组合数学-上海理工大学11例例1 某班选修企业管理的有某班选修企业管理的有18人，不选的有人，不选的有10人，人，则该班共有则该班共有 18+10=28 人。人。例例2 假设要从北京坐飞机或者火车或者客车到上假设要从北京坐飞机或者火车或者客车到上海。北京每天到达上海的飞机有海。北京每天到达上海的飞机有 5 个航班，火车个航班，火车有有 7 趟，客车有趟，客车有 10 趟，趟，则每天由北京到达上海的则每天由北京到达上海的旅行方式有旅行方式有 5+7+10=22 种。种。2023/4/9组合数学-上海理工大学12

10、乘法法则：乘法法则：设具有性质设具有性质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 条道路。条道路。加法法则：得到事件通过加法法则：得到事件通过两种不同的方法两种不同的方法。乘法法则：得到事件通过乘法法则：得到事件通过两个步骤两个步骤。2023/4/9组合数学-上海理工大学13例例4 某

11、种样式的运动服的着色由底色和装饰条纹的某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有黑、白，则共有 4 2=8 种着色方案。种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是色的话，则方案数就不是 4 4=16，而只有而只有 4 3=12 种。种。2023/4/9组合数学-上海理工大学14例例5 (1)求小于求小于10000的含的含1的正整数的个数；的正整数的个数；(2)求小于求小于10000的含的含0的正整数的个数。的正整数的

12、个数。(1)小于小于10000的不含的不含1的正整数可看做的正整数可看做4位数，但位数，但 0000除外除外.故有故有999916560个。个。含含1的有：的有：99996560=3439个，个，另：全部另：全部4位数有位数有104个，不含个，不含1的四位数有的四位数有94个，个，含含1的的4位数为两个的差：位数为两个的差：10494=3439个。个。2023/4/9组合数学-上海理工大学1599997380=2619.9+9 +9 +9 =(9 1)/(91)=73802345(2)“含含0”和和“含含1”不可直接套用。不可直接套用。0019含含1但不含但不含0。不含不含0的的1位数有位数有

13、9个，个，2位数有位数有92个，个，3位数有位数有93个，个，4位数有位数有94个。个。不含不含0小于小于10000的正整数有的正整数有含含0小于小于10000的正整数有的正整数有2023/4/9组合数学-上海理工大学16(1)43560；(2)6318个位数有个位数有5种取法，千位数有种取法，千位数有8种取法，百位，十位种取法，百位，十位各有各有8，7种取法。种取法。58872240。例例6 (1)n=73*112*134，求除尽，求除尽n的数的个数；的数的个数；(2)n=73*142，求除尽，求除尽n的数的个数；的数的个数；例例7 在在1000和和9999之间有多少每位上的数字均不同之间有

14、多少每位上的数字均不同的奇数？的奇数？2023/4/9组合数学-上海理工大学17例例8 由由a,b,c,d,e这这5个字符，从中取个字符，从中取6个构成字符串，个构成字符串，要求要求(1)第第1，6个字符必为子音字符个字符必为子音字符b，c，d；(2)每个字符串每个字符串必必有两个母音字符有两个母音字符a或或e，且两个母音，且两个母音字符不相邻；字符不相邻；(3)相邻的两个子音字符相邻的两个子音字符必必不相同。不相同。求满足这样的条件的字符串的个数。求满足这样的条件的字符串的个数。由条件由条件(1)，两个母音字符的位置不能在，两个母音字符的位置不能在1，6，又由条件又由条件(2)，位置只能是，

15、位置只能是(2,4),(2,5)和和(3,5)之一。之一。对每种格式，母音对每种格式，母音22，相邻子音，相邻子音32，其他两个，其他两个子音子音33。因此答案为。因此答案为 3（223233）=648。课堂练习2023/4/9组合数学-上海理工大学18abcde1b/c/d32a/e23b/c/d34a/22526b/c/d31b/c/d3223a/e24a/b/c35a/e26b/c/d31b/c/d32a/e23b/c/d3425a/e26b/c/d32023/4/9组合数学-上海理工大学19如我们说如我们说A集合有集合有n个元素个元素|A|=n，无非是建立了将，无非是建立了将A中元与中

16、元与1,n元一一对应的关系。元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换。在组合计数时往往借助于一一对应实现模型转换。比如要对比如要对A集合计数，但直接计数有困难，于是可集合计数，但直接计数有困难，于是可设法构造一易于计数的设法构造一易于计数的B，使得，使得A与与B一一对应一一对应。2.一一对应一一对应“一一对应一一对应”概念是一个在计数中极为基本的概概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。念。一一对应既是单射又是满射。2023/4/9组合数学-上海理工大学20一种常见的思路是按轮计场，费事。一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛另一种

17、思路是淘汰的选手与比赛(按场计按场计)集一一对集一一对应。应。99场比赛。场比赛。例例9 在在100名选手之间进行淘汰赛名选手之间进行淘汰赛(即一场的比赛即一场的比赛结果，失败者退出比赛结果，失败者退出比赛),最后产生一名冠军，问要最后产生一名冠军，问要举行几场比赛？举行几场比赛？2023/4/9组合数学-上海理工大学21可以先计算对角线的个数，然后计算交点，但是存可以先计算对角线的个数，然后计算交点，但是存在在多边形内无交点的情形，比较复杂在在多边形内无交点的情形，比较复杂。可以考虑对应关系：多边形内交点可以考虑对应关系：多边形内交点to多边形四个顶多边形四个顶点。点。可以证明这是一一映射（

18、映射，单且满）。可以证明这是一一映射（映射，单且满）。例例10 设凸设凸n边形的任意三条对角线不共点，求对边形的任意三条对角线不共点，求对角线在多边形内交点的个数。角线在多边形内交点的个数。2023/4/9组合数学-上海理工大学22 一一对应n例例 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|Hn=1甲烷 n=2 乙烷 n=3 丙烷2023/4/9组合数学-上海理工大学23 一一对应 H|H C H|H C H|H C H|H C H|H H|HH C H|H C C H|H C H|H

19、Hn=4 丁烷 n=4异丁烷这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。构造化合物转化为图论问题，计算符合上述条件的树的数目，便可确定对应的不同化合物的数目2023/4/9组合数学-上海理工大学241.2 一一对应n例例 (Cayley定理)n个有标号的顶点的树的数目等于 。n两个顶点的树是唯一的。12nn3时，数的数目3。123，132，213n思路：n点树一一对应长度n-2序列nn个字母的长度n-2序列的数目是2023/4/9组合数学-上海理工大学25 一一对应|41 2

20、5 3逐个摘去标号最小的叶子，叶子的相邻顶点(不是叶子，是内点)形成一个序列，序列的长度为n-2例例给定一棵有标号的树边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边)第一次摘掉，为相邻的顶点，得到序列的第一个数3 以此类推，消去23465，得到序列31551,长度为72=5，这是由树形成序列的过程。2023/4/9组合数学-上海理工大学26 一一对应（复杂）n由序列形成树的过程：由序列31551得到一个新序列111233455567生成的过程是首先将31551排序得到11355，因为序列31551的长度为5，得到按升序排序的序列1234567，序列的长度为5+2(即n)，然后将113

21、55按照大小插入到序列1234567中，得到111233455567然后将两个序列排在一起 315511112334555672023/4/9组合数学-上海理工大学27一一对应 31551111233455567 15511113455567 55111455567 51115567 11157 17第一步推导：将上下两个序列同时去掉上行序列的第一个元素3(用蓝色表示)，去掉下行序列的第一个无重复的元素2(用红色表示)。生成一条边()。由上序列确定3（蓝色），再确定2（红色），在下序列最小无重元，于是生成边23。（并消除红蓝色点。）依此类推，减到下面剩最后两个元素，这两个元素形成最后一条边。最

22、后形成树。（生成边的序列23，13，45，56，15，17）2023/4/9组合数学-上海理工大学281.2 一一对应n上述算法描述：给定序列b=(b1b2bn-2)设a=(123n-1 n)将b的各位插入a,得a,对()做操作。a是2n-2个元的可重非减序列。ba操作是从a中去掉最小无重元，设为a1,再从b和a中各去掉一个b中的第一个元素，设为b1，则无序对(a1,b1)是一条边。重复这一操作，得n-2条边，最后a中还剩一条边，共 n-1条边，正好构成一个树。b中每去掉一个元，a中去掉2个元。2023/4/9组合数学-上海理工大学291.2 一一对应n由算法知由树T得b=(b1b2bn-2)

23、，n反之，由b可得T。n即 f：Tb 是一一对应。n由序列确定的长边过程是不会形成回路的。n因任意长出的边(u,v)若属于某回路，此回路中必有一条最早生成的边，不妨就设为(u,v)，必须使u,v都在长出的边中重复出现，但照算法u,v之一从下行消失，不妨设为u，从而不可能再生成与u有关的边了，故由()得到的边必构成一个n个顶点的树。ba2023/4/9组合数学-上海理工大学30证明 2n3 1 5 5 1n1 2 3 4 5 6 7 第一个不出现在上面的数n2-3 3-1 4-5 6-5 5-1 1-7|2023/4/9组合数学-上海理工大学32排列的典型例子是取球模型：从排列的典型例子是取球模

24、型：从n个不同的球中个不同的球中,取取出出r个个,放入放入r个不同的盒子里，每盒个不同的盒子里，每盒1个。个。第第1个盒子有个盒子有n种选择种选择,第第2个有个有n-1种选择，种选择，第，第r个有个有n-r+1种选择。故由乘法法则有种选择。故由乘法法则有3.排列、组合排列、组合定义：定义：从从 n 个不同的元素中，取个不同的元素中，取 r 个不重复的元个不重复的元素，按次序排列，称为从素，按次序排列，称为从 n 个中取个中取 r 个的个的无重排无重排列列。排列的个数用。排列的个数用 P(n,r)表示。表示。当当 r=n 时称为时称为全排列全排列。P(n,r)=n(n-1)(n-r+1)=n!/

25、(n-r)!P(n,n)=n!2023/4/9组合数学-上海理工大学33例例11 由由5种颜色的星状物，种颜色的星状物，20种不同的花排列成如种不同的花排列成如下图案：两边是星状物，中间是下图案：两边是星状物，中间是3朵花，问共有多少朵花，问共有多少种这样的图案？种这样的图案？两边是星状物，从五种颜色的星状物中取两个的排两边是星状物，从五种颜色的星状物中取两个的排列的排列数是列的排列数是 P(5,2)=20。20种不同的花取种不同的花取3种排列的排列数是种排列的排列数是根据乘法法则得图案数为根据乘法法则得图案数为P(20,3)=20 19 18=6840。20 6840=136800。2023

26、/4/9组合数学-上海理工大学34接上例，若接上例，若A单位的单位的2人排在队伍两端，人排在队伍两端，B单位的单位的3人不能相邻，问有多少种不同的排列方案？人不能相邻，问有多少种不同的排列方案？(练习练习)B单位单位3人按一个元素参加排列，人按一个元素参加排列，P(8,8)P(3,3)。A单位的人排法固定后单位的人排法固定后A*A*A*A*A*A*A，B单位第单位第一人有一人有6种选择，第二人有种选择，第二人有5种，第三人有种，第三人有4种，因种，因此答案为此答案为P(7,7)654。例例12 A单位有单位有7名代表，名代表，B单位有单位有3位代表，排成位代表，排成一列合影要求一列合影要求B单

27、位的单位的3人排在一起人排在一起，问有多少种，问有多少种不同的排列方案。不同的排列方案。2023/4/9组合数学-上海理工大学35例例13 试求由试求由1,3,5,7组成的所有不重复出现的整组成的所有不重复出现的整数的总和。数的总和。这样的整数可以是这样的整数可以是1位数位数,2位数位数,3位数位数,4位数，若设位数，若设是是 i 位数的总和，则位数的总和，则S=S1+S2+S3+S4,S1=1+3+5+7=16；于是我们只需要计算于是我们只需要计算Si即可。即可。2023/4/9组合数学-上海理工大学36S4=6(1+3+5+7)1000+6(1+3+5+7)100+6(1+3+5+7)10

28、 +6(1+3+5+7)=96000+9600+960+96=106656；S=16+528+10656+106656=117856。S2=3(1+3+5+7)10+3(1+3+5+7)=480+48=528；S3=6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7)=9600+960+96=10656；2023/4/9组合数学-上海理工大学37组合的个数用组合的个数用 C(n,r)表示。表示。或者用或者用 表示。表示。定义：定义：从从 n 个不同元素中取个不同元素中取 r 个不重复的元素组个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从成一个子集，而不考虑其元素

29、的顺序，称为从 n 个中取个中取 r 个的个的无重组合无重组合。C(n,r)=0，若，若n r。2023/4/9组合数学-上海理工大学38故有故有C(n,r)r!=P(n,r)，C(n,r)=P(n,r)/r!，从从n个不同的球中个不同的球中,取出取出r个个,放入放入r个相同的盒子里个相同的盒子里,每盒每盒1个，这是从个，这是从n个中取个中取r个的组合的模型。个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有模型。每一个组合可有r!个标号方案。个标号方案。2023/4/9组合数学-上海理工大学39(2)C(5,2)+C(7,

30、2)+C(10,2)=10+21+45=76；(1)57+510+710=155;(3)155+76=231=C(5+7+10,2)。例例14 有有5本不同的日文书，本不同的日文书，7本不同的英文书，本不同的英文书，10本本不同的中文书。不同的中文书。(1)取取2本不同文字的书；本不同文字的书；(2)取取2本相同文字的书；本相同文字的书；(3)任取两本书。任取两本书。2023/4/9组合数学-上海理工大学40例例15 甲和乙两单位共甲和乙两单位共11个成员，其中甲单位个成员，其中甲单位7人，人，乙单位乙单位4人，拟从中组成一个人，拟从中组成一个5人小组：人小组：(1)要求包含乙单位恰好要求包含

31、乙单位恰好2人；人；(2)要求至少包含乙单位要求至少包含乙单位2人；人；(3)要求乙单位某一人与甲单位特定一人不能同时在要求乙单位某一人与甲单位特定一人不能同时在这个小组。这个小组。试求各有多少种方案。试求各有多少种方案。(1)C(4,2)C(7,3)；(2)C(4,2)C(7,3)+C(4,3)C(7,2)+C(4,4)C(7,1)；(3)C(10,5)+C(9,4)，或，或C(11,5)-C(9,3)。2023/4/9组合数学-上海理工大学41将将1,300分成分成3类：类：A=i|i1(mod 3)=1,4,7,298,B=i|i2(mod 3)=2,5,8,299,C=i|i3(mod

32、 3)=3,6,9,300。例例16 从从1,300中取中取3个不同的数，使这个不同的数，使这3个数的和个数的和能被能被3整除，有多少种方案？（整除，有多少种方案？（练习练习）要满足条件，有四种情形：要满足条件，有四种情形：1.3个数同属于个数同属于A;2.3个数同属于个数同属于B;3.3个数同属于个数同属于C;4.A,B,C各取一数。各取一数。故共有故共有3C(100,3)+1003=485100+1000000=1485100。2023/4/9组合数学-上海理工大学42解解1：a1选择其同伴有选择其同伴有7种可能，种可能，选定后选定后,余下余下6人中某一人选择其同伴只有人中某一人选择其同伴

33、只有5种可能，种可能，余下余下4人，其中某人，其中某1人有人有3种选择可能，种选择可能，在余下的在余下的2人只好配成一对，无法选择，人只好配成一对，无法选择，故共有故共有N=753=105。例例17 假定有假定有a1,a2,a3,a4,a5,a6,a7,a8这这8位成员，位成员，两两配对分成两两配对分成4组，试问有多少种方案？组，试问有多少种方案？（练习）（练习）2023/4/9组合数学-上海理工大学43解解2：分成：分成4组。第一组取法为组。第一组取法为C(8,2)，余下余下6人，第二组取法为人，第二组取法为C(6,2)，第三组取法为第三组取法为C(4,2)，剩下为第四组。剩下为第四组。但但

34、4组的顺序是重复的，因此答案为组的顺序是重复的，因此答案为 C(8,2)C(6,2)C(4,2)/P(4,4)=105。解解3：8人全排列有人全排列有P(8,8)。分成。分成4组。组。每组中每组中2人交换是重复的，重复数为人交换是重复的，重复数为2222，另外另外4组的顺序也是重复的，重复数为组的顺序也是重复的，重复数为P(4,4)，因此答案为因此答案为 P(8,8)/(2222P(4,4)=105。2023/4/9组合数学-上海理工大学44一个进站方案可以表示成：一个进站方案可以表示成：00011001010100，其中其中“0”表示车，表示车，“1”表示间隔。表示间隔。其中其中“0”是不同

35、元，是不同元，“1”是相同元。是相同元。给给“1”这这6个入口只用个入口只用5个间隔。个间隔。任意进站方案可表示成上面任意进站方案可表示成上面14个元素的一个排列。个元素的一个排列。例例18 某广场有某广场有6个入口，每个入口每次只能通过一个入口，每个入口每次只能通过一辆汽车，现有辆汽车，现有9辆车要开进广场，有多少种入场方辆车要开进广场，有多少种入场方案？案？2023/4/9组合数学-上海理工大学45解解2：在：在14个元的排列中先确定个元的排列中先确定“1”的位置，有的位置，有C(14,5)种选择，种选择，再确定车的位置，有再确定车的位置，有9！种选择。！种选择。故故 C(14,5)9!即

36、为所求。即为所求。解解3：实际上相当于：实际上相当于14个位置中选取个位置中选取9辆汽车的排列，辆汽车的排列，即为即为 P(14,9)。解解1：标号可产生：标号可产生5!个个14个元的全排列。个元的全排列。若设若设x为所求方案，则为所求方案，则 x 5!=14!。故故 x=14!/5!=726485760。2023/4/9组合数学-上海理工大学46注意到，每个交点只有两个对角线通过，对应了注意到，每个交点只有两个对角线通过，对应了4个个顶点所组成的一个组合，不同的交点对应的组合也顶点所组成的一个组合，不同的交点对应的组合也不相同。不相同。故共有故共有C(n,4)个交点。个交点。例例19 一个凸

37、一个凸 n 边形，它的任何边形，它的任何3条对角线都不交于条对角线都不交于同一点，问它的所有对角线在凸同一点，问它的所有对角线在凸 n 边形内部有多少边形内部有多少个交点。个交点。2023/4/9组合数学-上海理工大学47定义：定义：从从 n 个不同的数中不重复的取出取出个不同的数中不重复的取出取出 r 个沿个沿一圆周排列，称为一个一圆周排列，称为一个圆周排列圆周排列。所有的所有的r-圆周排列数记为圆周排列数记为 Q(n,r)（计算公式？计算公式？）。）。注意圆周排列与排列的不同之处在于圆周排列首尾注意圆周排列与排列的不同之处在于圆周排列首尾相邻。相邻。如如a、b、c、d的的4种不同排列种不同

38、排列 abcd,dabc,cdab,bcda,在圆周排列中都是一个排列。在圆周排列中都是一个排列。4.圆周排列圆周排列2023/4/9组合数学-上海理工大学48 12 4 3 1234 12 4 3 2341 12 4 3 3412 12 4 3 4123以以4个元素为例个元素为例Q(n,r)=P(n,r)/r,2rnQ(n,n)=(n-1)!从从 n 个中取个中取 r 个的圆周排列的排列数为：个的圆周排列的排列数为：2023/4/9组合数学-上海理工大学49若无要求，则为若无要求，则为Q(8,8)；若要求蓝色珠子一起，则为若要求蓝色珠子一起，则为Q(6,6)P(3,3)；若要求蓝色珠子不相邻

39、，则为若要求蓝色珠子不相邻，则为Q(5,5)543。例例20 5颗红珠子，颗红珠子，3颗蓝珠子装在圆板的四周，试问颗蓝珠子装在圆板的四周，试问有多少种方案？若要求蓝色珠子不相邻，又有多少有多少种方案？若要求蓝色珠子不相邻，又有多少种排列方案？蓝色珠子在一起呢？种排列方案？蓝色珠子在一起呢？2023/4/9组合数学-上海理工大学50例例21 5对夫妇出席一个宴会，围一圆桌坐下，试问对夫妇出席一个宴会，围一圆桌坐下，试问有几种不同的坐法？要求每对夫妇相邻又如何？有几种不同的坐法？要求每对夫妇相邻又如何？若无限制，则为若无限制，则为Q(10,10)；若要求相邻，则为若要求相邻，则为Q(5,5)222

40、22。2023/4/9组合数学-上海理工大学51选取的选取的 r 个元素叫做个元素叫做 S 的一个的一个r-(可重可重)排列排列。当。当 时也叫做时也叫做 S 的一个排列。的一个排列。定义：定义：从一个多重集从一个多重集 中有序中有序5.可重排列可重排列定义：多重集定义：多重集是指元素可以多次出现的集合，即是指元素可以多次出现的集合，即元素可以重复。我们把某个元素元素可以重复。我们把某个元素 ai 出现的次数出现的次数ni(ni=0,1,2,)叫做该元素的叫做该元素的重复数重复数。通常把含有通常把含有 k 种不同元素的多重集种不同元素的多重集 S 记作记作2023/4/9组合数学-上海理工大学

41、52定理：定理：设多重集设多重集 则则 S 的的r-(可重可重)排列数是排列数是 kr。推论：推论：设多重集设多重集 且对一切且对一切的的 i=1,2,k，有，有nir，则，则 S 的的r-(可重可重)排列数是排列数是 kr。2023/4/9组合数学-上海理工大学53所求的标志数是多重集所求的标志数是多重集2红旗，红旗，3黄旗黄旗的排列的排列数，故数，故 N=5!/(2!3!)=10。例例23 用两面红旗，三面黄旗依次悬挂在一根旗杆用两面红旗，三面黄旗依次悬挂在一根旗杆上，问可以组成多少种不同的标志上，问可以组成多少种不同的标志?例例22 求不多于求不多于4位数的二进制数的个数。位数的二进制数

42、的个数。2023/4/9组合数学-上海理工大学54定理：定理：从从 中取中取 r 个作可重个作可重的组合，其个数为的组合，其个数为C(k+r-1,r)。6.可重组合可重组合2023/4/9组合数学-上海理工大学55 r个相同的球个相同的球 /001001100 /k-1个相同的盒壁个相同的盒壁而后一问题又可转换为而后一问题又可转换为 r 个相同的球与个相同的球与 k-1 个相同个相同的盒壁的排列的问题。的盒壁的排列的问题。则所求计数为则所求计数为 C(k+r-1,r)。这个计数问题相当于这个计数问题相当于 r 个相同的球放入个相同的球放入 k 个不同个不同的盒子里，个数没有限制的计数。的盒子里

43、，个数没有限制的计数。2023/4/9组合数学-上海理工大学56另证：另证：不妨假设不妨假设k个不同元素为个不同元素为1,2,k，设某一个，设某一个 r 可可重组合为重组合为b1,b2,br。由于允许重复，可以假设。由于允许重复，可以假设这相当于从这相当于从1到到 k+r-1中取中取 r 个不允许重复的组合。个不允许重复的组合。很容易验证，这是一个一一对应，从而定理成立。很容易验证，这是一个一一对应，从而定理成立。2023/4/9组合数学-上海理工大学57任取一个所求的任取一个所求的 r 组合，从中拿走每个元素一个组合，从中拿走每个元素一个就得到就得到 S 的一个的一个 r-k 组合，反之组合

44、，反之,对于对于 S 的一个的一个 r-k组合，加入元素组合，加入元素a1,a2,ak 就得到所求组合，所以就得到所求组合，所以其组合数即为其组合数即为 S 的的 r-k 可重组合数。可重组合数。2023/4/9组合数学-上海理工大学58典型模型：典型模型：定理：定理：线性方程线性方程的非负整数解的个数为的非负整数解的个数为 C(k+r-1,r)。取取 r 个无区别的球放进个无区别的球放进 k 个有标志的盒子，每个盒个有标志的盒子，每个盒子中的球的数目不加限制子中的球的数目不加限制,允许重复的组合数即允许重复的组合数即其方案数。其方案数。n 有多少项？n4个无标志的球放进3个有标志的盒子x,y

45、,zn从3个元素可重复的取4个的组合数目。2023/4/9组合数学-上海理工大学60定理定理：从从1,2,n中取中取 r 个作不相邻的组合，其个作不相邻的组合，其个数为个数为 C(n-r+1,r)。7.不相邻的组合不相邻的组合不相邻的组合不相邻的组合是指从是指从1,2,n中取中取 r 个，不允许重个，不允许重复且不存在相邻的数同时出现的组合。复且不存在相邻的数同时出现的组合。设某一个不相邻组合为设某一个不相邻组合为b1,b2,br，可以假设，可以假设b1b2br,而且相邻两项至少相差而且相邻两项至少相差2。这相当于从这相当于从1到到 n-r+1中取中取 r 个不允许重复的组合。个不允许重复的组合。很容易验证，这是一个一一对应，从而定理成立。很容易验证，这是一个一一对应，从而定理成立。