组合数学讲义 排列组合幻灯片.ppt

《组合数学讲义 排列组合幻灯片.ppt》由会员分享，可在线阅读，更多相关《组合数学讲义 排列组合幻灯片.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、组合数学讲义 排列组合第1页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University2 2第二章：排列组合n加法法则、乘法法则n排列、组合n举例 n排列、组合生成n字典排序法n邻位互换法n注记 第2页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer S

2、cience and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University3 3基本计数原理n集合S的划分：n加法原理n若S划分为S1,S2,Sm,则n乘法原理nS为有序对(a,b)集合，其中a有p种选择，b有q种选择，则n注：乘法原理是加法原理的一个推论（可以证明）。第3页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDep

3、t of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University4 4举例n例1.两位数中，有多少两位互异且非零的数？nab为有序对(a,b)，n共9x8=72n例2.现有6个橘子，9个苹果，欲组成果篮。要求果篮非空，有多少种不同的可能？n橘子0,1,2,3,4,5,6n苹果0,1,2,3,4,5,6,7,8,9n不同组合7x10=70n除去(0,0)的情况，有69种可能第4页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Com

4、puter Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University5 5计数问题的类型n对元素的有序的摆放数或有序的选择数进行计数n没有重复如何元素n允许元素重复（但可能是有效次重复）n对元素的无序的摆放数或无序的选择数进行计数n没有重复如何元素n允许元素重复（但可能是有效次重复）第5页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science a

5、nd EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University6 6举例n例1.在1000和9999有多少具有不同数字的奇数？n有个、十、百、千4个位置可以选择n个位：1,3,5,7,9有5种选择n千位：剩下8种选择n十/百位：8种选择，剩下一位只有7种选择n共计5x8x8x7=2240种n选择顺序影响乘法原理的使用n例2.在0和10000之间整数恰好有一位数字是5？nSi是i 位数集合(i=1,2,3,4)n|S1|=1；|S2|=

6、17:个位是5有8种，十位是5有9种n|S3|=225:个位是5有8x9种，十位是5有8x9种，百位是5有9x9种；|S4|=2763第6页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University7 7排列、组合问题n n 定义定义定义定义 从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取

7、r个的无重无重排列。n排列的全体组成的集合用P(n,r)表示。排列的个数用P(n,r)表示。当r=n时称为全排列。n n 定义定义定义定义 从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合无重组合。n组合的全体组成的集合用C(n,r)表示，组合的个数用C(n,r)或 表示。第7页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong

8、University Shanghai Jiaotong University8 8组合vs.排列n从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，第r个有n-r+1种选择。故有P(n,r)=n(n-1)(n-r+1)有时也用nr记n(n-1)(n-r+1)n若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。n故有C(n,r)r!=P(n,r),第8页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dep

9、t of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University9 9例n问题：求1000!中的尾数有几个零？n分析：一个零对应一对因子2和5n1000以内5的倍数有200个n1000以内25的倍数有40个n1000以内125的倍数有8个n1000以内625的倍数有1个n所以，1000!中5的幂有200+40+8+1=249个n1000!中2的幂远多于249个n解：n1000!中有249个0

10、第9页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University1010树的数目n图论问题：对n个顶点v1,v2,vn用n-1条边连接起来，问有多少种方案？n例，给定一棵有标号 的树，边上的标号表 示摘去叶的顺序（摘 去一个叶子相应去掉一条边）n逐个摘去标号最小的叶子，叶子的相邻顶点形成一个序列，序列的长度为

11、n-2n第一次摘掉，为相邻的顶点，得到序列的第一个数3,以此类推，得到序列31551,长度为7-2=5,这是由树形成序列的过程。第10页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University1111n顶点树与n-2序列的对应n由序列形成树的过程：n给定序列31551（1）n从序列1234567（2）中找第

