组合数学讲义 排列组合

组合数学讲义排列组合第1页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity2第二章：排列组合加法法则、乘法法则排列、组合举例排列、组合生成字典排序法邻位互换法注记

第2页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity3基本计数原理集合S的划分：加法原理若S划分为S1,S2,…,Sm,则乘法原理S为有序对(a,b)集合，其中a有p种选择，b有q种选择，则注：乘法原理是加法原理的一个推论（可以证明）。第3页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity4举例例1.两位数中，有多少两位互异且非零的数？ab为有序对(a,b)，共9x8=72例2.现有6个橘子，9个苹果，欲组成果篮。要求果篮非空，有多少种不同的可能？橘子{0,1,2,3,4,5,6}苹果{0,1,2,3,4,5,6,7,8,9}不同组合7x10=70除去(0,0)的情况，有69种可能第4页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity5计数问题的类型对元素的有序的摆放数或有序的选择数进行计数没有重复如何元素允许元素重复（但可能是有效次重复）对元素的无序的摆放数或无序的选择数进行计数没有重复如何元素允许元素重复（但可能是有效次重复）第5页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity6举例例1.在1000和9999有多少具有不同数字的奇数？有个、十、百、千4个位置可以选择个位：1,3,5,7,9有5种选择千位：剩下8种选择十/百位：8种选择，剩下一位只有7种选择共计5x8x8x7=2240种选择顺序影响乘法原理的使用例2.在0和10000之间整数恰好有一位数字是5？Si是i

位数集合(i=1,2,3,4)|S1|=1；|S2|=17:个位是5有8种，十位是5有9种|S3|=225:个位是5有8x9种，十位是5有8x9种，百位是5有9x9种；|S4|=2763第6页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity7排列、组合问题[定义]从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的全体组成的集合用P(n,r)表示。排列的个数用P(n,r)表示。当r=n时称为全排列。[定义]从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的全体组成的集合用C(n,r)表示，组合的个数用C(n,r)或表示。第7页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity8组合vs.排列从n个中取r个的排列的典型例子是从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种选择，第2个有n-1种选择，……，第r个有n-r+1种选择。故有P(n,r)=n(n-1)……(n-r+1)有时也用[n]r记n(n-1)……(n-r+1)若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)·r!=P(n,r),

第8页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity9例问题：求1000!中的尾数有几个零？分析：一个零对应一对因子2和51000以内5的倍数有200个1000以内25的倍数有40个1000以内125的倍数有8个1000以内625的倍数有1个所以，1000!中5的幂有200+40+8+1=249个1000!中2的幂远多于249个解：1000!中有249个0第9页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity10树的数目图论问题：对n个顶点v1,v2,…,vn用n-1条边连接起来，问有多少种方案？例，给定一棵有标号的树，边上的标号表示摘去叶的顺序（摘去一个叶子相应去掉一条边）逐个摘去标号最小的叶子，叶子的相邻顶点形成一个序列，序列的长度为n-2第一次摘掉②，③为②相邻的顶点，得到序列的第一个数3,以此类推，得到序列31551,长度为7-2=5,这是由树形成序列的过程。第10页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity11n顶点树与n-2序列的对应由序列形成树的过程：给定序列31551（1）从序列1234567（2）中找第一个不在（1）出现的数“2”，建立边“（2,3）”得到1551（1’）及134567（2’），类似得到边（3,1）再得到551（1’’）及14567（2’’）依此类推得到边（4,5），（6,5），（7,1）最后序列（2）中剩下的2个数构成最后的边（1,5）这表明，n顶点树与n-2序列建立了1-1对应第11页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity12Cayley定理定理：n个有标号的顶点的树的数目等于nn-2证明：由1-1对应关系知n个顶点树的数目＝序列b1,b2,…,bn-2(0<b<=n)的数目相应序列的数目为nn-2注：一个问题与另一个问题1-1对应，则可将一个问题转化为另一个问题来处理。在处理组合计数问题时，常常通过问题的1-1对应实现模型的转换，以便于问题的求解。第12页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity13生成排列问题：从已知排列出发，生成新的排列目的：提高效率，减少开销n个元素的排列的个数太多，（Stirling公式）任务：寻找好的算法序数法如十进制、二进制，或递增、递减进制字典序法123,132,213,231,312,321第13页，课件共34页，创作于2023年2月字典序法举例求839647521的下一个排列7521

