《排列与组合》PPT课件

组合数学钱钱 江江北邮理学院组合数学就是按照一定的规则来安排一些离散个组合数学就是按照一定的规则来安排一些离散个体的有关问题。其内容包括：体的有关问题。其内容包括：1、计数与枚举计数与枚举2、容斥原理和鸽巢原理容斥原理和鸽巢原理3、组合设计组合设计4、组合算法和组合优化组合算法和组合优化5、图论图论 排列、组合、母函数、递推关系、容斥原理、排列、组合、母函数、递推关系、容斥原理、Burnside引理、引理、Polya定理定理第一章第一章 排列与组合排列与组合1.1 排列与组合排列与组合1.2 排列组合的生成算法排列组合的生成算法1.3 组合意义的解释与应用举例组合意义的解释与应用举例1.1 排列与组合排列与组合 加法法则和乘法法则加法法则和乘法法则 一一对应一一对应 排列、组合排列、组合 圆周排列圆周排列 可重排列可重排列 可重组合可重组合 不相邻的组合不相邻的组合1.加法法则与乘法法则加法法则与乘法法则加法法则：加法法则：设具有性质设具有性质A的事件有的事件有m个，具有性个，具有性质质B的事件有的事件有n个，则具有性质个，则具有性质A或或B的事件有的事件有m+n个。个。若若|A|=m,|B|=n,AB=,则则|AB|=m+n。集合论语言：集合论语言：基本假设：性质基本假设：性质A和性质和性质B是是无关无关的两类。的两类。例例1 某班选修企业管理的有某班选修企业管理的有18人，不选的有人，不选的有10人，人，则该班共有则该班共有 18+10=28 人。人。例例2 假设要从北京坐飞机或者火车或者客车到上假设要从北京坐飞机或者火车或者客车到上海。北京每天到达上海的飞机有海。北京每天到达上海的飞机有 5 个航班，火车个航班，火车有有 7 趟，客车有趟，客车有 10 趟，趟，则每天由北京到达上海的则每天由北京到达上海的旅行方式有旅行方式有 5+7+10=22 种。种。乘法法则：乘法法则：设具有性质设具有性质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 条道路。条道路。加法法则：得到事件通过加法法则：得到事件通过两种不同的方法两种不同的方法。乘法法则：得到事件通过乘法法则：得到事件通过两个步骤两个步骤。例例4 某种样式的运动服的着色由底色和装饰条纹的某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有黑、白，则共有 4 2=8 种着色方案。种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则方案数就不是色的话，则方案数就不是 4 4=16，而只有而只有 4 3=12 种。种。例例5 (1)求小于求小于10000的含的含1的正整数的个数；的正整数的个数；(2)求小于求小于10000的含的含0的正整数的个数。的正整数的个数。(1)小于小于10000的不含的不含1的正整数可看做的正整数可看做4位数，但位数，但 0000除外除外.故有故有999916560个。个。含含1的有：的有：99996560=3439个，个，另：全部另：全部4位数有位数有104个，不含个，不含1的四位数有的四位数有94个，个，含含1的的4位数为两个的差：位数为两个的差：10494=3439个。个。99997380=2619.9+9 +9 +9 =(9 1)/(91)=73802345(2)“含含0”和和“含含1”不可直接套用。不可直接套用。0019含含1但不含但不含0。不含不含0的的1位数有位数有9个，个，2位数有位数有92个，个，3位数有位数有93个个，4位数有位数有94个。个。不含不含0小于小于10000的正整数有的正整数有含含0小于小于10000的正整数有的正整数有(1)43560；(2)6318个位数有个位数有5种取法，千位数有种取法，千位数有8种取法，百位，十种取法，百位，十位各有位各有8，7种取法。种取法。58872240。例例6 (1)n=73*112*134，求除尽，求除尽n的数的个数；的数的个数；(2)n=73*142，求除尽，求除尽n的数的个数；的数的个数；例例7 在在1000和和9999之间有多少每位上的数字均不同之间有多少每位上的数字均不同的奇数？的奇数？例例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)之一。之一。对每种格式，母音对每种格式，母音22，相邻子音，相邻子音32，其他两个，其他两个子音子音33。因此答案为。因此答案为 3（223233）=648。如我们说如我们说A集合有集合有n个元素个元素|A|=n，无非是建立了将，无非是建立了将A中元与中元与1,n元一一对应的关系。元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换。在组合计数时往往借助于一一对应实现模型转换。比如要对比如要对A集合计数，但直接计数有困难，于是可集合计数，但直接计数有困难，于是可设法构造一易于计数的设法构造一易于计数的B，使得，使得A与与B一一对应一一对应。2.一一对应一一对应“一一对应一一对应”概念是一个在计数中极为基本的概概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。念。一一对应既是单射又是满射。一种常见的思路是按轮计场，费事。一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛另一种思路是淘汰的选手与比赛(按场计按场计)集一一对集一一对应。应。63场比赛。场比赛。例例9 在在64名选手之间进行淘汰赛名选手之间进行淘汰赛(即一场的比赛结即一场的比赛结果，失败者退出比赛果，失败者退出比赛),最后产生一名冠军，问要举最后产生一名冠军，问要举行几场比赛？行几场比赛？可以先计算对角线的个数，然后计算交点，但是可以先计算对角线的个数，然后计算交点，但是存在在多边形内无交点的情形，比较复杂存在在多边形内无交点的情形，比较复杂。可以考虑对应关系：多边形内交点可以考虑对应关系：多边形内交点to多边形四个顶多边形四个顶点。点。可以证明这是一一映射（映射，单且满）。可以证明这是一一映射（映射，单且满）。例例10 设凸设凸n边形的任意三条对角线不共点，求对边形的任意三条对角线不共点，求对角线在多边形内交点的个数。角线在多边形内交点的个数。排列的典型例子是取球模型：从排列的典型例子是取球模型：从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!/(n-r)!P(n,n)=n!例例11 由由5种颜色的星状物，种颜色的星状物，20种不同的花排列成如种不同的花排列成如下图案：两边是星状物，中间是下图案：两边是星状物，中间是3朵花，问共有多少朵花，问共有多少种这样的图案？种这样的图案？两边是星状物，从五种颜色的星状物中取两个的排两边是星状物，从五种颜色的星状物中取两个的排列的排列数是列的排列数是 P(5,2)=20。20种不同的花取种不同的花取3种排列的排列数是种排列的排列数是根据乘法法则得图案数为根据乘法法则得图案数为P(20,3)=20 19 18=6840。20 6840=136800。接上例，若接上例，若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单位的单位的3人排在一起，问有多少种人排在一起，问有多少种不同的排列方案。不同的排列方案。,1,2,3,4.iS i 例例13 试求由试求由1,3,5,7组成的所有不重复出现的整组成的所有不重复出现的整数的总和。数的总和。这样的整数可以是这样的整数可以是1位数位数,2位数位数,3位数位数,4位数，若设位数，若设是是 i 位数的总和，则位数的总和，则S=S1+S2+S3+S4,S1=1+3+5+7=16；于是我们只需要计算于是我们只需要计算Si即可。即可。S4=6(1+3+5+7)1000+6(1+3+5+7)100+6(1+3+5+7)10 +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；组合的个数用组合的个数用 C(n,r)表示。表示。或者用或者用 表示。表示。,nrnCr 定义：定义：从从 n 个不同元素中取个不同元素中取 r 个不重复的元素组个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从成一个子集，而不考虑其元素的顺序，称为从 n 个中取个中取 r 个的个的无重组合无重组合。C(n,r)=0，若，若n n,则则 N=0;12!.!knnnn；(2)若若r=n,则则 N=inrrNk；(3)若若r n,且对所有的且对所有的i,则则(4)若若r n,且存在且存在i,nir,则对则对 N 没有一般的求没有一般的求解公式，具体解法以后再说。解公式，具体解法以后再说。1212(,.,.,()(),)krijSaaarb bbbb iC k rjk r 允允许许重重复复的的是是指指从从中中取取 个个元元素素，允允许许重重复复 即即允允许许的的数数同同时时出出现现于于一一个个组组合合中中的的组组合合，其其全全体体记记为为，其其可可重重组组合合个个数数记记为为。12,.,kSaaa 定理：定理：从从 中取中取 r 个作可重个作可重的组合，其个数为的组合，其个数为C(k+r-1,r)。6.可重组合可重组合 r个相同的球个相同的球 /001001100 /k-1个相同的盒壁个相同的盒壁而后一问题又可转换为而后一问题又可转换为 r 个相同的球与个相同的球与 k-1 个相同个相同的盒壁的排列的问题。的盒壁的排列的问题。则所求计数为则所求计数为 C(k+r-1,r)。这个计数问题相当于这个计数问题相当于 r 个相同的球放入个相同的球放入 k 个不同个不同的盒子里，个数没有限制的计数。的盒子里，个数没有限制的计数。12.rbbb另证：另证：不妨假设不妨假设k个不同元素为个不同元素为1,2,k，设某一个，设某一个 r 可重组合为可重组合为b1,b2,br。由于允许重复，可以假。由于允许重复，可以假设设这相当于从这相当于从1到到 k+r-1中取中取 r 个不允许重复的组合。个不允许重复的组合。很容易验证，这是一个一一对应，从而定理成很容易验证，这是一个一一对应，从而定理成立。立。11221,1,1,1.iircb cbcbicckr 令令于于是是有有第二个证明可说一种第二个证明可说一种“拉伸压缩拉伸压缩”技巧。不可谓不技巧。不可谓不巧妙。但仍不如第一证明来的明快，由此可见巧妙。但仍不如第一证明来的明快，由此可见组合组合证明证明的功效。的功效。1122,.,(1,).kkiSn a nanaiknrSrC krr:设:设多多重重集集且且对对一一切切的的=1,2,.,有=1,2,.,有则则 的的组组合合数数是是推推论论12,.,(1,1).kSaaarkSrC rk:设:设多多重重集集且且则则中中每每个个元元素素至至少少取取一一个个的的组组合合推推数数是是论论任取一个所求的任取一个所求的 r 组合，从中拿走每个元素一个组合，从中拿走每个元素一个就得到就得到 S 的一个的一个 r-k 组合，反之组合，反之,对于对于 S 的一个的一个 r-k组合，加入元素组合，加入元素a1,a2,ak 就得到所求组合，所以就得到所求组合，所以其组合数即为其组合数即为 S 的的 r-k 可重组合数。可重组合数。112212,.,.,kkkSna nanannnn设设则则 S 的的 r-组合数组合数 N 满足：满足：(4)若若r n,且存在且存在i,ni n,则则 N=0;(2)若若r=n,则则 N=1;inr(3)若若r n,且对所有的且对所有的i,则则 N=C(k+r-1,r);典型模型：典型模型：定理：定理：线性方程线性方程的非负整数解的个数为的非负整数解的个数为 C(k+r-1,r)。12kxxxr取取 r 个无区别的球放进个无区别的球放进 k 个有标志的盒子，每个盒个有标志的盒子，每个盒子中的球的数目不加限制子中的球的数目不加限制,允许重复的组合数即允许重复的组合数即其方案数。其方案数。定理定理：从从1,2,n中取中取 r 个作不相邻的组合，其个作不相邻的组合，其个数为个数为 C(n-r+1,r)。7.不相邻的组合不相邻的组合不相邻的组合不相邻的组合是指从是指从1,2,n中取中取 r 个，不允许个，不允许重复且不存在相邻的数同时出现的组合。重复且不存在相邻的数同时出现的组合。设某一个不相邻组合为设某一个不相邻组合为b1,b2,br，可以假设，可以假设b1b2br,而且相邻两项至少相差而且相邻两项至少相差2。这相当于从这相当于从1到到 n-r+1中取中取 r 个不允许重复的组合。个不允许重复的组合。很容易验证，这是一个一一对应，从而定理成立。很容易验证，这是一个一一对应，从而定理成立。11221,1,1,1.iircb cbcbiccnr令令于于是是有有