12、一个不在（1）出现的数“2”，建立边“（2,32,3）”n得到1551（1）及134567（2），类似得到边（3,13,1）n再得到551（1）及14567（2）依此类推得到边（4,54,5），（6,56,5），（7,1）n最后序列（2）中剩下的2个数构成最后的边（1,51,5）n这表明，n顶点树与n-2序列建立了1-1对应第11页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaoton

13、g University Shanghai Jiaotong University1212Cayley定理n定理：n个有标号的顶点的树的数目等于nn-2n证明：由1-1对应关系知nn个顶点树的数目序列b1,b2,bn-2(0b=n)的数目n相应序列的数目为nn-2n注：一个问题与另一个问题1-1对应，则可将一个问题转化为另一个问题来处理。在处理组合计数问题时，常常通过问题的1-1对应实现模型的转换，以便于问题的求解。第12页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Co

14、mputer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University1313生成排列n问题：从已知排列出发，生成新的排列n目的：提高效率，减少开销nn个元素的排列的个数太多，（Stirling公式）n任务：寻找好的算法n序数法n如十进制、二进制，或递增、递减进制n字典序法n123,132,213,231,312,321第13页，共34页，编辑于2022年，星期一字典序法举例求83964 47521的下一个排列7 5 2 1 747 42 2 41 1 在后缀7521中找出比4大的数7 5

15、找出其中比4大的最小数 5 5 4、5 对换 8396 7 2154后缀变为7421 将此后缀翻转 12 4 7接上前缀83965得到839651247 即839647521的下一个。例为后缀大于4的用橙色表示小于4的用绿色表示 找出比右边数字小的第一个数4注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第14页，共34页，编辑于2022年，星期一字典序法举例在1,n的全排列中,n n-1 321是最后一个排列,其中介数是(n-1,n-2,.,3,2,1)其序号为n-1kk!k=1另一方面可直接看出其序号为n!-1 n-1 n-1于是n!-1=kk!即 n!=kk!+1

16、 k=1 k=1注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第15页，共34页，编辑于2022年，星期一字典序法举例一般而言，设P是1,n的一个全排列。P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1Pnj=maxi|PiPj对换Pj，Pk，将Pj+1Pk-1PjPk+1Pn翻转，P=P1P2Pj-1PkPnPk+1PjPk-1Pj+1即P的下一个注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第16页，共34页，编辑于2022年，星期一字典序法举例2)计算给定排列的序号839647521的序号即先于此排列的排列的个数。将先

17、于此排列的排列按前缀分类按前缀分类。前缀先于8的排列的个数：78!第一位是8,先于83得的排列的个数：27!前2位是83,先于839得的排列的个数：66!先于此排列的的排列的个数：78!+27!+66!前3位是839,先于8396得的排列的个数：45!+45!前4位是8396,先于83964得的排列的个数：24!+24!前5位是83964,先于839647得的排列的个数：33!+33!前6位是839647,先于8396475得的排列的个数：22!+22!前7位是8396475,先于83964752得的排列的个数：11!+11!297191 前8位固定，则最后一位也随之固定 将8!,7!,1!前

18、面的系数抽出，放在一起得到 72642321此数的特点：7：8的右边比8小的数的个数 2：3的右边比3小的数的个数6：9的右边比9小的数的个数4：6的右边比6小的数的个数2：4的右边比4小的数的个数3：7的右边比7小的数的个数2：5的右边比5小的数的个数1：2的右边比2小的数的个数72642321是计算排列839647521的序号的中间环节，我们称之为中介数中介数。这是一个很有用的概念。注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第17页，共34页，编辑于2022年，星期一字典序法举例一般而言,对于1,9的全排列中介数首位的取值为08，第2位的取值为07，以此类推，