74＜7

4<5

5

4>2

2

4>1

1

在后缀7521中找出比4大的数75找出其中比4大的最小数55

4、5

对换8396

72154后缀变为7421将此后缀翻转1247接上前缀83965得到839651247即839647521的下一个。[例]为后缀大于4的用橙色表示小于4的用绿色表示

找出比右边数字小的第一个数4注：本讲义中的动画部分摘自他人的讲义第14页，课件共34页，创作于2023年2月字典序法举例在[1,n]的全排列中,nn-1…321是最后一个排列,其中介数是(n-1,n-2,...,3,2,1)其序号为n-1∑k×k!k=1另一方面可直接看出其序号为n!-1

n-1n-1于是n!-1=∑k×k!

即

n!=∑k×k!+1

k=1k=1注：本讲义中的动画部分摘自他人的讲义第15页，课件共34页，创作于2023年2月字典序法举例一般而言，设P是[1,n]的一个全排列。P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pnj=max{i|Pi<Pi+1},k=max{i|Pi>Pj}对换Pj，Pk，将Pj+1…Pk-1PjPk+1…Pn翻转，P’=P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个注：本讲义中的动画部分摘自他人的讲义第16页，课件共34页，创作于2023年2月字典序法举例2)计算给定排列的序号839647521的序号即先于此排列的排列的个数。将先于此排列的排列按前缀分类。前缀先于8的排列的个数：7×8!第一位是8,先于83得的排列的个数：2×7!前2位是83,先于839得的排列的个数：6×6!先于此排列的的排列的个数：7×8!+2×7!+6×6!前3位是839,先于8396得的排列的个数：4×5!+4×5!前4位是8396,先于83964得的排列的个数：2×4!+2×4!前5位是83964,先于839647得的排列的个数：3×3!+3×3!前6位是839647,先于8396475得的排列的个数：2×2!+2×2!前7位是8396475,先于83964752得的排列的个数：1×1!+1×1!297191前8位固定，则最后一位也随之固定将8!,7!,…,1!前面的系数抽出，放在一起得到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页，创作于2023年2月字典序法举例一般而言,对于[1,9]的全排列中介数首位的取值为0—8，第2位的取值为0—7，以此类推，第8位的取值为0、1。从而序号可表示为：

n-1∑ki(n-i)!i=1ki：Pi的右边比Pi小的数的个数i=1,2,…,n-1注：本讲义中的动画部分摘自他人的讲义第18页，课件共34页，创作于2023年2月字典序法举例由中介数推出排列的算法[例]由72642321推算出839647521方法1：P1P2P3P4P5P6P7P8P9_________P1=88→7+1=82+1=3→P2=336+1=7，但3已在P3左边出现，↑7+1=8，但8已在P3左边出现，↑8+1=9→P3=994+1=5，但3已经在P4左边出现，5+1=6→P4=66↑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=121这个过程比较麻烦(这酝酿着改进的可能)，该算法从左到右依次推出P1,P2,…,P9。下述算法依次定出1,2,3,…,9的位置。注：本讲义中的动画部分摘自他人的讲义第19页，课件共34页，创作于2023年2月字典序法举例方法2-1：72642321中未出现0，1在最右边中介数右端加一个0扩成9位，先定1，每定一位，其左边未定位下加一点，从（位－位下点数=0）的位中选最左的。726423210定1的位置1●●●●●●●●22●●●●●●●33●44●●●55●●●●66●●77●●8899由72642321推算出839647521注：本讲义中的动画部分摘自他人的讲义第20页，课件共34页，创作于2023年2月字典序法举例方法2-2：已定出上标‘●’，找左起第一个0，下标‘__’由72642321推算出839647521

●72642321-11111111=61531210________12