19、第8位的取值为0、1。从而序号可表示为：n-1 ki(n-i)!i=1ki：Pi的右边比Pi小的数的个数i=1,2,n-1注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第18页，共34页，编辑于2022年，星期一字典序法举例由中介数推出排列的算法例 由72642321推算出839647521方法1：P1 P2 P3 P4 P5 P6 P7 P8 P9_ _ _ _ _ _ _ _ _P1=887+1=82+1=3P2=336+1=7，但3已在P3左边出现，7+1=8，但8已在P3左边出现，8+1=9 P3=994+1=5，但3已经在P4左边出现，5+1=6 P4=66

20、2+1=3，但3已经在P5左边出现，3+1=4 P4=443+1=4，但3,4已经在P6左边出现，4+1+1=6，但6已经在P6左边出现，6+1=7 P6=772+1=3，但3已经在P7左边出现，3+1=4，但4已经在P7左边出现，4+1=5 P7=551+1=2 P8=2 P9=1 2 1这个过程比较麻烦(这酝酿着改进的可能)，该算法从左到右依次推出P1,P2,P9。下述算法依次定出1,2,3,9的位置。注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第19页，共34页，编辑于2022年，星期一字典序法举例方法2-1：72642321中未出现0，1在最右边中介数右端加

21、一个0扩成9位，先定1，每定一位，其左边未定位下加一点，从（位位下点数=0）的位中选最左最左的。7 2 6 4 2 3 2 1 0定 1 的位置1223344 55 66 77 8899由72642321推算出839647521注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第20页，共34页，编辑于2022年，星期一字典序法举例方法2-2：已定出上标，找左起第一个0，下标_由72642321推算出839647521 72642321-11111111=61531210_ _ _ _ _ _ _ _ 12 61531210-11111110=504201003 5042

22、0100-10000000=404201004 40420100-10110000=303101005 30310100-10110100=202000006 20200000-10100000=101000007 10100000-10100000=000000008 000000009以上两种从中介数求排列的算法都比较麻烦。给定一排列与下一个排列各自的中介数进位链（中介数的后继）递增进位制数注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第21页，共34页，编辑于2022年，星期一递增进位制数法举例_ _ _ _ _ _ _ _ _ 6 7 3 4 2 2 2 1

23、a9 a8 a7 a6 a5 a4 a3 a2_ _/V 6个空格9_ _/V 7个空格8 _ _/V 3个空格765431 _ _/V 4个空格 _ _/V 2个空格 1个空格 序号 nm=ak(k-1)!k=22注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第22页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shangh

24、ai Jiaotong University2323生成算法分析n在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。n递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。n这就启发我们，能不能设计一种算法：n下一个排列总是上一个排列某相邻两位对换得到的。n递减进位制数字的换位是单向的，从右向左，n而将要介绍的邻位对换法的换位是双向的。第23页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engi

25、neering，Shanghai Jiaotong University Shanghai Jiaotong University2424邻位互换生成算法n这个算法可描述如下n对1 to n-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1 to n的n个排列。n对1 to n-1的每一个奇排列，n从左到右插入n个空档，生成1 to n的n个排列n对2,n的每个数字都是如此第24页，共34页，编辑于2022年，星期一邻位对换法举例例 839647521 836947521解2的右边有1个数字(奇数)比2小,2上加一个点。3的右边有2个数字(偶数)比3小,3上不加点。4的右边有2个数

26、字(偶数)比4小,4上不加点。5的右边有2个数字(偶数)比5小,5上不加点。6的右边有2个数字(偶数)比6小,6上不加点。7的右边有3个数字(奇数)比7小,7上加一个点。8的右边有7个数字(奇数)比8小,8上加一个点。18上共有3个(奇数)点，9上箭头向右。P=839647521()b2 b3 b4 b5 b6 b7 b8 b9101213722上箭头向左，2右边有1个数字比2小，b2=13上箭头向右，3左边有0个数字比3小，b3=04上箭头向右，4左边有1个数字比4小，b4=15上箭头向右，5左边有2个数字比5小，b5=26上箭头向右，6左边有1个数字比6小，b6=17上箭头向左，7右边有3