●●●●61531210-11111110=504201003●●●●50420100-10000000=404201004●●●●●40420100-10110000=303101005●●●●●●●●30310100-10110100=202000006●●●●●●●●●●20200000-10100000=101000007●●●●●●●●●●●●10100000-10100000=000000008●●●●●●●000000009以上两种从中介数求排列的算法都比较麻烦。给定一排列与下一个排列各自的中介数→进位链（中介数的后继）→递增进位制数注：本讲义中的动画部分摘自他人的讲义第21页，课件共34页，创作于2023年2月递增进位制数法举例_________

67342221↓↓↓↓↓↓↓↓

a9a8a7a6a5a4a3a2★\____________________/

V

6个空格9★\____________________________/

V

7个空格8★★★★★★\________/

V

3个空格765431\________________/

V

4个空格\____/

V

2个空格1个空格

序号

nm=∑ak(k-1)!

k=22注：本讲义中的动画部分摘自他人的讲义第22页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity23生成算法分析在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法：下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左，而将要介绍的邻位对换法的换位是双向的。第23页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity24邻位互换生成算法这个算法可描述如下对1ton-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1ton的n个排列。对1ton-1的每一个奇排列，n从左到右插入n个空档，生成1ton的n个排列对[2,n]的每个数字都是如此第24页，课件共34页，创作于2023年2月邻位对换法举例[例]839647521→836947521●→[解]2的右边有1个数字(奇数)比2小,2上加一个点。●●3的右边有2个数字(偶数)比3小,3上不加点。4的右边有2个数字(偶数)比4小,4上不加点。5的右边有2个数字(偶数)比5小,5上不加点。6的右边有2个数字(偶数)比6小,6上不加点。7的右边有3个数字(奇数)比7小,7上加一个点。8的右边有7个数字(奇数)比8小,8上加一个点。1—8上共有3个(奇数)点，9上箭头向右。P=839647521→()↓b2b3b4b5b6b7b8b9101213722上箭头向左，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个数字比7小，b7=38上箭头向左，8右边有7个数字比8小，b8=79上箭头向右，9左边有2个数字比9小，b9=2839647521的中介数为10121372←→→→→←→←注：本讲义中的动画部分摘自他人的讲义第25页，课件共34页，创作于2023年2月邻位对换法举例ak(p)：p中1—k排列的序号，ak(p)的奇偶性与1—k排列的奇偶性相同。a9(p)=9×a8(p)+b9(p)=9×(8×a7(p)+b8(p))+b9(p)※※an(p)，bn(p)简写成an，bn注：本讲义中的动画部分摘自他人的讲义第26页，课件共34页，创作于2023年2月邻位对换法举例已知(10121372)↓求排列。9的位置由b9和a8的奇偶性决定。a8的奇偶性同b8的奇偶性。a7的奇偶性同b7+b6的奇偶性。b2=0,1。→←→b8奇→9，b6+b7偶→8，b6奇→7，→→

b4+b5奇→6，b4奇→5序号=1·3+0)·4+1)·5+2)·6+1)·7+3)·8+7)·9+2=203393←→(10121372)↓注：本讲义中的动画部分摘自他人的讲义第27页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity28组合的生成设从[1,n]中取r元的组合全体为C(n,r)，C1C2…Cr∈C(n,r).不妨设C1＜C2＜…＜Cr,i≤Ci≤(n－r+i),i=1,2,…,r令j=max{i|Ci＜n－r+i}，则C1C2…Cr的下一个组合为C1C2…Cj

-1(Cj+1)(Cj+2)…(Cj+r－j+1)这等于给C(n,r)的元素建立了字典序.第28页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity29组合的生成举例[例]用两种方法计算[1,n]的无重不相邻组合C'(n,r)的计数问题解法1:

0…010…010…010…010…0共有n位，其中含有r个1且不可含11。①以1结尾：r-1个10与n-1-2(r-1)个0的排列

r-1+[n-1-2(r-1)]=n-r

这样的排列有②以0结尾：r个10与n-2r个0的排列

r+n-2r=n-r这样的排列有个,所以，

第29页，课件共34页，创作于2023年2月2023/7/26DeptofComputerScienceandEngineering，ShanghaiJiaotongUniversity30组合的生成举例解法2:任给a1a2…ar∈C'(n,r),a1＜a2＜…＜ar

令f：a1a2…ar→b1b2…br

bi=ai-i+1,