27、个数字比7小，b7=38上箭头向左，8右边有7个数字比8小，b8=79上箭头向右，9左边有2个数字比9小，b9=2 839647521的中介数为10121372注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第25页，共34页，编辑于2022年，星期一邻位对换法举例ak(p)：p中1k排列的序号，ak(p)的奇偶性与1k排列的奇偶性相同。a9(p)=9a8(p)+b9(p)=9(8a7(p)+b8(p)+b9(p)an(p)，bn(p)简写成an，bn注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第26页，共34页，编辑于2022年，星期一邻位

28、对换法举例已知已知(10121372)求排列。求排列。9的位置由b9和a8的奇偶性决定。a8的奇偶性同b8的奇偶性。a7的奇偶性同b7+b6的奇偶性。b2=0,1。b8奇9，b6+b7偶8，b6奇7，b4+b5奇6，b4奇5序号=13+0)4+1)5+2)6+1)7+3)8+7)9+2=203393(10121372)注：本讲义中的动画部分摘自他人的讲义注：本讲义中的动画部分摘自他人的讲义第27页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science

29、 and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University2828组合的生成组合的生成n设从1,n中取r元的组合全体为C(n,r)，C1C2CrC(n,r).n不妨设C1C2Cr,iCi(nr+i),i=1,2,r n令j=maxi|Cinr+i，则C1C2Cr的下一个组合下一个组合下一个组合下一个组合为C1C2Cj-1(Cj+1)(Cj+2)(Cj+rj+1)n这等于给C(n,r)的元素建立了字典序.第28页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Comp

30、uter Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University2929组合的生成举例组合的生成举例n例例用两种方法计算1,n的无重不相邻组合C(n,r)的计数问题n解法1:00100100100100 共有n位，其中含有r个1且不可含11。n以1结尾：r-1个10与n-1-2(r-1)个0的排列r-1+n-1-2(r-1)=n-r 这样的排列有 n以0结尾：r个10与n-2r个0的排列r+n-2r=n-r这

31、样的排列有 个,n所以，第29页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University3030组合的生成举例组合的生成举例n解法2:任给a1a2arC(n,r),a1a2ar 令f：a1a2arb1b2brbi=ai-i+1,i=1,2,r.1b1b2brn-r+1,b1b2brC(n-r+1,r)C(n

32、,r)=C(n-r+1,r)第30页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University3131允许重复的组合nC(n,r)的计数问题相当于r相同的球放入n个互异的盒子，每盒球的数目不同的方案的计数。n而问题C(n,r):可重复的组合，可转换为r个相同的球与n-1个相同的盒壁的排列的问题n其计数为 C(

33、n+r-1,r)n即C C(n,r)=(n,r)=C(n+r-1,r)=C C(n-1,r)+(n-1,r)+C C(n,r-1)(n,r-1)不含指定球”ai”，至少含一个指定球”ai”第31页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University3232另一个证明n设a1a2arC(n,r),1a1a

34、2arn,令C(n,r)上的f，使得bi=ai+i-1,i=1,2,r.则b1b2br满足1b1b2brn+r-1b1b2brC(n+r-1,r),f：a1a2arb1b2br显然f是单射，f-1:b1b2bra1a2arai=bi-i+1,i=1,2,r.a1a2arC(n,r)f是单射 C(n,r)C(n+r-1,r)f-1是单射 C(n,r)C(n+r-1,r)C(n,r)=C(n+r-1,r)n第二个证明可说一种“拉伸压缩”技巧。不可谓不巧妙。第32页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and Eng

35、ineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University3333若干说明n n等式的组合意义n许多等式来自组合计数，有特定的含义nStirling近似公式n意味着相对误差趋于0：n但绝对误差无穷大：第33页，共34页，编辑于2022年，星期一2022/10/52022/10/5Dept of Computer Science and EngineeringDept of Computer Science and Engineering，Shanghai Jiaotong University Shanghai Jiaotong University3434 Thanks!第34页，共34页，编辑于2022年，星期一