卢开澄组合数学--组合数学第一章.ppt

组组合合数数学学清华大学计算机 黄连生1999年7月前言 组合数学是一个古老而又年轻的数学分支。据传说，大禹在4000多年前就观察到神龟背上的幻方.前言 幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486前言 贾宪贾宪 北宋数学家（约11世纪）著有黄帝九章细草、算法斅古集斅 音“笑（“古算法导引”）都已失传。杨辉著详解九章算法（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（William Geoge Horner，17861837）的方法（1819年）早770年。前言 1666年莱布尼兹所著组合学论文一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。前言 组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。这与数学分析形成了对照。前言本学期主要讲组合分析（计数和枚举）以及组合优化的一部分（线性规划的单纯形解法）。组合分析是组合算法的基础。前言 组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分计数时的合理分类类和组合模型的转换。组合模型的转换。但是，要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。第一章排列组合1.1 加法法则与乘法法则1.1 加法法则与乘法法则 加法法则加法法则 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言：若|A|=m,|B|=n,AB=,则|AB|=m+n。1.1 加法法则与乘法法则 例 某班选修企业管理的有 18 人，不选的有 10 人，则该班共有 18+10=28 人。例 北京每天直达上海的客车有 5 次，客机有 3 次，则每天由北京直达上海的旅行方式有 5+3=8 种。1.1 加法法则与乘法法则 乘法法则乘法法则 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有 m n种产生方式。集合论语言：若|A|=m,|B|=n,AB=(a,b)|a A,b B,则|A B|=m n。1.1 加法法则与乘法法则例 某种字符串由两个字符组成，第一个字符可选自a，b，c，d，e，第二个字符可选自1，2，3，则这种字符串共有5 3=15 个。例 从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6 条道路。1.1 加法法则与乘法法则例例 某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42 =8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是4 4=16，而只有 4 3=12 种。在乘法法则中要注意事件 A 和 事件 B 的相互独立性。1.1 加法法则与乘法法则例例 1)求小于10000的含1的正整数的个数 2)求小于10000的含0的正整数的个数1)小于10000的不含1的正整数可看做4位数,但0000除外.故有999916560个.含1的有：99996560=3439个另:全部4位数有10 个,不含1的四位数有9 个,含1的4位数为两个的差:10 9=3439个4 44 42)“含含0”和和“含含1”不可直接套用。不可直接套用。0019含含1但不含但不含0。在组合的习题中有许多类似的在组合的习题中有许多类似的隐含隐含的的规定，要特别留神。规定，要特别留神。不含不含0的的1位数有位数有9个，个，2位数有位数有9 个，个，3位数有位数有9 个，个，4位数有位数有9 个个 不含不含0小于小于10000的正整数有的正整数有 9+9 +9 +9 =(9 1)/(91)=7380个个含含0小于小于10000的正整数有的正整数有 99997380=2619个个23423451.2排列与组合定义定义 从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的全体组成的集合用 P(n,r)表示。排列的个数用P(n,r)表示。当r=n时称为全排列。一般不说可重即无重。可重排列的相应记号为 -P(n,r),P(n,r)。l1.2排列与组合定义从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。组合的全体组成的集合用C(n,r)表示，组合的个数用C(n,r)表示，对应于可重组合 -有记号C(n,r),C(n,r)。1.2排列与组合从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)1.2排列与组合若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有 C(n,r)r!=P(n,r),C(n,r)=P(n,r)/r!=nr/r!=()=易见 P(n,r)=nnrr n!r!(n-r)!1.2排列与组合例例 有5本不同的日文书，7本不同的英文书，10本不同的中文书。1)取2本不同文字的书；2)取2本相同文字的书；3)任取两本书1.2排列与组合解解 1)57+510+710=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;3)155+76=231=()5+7+10 21.2排列与组合例例 从1,300中取3个不同的数，使这3个数的和能被3整除，有多少种方案？解解 将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 3)=3,6,9,300.要满足条件，有四种解法：1)3个数同属于A;2)3个数同属于B 3)3个数同属于C;4)A,B,C各取一数.故共有3C(100,3)+100=485100+1000000=148510031.2排列与组合例例 某车站有某车站有6 6个入口处，每个入口处每次只能进一人，个入口处，每个入口处每次只能进一人，一组一组9 9个人进站的方案有多少？个人进站的方案有多少？解一进站方案表示成：00011001010100其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。1.2排列与组合解法1标号可产生5!个14个元的全排列。故若设x为所求方案，则 x5!=14!x=14!/5!=7264857601.2排列与组合解法2在14个元的排列中先确定“1”的位置，有C(14,5)种选择，在确定人的位置，有9！种选择。故C(14,5)9!即所求1.2排列与组合解法3把全部选择分解成若干步，使每步宜于计算。不妨设9个人编成1至9号。1号有6种选择；2号除可有1号的所有选择外，还可（也必须）选择当与1号同一门时在1号的前面还是后面，故2号有7种选择；3号的选择方法同2号，故共有8种。以此类推，9号有14种选择。9故所求方案为61.3 Stirling近似公式组合计数的渐进值问题是组合论的一个研究方向。Stirling公式给出一个求n!的近似公式，它对从事计算和理论分析都是有意义的。1.3 Stirling近似公式1)Wallis公式令Ik=sin xdx.显然I0=,I1=1.k2时，Ik=cosxsin x|+(k1)cos xsin xdx=0+(k1)(1sin x)sin xdx=(k1)(Ik2Ik)k 2k-1 2 0 2 0 2 0 2 02 k-22 k-2故 Ik=Ik-2 (1-3-1)k-1 k1.3 Stirling近似公式令n!=135(n-2)n，n是奇数。246(n-2)n，n是偶数。(1-3-2)由(1-3-1)，I1,k是奇数 Ik=I0,k是偶数(k-1)!k!(k-1)!k!当x(0,/2)时，sin x sin x因而 I2k+1I2kI2k-1,k=1,2,。k+1 k1.3 Stirling近似公式由(1-3-2)，(2k)!(2k-1)!(2k-2)!(2k+1)!(2k)!2 (2k-1)!1 1.2 (2k)!(2k-1)!1 2k+12k+1 2k2k1.3 Stirling近似公式所以lim =,(2k)!(2k-1)!1 2k+12 2klim =,(2k)!(2k)!(2k)!1 2k+12 2klim =。(1-10-3)2 (k!)(2k)!1 2k+12 2k2k 21.3 Stirling近似公式2)2)stirling公式公式y y=lnx 0 1 2 3 n-1 n x1.3 Stirling近似公式令An=lnxdx=xlnx|dx=nlnnn+1 (1-3-4)tn=ln1+ln2+ln(n1)+lnn=ln(n!)lnn (1-3-5)tn的几何意义是由x轴,x=n,以及连接(1,0),(2,ln2),(n1,ln(n1),(n,lnn)诸点而成的折线围成的面积。n n n1 1 11 12 2121.3 Stirling近似公式Tn=+ln2+ln(n1)+lnn (1-3-6)1 18 2Tn是由三部分面积之和构成的。一是曲线y=lnx在x=k点的切线和x轴，以及x=k,x=k包围的梯形，当k分别为2,3,n-1时的面积之和；一是由y=lnx在x=1点的切线，x=3/2线，以及x轴围城的梯形；另一是由y=lnn,x=n,x=n及x轴包围的矩形面积。因而有 tnAnTn (1-3-7)1212121.3 Stirling近似公式令bn=An tn.序列b1,b2,是单调增，而且有上界，故有极限，令 limbn=b1由(1-3-4),(1-3-5)得 bn=nlnnn+1ln(n!)+lnn=lnnn+1ln(n!)+ln n ln(n!)=1bn+lnn ln n lnen!=e n()(1-3-8)0AntnTntn=18n12nn n1-bnnen1.3 Stirling近似公式令n=e ,limn=.将(1-3-8)代入(1-3-3),整理得 =2.所以n!2n ()n1-bnnen1.4模型转换“一一对应”概念是一个在计数中极为基本的概念。一一对应既是单射又是满射。如我们说A集合有n个元素|A|=n，无非是建立了将A中元与1,n元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换。比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。1.4模型转换例例简单格路问题|(0,0)(m,n)|=()从(0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？m+n my (m,n).0 .x1.4模型转换无论怎样走法，在x方向上总共走m步，在y方向上总共走n步。若用一个x表示x方向上的一步，一个字母y表示y方向上的一步。则(0,0)(m,n)的每一条路径可表示为m 个x与n个y的一个有重排列。将每一个有重排列的x与y分别编号，可得m!n!个m+n元的无重全排列。1.4模型转换设所求方案数为p(m+n；m，n)则P(m+n；m，n)m!n!=(m+n)!故P(m+n;m,n)=()=()=C(m+n,m)设ca,db,则由(a,b)到(c,d)的简单格路数为|(a,b)(c,d)|=()(m+n)!m+n m+n m!n!m n(c-a)+(d-b)c-a (c,d)(a,b)1.4模型转换例例 在上例的基础上若设mn，求(0,1)点到(m,n)点不接触对角线x=y的格路的数目 (“接触”包括“穿过”)从(0,1)点到(m,n)点的格路，有的接触x=y，有的不接触。对每一条接触x=y的格路，做(0,1)点到第一个接触点部分关于x=y的对称格路，这样得到一条从(1,0)到(m,n)的格路。1.4模型转换容易看出从(0,1)到(m,n)接触x=y的格路与(1,0)到(m,n)的格路(必穿过x=y)一一对应y y=x (m,n)0 (1,0)x(0,1).y x-y=1 (m,n)x(0,0)(1,1).1.4模型转换故所求格路数为()()=()=()=(1)()=()m+n-1 m+n-1 m m-1(m+n-1)!(m+n-1)!(m+n-1)!1 1m!(n-1)!(m-1)!n!(m-1)!(n-1)!m nm+n-1 m+n-1 m m n-m m n n m+n-1 m n-m n 1.4模型转换若条件改为可接触但不可穿过，则限制线要向下或向右移一格，得xy=1，(0,0)关于xy=1的对称点为(1,-1).所求格路数为 ()()=()m+n m+n m m-1(m+n)!(m+n)!n+1-m m!n!(m-1)!(n+1)!n+1 m+n m 格路也是一种常用模型1.4模型转换例例 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 丙烷1.4模型转换 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 Hn=4 丁烷 n=4异丁烷这说明对应CnH2n+2的枝链是有3n+2个顶点的一棵树，其中n个顶点与之关联的边数为4；其它2n+2个顶点是叶子。对于这样结构的每一棵树，就对应有一种特定的化合物。从而可以通过研究具有上述性质的树找到不同的碳氢化合物CnH2n+2.1.4模型转换例例 在100名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？解解 一种常见的思路是按轮计场，费事。另一种思路是淘汰的选手与比赛(按场计)集一一对应。99场比赛。1.4模型转换例例 (Cayley定理)n个有标号的顶点的树的数目等于n 。n-2 生长点不是叶子,每个生长点是1,n中的任一元.有n种选择。两个顶点的树是唯一的。1.4模型转换|41 2 5 3逐个摘去标号最小的叶子，叶子的相邻顶点(不是叶子，是内点)形成一个序列，序列的长度为n-2例例 给定一棵有标号的树边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边)第一次摘掉，为相邻的顶点，得到序列的第一个数3以此类推，得到序列31551,长度为72=5这是由树形成序列的过程。1.4模型转换由序列形成树的过程：由序列31551得到一个新序列111233455567生成的过程是首先将31551排序得到11355，因为序列31551的长度为5，得到按升序排序的序列1234567，序列的长度为5+2(即n+2)，然后将11355按照大小插入到序列1234567中，得到111233455567然后将两个序列排在一起 315511112334555671.4模型转换 31551111233455567 15511113455567 55111455567 51115567 11157 17第一步推导：将上下两个序列同时去掉上行序列的第一个元素3(用黄色表示)，去掉下行序列的第一个无重复的元素2(用红色表示)。生成一条边()。依此类推，减到下面剩最后两个元素，这两个元素形成最后一条边。最后形成树。1.4模型转换上述算法描述：给定序列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个元。1.4模型转换由算法知由树T得b=(b1b2bn-2)，反之，由b可得T。即 f：Tb 是一一对应。由序列确定的长边过程是不会形成回路的。因任意长出的边(u,v)若属于某回路，此回路中必有一条最早生成的边，不妨就设为(u,v)，必须使u,v都在长出的边中重复出现，但照算法u,v之一从下行消失，不妨设为u，从而不可能再生成与u有关的边了，故由()得到的边必构成一个n个顶点的树。ba1.4模型转换证 由一棵n个顶点的树可得到一个长度为n2的序列，且不同的树对应的序列 不同*，因此|T|n 。*对n用归纳法可证反之，由一个长度为n2的序列(每个元素为1 n 的一个整数)，可得到一棵树，且不同的序列对应的树是不同的，因此 n|T|T|=n#n-2n-2n-21.5全排列的生成算法 就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。全排列的生成算法全排列的生成算法1.5全排列的生成算法这里介绍全排列算法四种：(A)字典序法(B)递增进位制数法(C)递减进位制数法(D)邻位对换法1.5.1字典序法 对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。1.5.1字典序法 例例 字符集1,2,3,较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。一个全排列可看做一个字符串，字符串可有前缀前缀、后缀后缀。1.5.1字典序法1）生成给定全排列的下一个排列所谓一个的下一个一个的下一个就是这一个这一个与下一个下一个之间没有其他的没有其他的。这就要求这一个与下一个有尽可能长长的共同前缀共同前缀，也即变化限制在尽可能短短的后缀后缀上。1.5.1字典序法 例例 839647521是1-9的排列。19的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。1.5.1字典序法求83964 47521的下一个排列7 5 2 1 747 42 2 41 1 在后缀7521中找出比4大的数7 5找出其中比4大的最小数 5 5 4、5 对换 8396 7 215 4后缀变为7421 将此后缀翻转 12 4 7接上前缀83965得到839651247 即839647521的下一个。例为后缀大于4的用橙色表示小于4的用绿色表示 找出比右边数字小的第一个数41.5.1字典序法在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 k=1 k=11.5.1字典序法一般而言，设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的下一个1.5.1字典序法2)计算给定排列的序号839647521的序号即先于此排列的排列的个数。将先于此排列的排列按前缀分类按前缀分类。前缀先于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!前面的系数抽出，放在一起得到 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的序号的中间环节，我们称之为中介数中介数。这是一个很有用的概念。1.5.1字典序法一般而言,对于1,9的全排列中介数首位的取值为08，第2位的取值为07，以此类推，第8位的取值为0、1。从而序号可表示为：n-1 ki(n-i)!i=1ki：Pi的右边比Pi小的数的个数i=1,2,n-11.5.1字典序法由中介数推出排列的算法例 由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=662+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的位置。1.5.1字典序法方法2-1：72642321中未出现0，1在最右边中介数右端加一个0扩成9位，先定1，每定一位，其左边未定位下加一点，从（位位下点数=0）的位中选最左最左的。7 2 6 4 2 3 2 1 0定 1 的位置1223344 55 66 77 8899由72642321推算出8396475211.5.1字典序法方法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以上两种从中介数求排列的算法都比较麻烦。给定一排列与下一个排列各自的中介数进位链（中介数的后继）递增进位制数1.5.2递增进位制数法1)由排列求中介数 在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2n)一致。1.5.2递增进位制数法可看出n-1位的进位链。右端位逢2进1，右起第2位逢3进1，右起第i位逢i+1进1，i=1,2,n-1.这样的中介数我们称为递增进位制数。上面是由中介数求排列。1.5.2递增进位制数法由序号（十进制数）求中介数（递增进位制数）如下：m=m1,0 m n!-1 m1=2m2+kn-1,0 kn-1 1 m2=3m3+kn-2,0 kn-2 2 .mn-2=(n-1)mn-1+k2,0 k2 n-2 mn-1=k1,0 k1 n-1 p1p2pn(k1k2kn-1)m1.5.2递增进位制数法在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。为方便起见，令ai+1=kn-I，i=1,2,n-1(k1k2kn-1)=(anan-1a2)ai：i的右边比i小的数字的个数1.5.2递增进位制数法在这样的定义下，有839647521(67342221)(67342221)+1=(67342300)84961752368+7)7+3)6+4)5+2)4+2)3+2)2+1=2799051.5.2递增进位制数法由(anan-1a2)求p1p2pn。从大到小求出n,n-1,2,1的位置_._ n _ _ _ an个空格n的右边有an个空格。n-1的右边有an-1个空格。2的右边有a2个空格。最后一个空格就是1的位置。_ _/V1.5.2递增进位制数法_ _ _ _ _ _ _ _ _ 6 7 3 4 2 2 2 1 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=221.5.3递减进位制数法在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。(anan-1a2)(a2a3an-1an)839647521(12224376)n nm=akn!/k!=n!ak/k!k=2 k=2(12224376)=13+2)4+2)5+2)6+4)7+3)8+7)9+6=340989 求下一个排列十分容易1.5.4邻位对换法递减进位制数法的中介数进位不频繁，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。递减进位制数字的换位是单向的，从右向左，而邻位对换法的换位是双向的。1.5.4邻位对换法这个算法可描述如下：对1n-1的每一个偶排列，n从右到左插入n个空档(包括两端)，生成1n的n 个排列。对1n-1的每一个奇排列，n从左到右插入n个空档，生成1n的n个排列。对2,n的每个数字都是如此。1.5.4邻位对换法例 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上加一个点。18上共有3个(奇数)点，9上箭头向右。P=839647521()b2 b3 b4 b5 b6 b7 b8 b91 0 1 2 1 3 7 22上箭头向左，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=2 839647521的中介数为101213721.5.4邻位对换法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，bn1.5.4邻位对换法已知已知(10121372)求排列。求排列。9的位置由b9和a8的奇偶性决定。a8的奇偶性同b8的奇偶性。a7的奇偶性同b7+b6的奇偶性。b2=0,1。b8奇9，b6+b7偶8，b6奇7，b4+b5奇6，b4奇51.5.4邻位对换法序号=13+0)4+1)5+2)6+1)7+3)8+7)9+2=203393(10121372)1.5.4邻位对换法1.6组合的生成设从1,n中取r元的组合全体为C(n,r).C1C2CrC(n,r).不妨设C1C2CriCi(nr+i),i=1,2,r令j=maxi|Cinr+i.则C1C2Cr的下一个组合为C1C2Cj-1(Cj+1)(Cj+2)(Cj+rj+1)这等于给C(n,r)的元素建立了字典序。12r的序号为0，n-r+1 n-r+2n的序号为()1 _ _ n r1.6组合的生成例 在C(10,4)中 4679的序号是首位小于4的组合的个数；首位是4，第2位小于6的组合的个数；前2位是46，第3位小于7的组合的个数；前3位是467，第4位小于9的组合的个数之和。反之，也可以由序号求组合。1.6组合的生成A(m,l)：1,m的l-组合(或l-子集)。第1个组合：1,2,l-1,l.最后1个组合：1,2,l-1,mA(n,k)=A(n-1,k)，A(n-1,k-1)nA：将有序集A(或线性表)的顺序逆转的有序集。An：将A中每个元素(是集合)都与n求并的有序集_ _ _1.6组合的生成例 用两种方法计算1,n的无重不相邻组合C(n,r)的计数问题解法1 00100100100100 其中不可含11 /共n位r个1 /以1结尾：r-1个10与n-1-2(r-1)个0的排列r-1+n-1-2(r-1)=n-r这样的排列有 (n-r)!=(r-1)!(n-2r+1)!()n-rr-11.6组合的生成以0结尾：r个10与n-2r个0的排列 r+n-2r=n-r这样的排列有()个()+()=()f(a1a2ar)=b1b2brn-r r n-r n-r n-r+1r-1 r r1.6组合的生成解法任给a1a2arC(n,r),a1 a2 ar令f：a1a2arb1b2brbi=ai-i+1,i=1,2,r.1b1 b2 br n-r+1,b1b2brC(n-r+1,r)C(n,r)=C(n-r+1,r)1.7可重组合C(n,r)的计数问题相当于r相同的球放入n个互异的盒子，每盒球的数目不同的方案的计数。而后一问题又可转换为r个相同的球与n-1个相同的盒壁的排列的问题。易知所求计数为 =C(n+r-1,r)即C(n,r)=()=C(n-1,r)+C(n,r-1)不含“”至少含一个“”(n-1+r)!r!(n-1)!n+r-1 r r个相同的球 /001001100 /n-1个相同的盒壁1.7可重组合另证设a1a2arC(n,r)1a1a2 arn,令C(n,r)上的f，使得bi=ai+i-1,i=1,2,r.则b1b2br满足1b1b2brn+r-1 b1b2brC(n+r-1,r)f：a1a2arb1b2br显然f是单射，f ：b1b2bra1a2ar-11.7可重组合ai=bi-i+1,i=1,2,r.a1a2arC(n,r)f是单射C(n,r)C(n+r-1,r)f 是单射 C(n,r)C(n+r-1,r)C(n,r)=C(n+r-1,r)第二个证明可说一种“拉伸压缩”技巧。不可谓不巧妙。但仍不如第一证明来的明快，由此可见组合证明的功效。-11.8若干等式及其组合意义组合意义或组合证明，含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。1.8若干等式及其组合意义1.C(n,r)=C(n,n-r)(1.7.1)从1,n去掉一个r子集，剩下一个(n-r)子集。由此建立C(n,r)与C(n,n-r)的一个一一对应。故C(n,r)=C(n,n-r)1.8若干等式及其组合意义2.C(n,r)=C(n-1,r)+C(n-1,r-1)(1.7.2)从1,n取a1,a2,ar.设1a1a2arn,对取法分类：a1=1,有C(n-1,r-1)种方案 a11,有C(n-1,r-1)种方案共有C(n-1,r)+C(n-1,r-1)中方案，故C(n,r)=C(n-1,r)+C(n-1,r-1)1.8若干等式及其组合意义杨辉三角除了(0,0)点，都满足此递推式 0rn,n0r C(n,r)=1,r=00,0nr,r0nn0且r0C(m+n,m)=C(m+n-1,m)+C(m+n-1,m-1)(0,0)(m,n)=(0,0)(m,n-1)(0,0)(m-1,n)(-1)()|r|-1|n|-1n+r nr r!1.8若干等式及其组合意义3.()+()+()+()=()(1.7.3)1可从(7.2)推论，也可做一下组合证明从1,n+r+1取a1a2anan+1，设a1a2an an+1，可按a1的取值分类：a1=1,2,3,r,r+1.a1=1,a2an+1取自2,n+r+1 有()种取法n n+1 n+2 n+r n+r+1n n n n nn+r na1=2,a2an+1取自3,n+r+1 有()种取法n+r-1 n a1=r,a2an+1取自r+1,n+r+1 有()种取法n+1 na1=r+1,a2an+1取自r+2,n+r+1 有()种取法nn也可看做按含1不含1，含2不含2,含r不含r的不断分类1.8若干等式及其组合意义2从(0,0)到(n+1,r),过且仅过一条带箭头的边,而过这些边的路径有(从下到上)(),(),()故有.()+()+()+()=()n n+1 n+rn n nn n+1 n+2 n+r n+r+1n n n n nr (n+1,r).(0,0)n n+11.8若干等式及其组合意义3 可重组合.1,n+2的C(n+2,r)模型 ()不含1,含1个1,含2个1,含r个1C(),C(),C(),C()(),(),(),()n+r+1 rn+1 n+1 n+1 n+1 r r-1 r-2 0 n+r n+r-1 n+r-2 n r r-1 r-2 01.8若干等式及其组合意义4.()()=()()(1.7.4)选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委选常委,再选非常委政治局委员两种选法都无遗漏,无重复地给出可能的方案，应该相等。n l n n-rl r r l-r1.8若干等式及其组合意义5.()+()+()=2,m0,(1.7.5)证证1 1(x+y)=()x y,令x=y=1,得(1.7.5)组合证组合证1 1 1,m的所有方案.每一子集都可取k1,m或不取.这样有2 个方案.另可有0-子集(空集),1-子集,m-子集.组合证组合证2 2 从(0,0)走m步有2 种走法,都落在直线x+y=m上,而到(m,0),(m-1,1),(m-2,2),(2,m-2),(1,m-1),(0,m)各点的走法各有(),(),(),(),(),()种m m m m0 1 m m k m-k m m kk=0mmm m m m m m 0 1 2 m-2 m-1 m1.8若干等式及其组合意义6.()-()+()-()=0 (1.7.6)证证1 1 在(x+y)=()x y 中令x=1,y=-1即得.n n n n0 1 2 nn n-k knk nk=01.8若干等式及其组合意义证证2 2 在1,n的所有组合中,含1的组合不含1的组合.有11对应关系。在任一含1组合及与之对应的不含1组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集，将含偶数阁元的组合做成另一集。此二集的元数相等。()=()n ni ii奇 i偶1.8若干等式及其组合意义7.()=()()+()()+()()(1.7.7)即Vandermonde恒等式证证1 1 从m个互异红球和n个互异蓝球中取r个球,按r个球中红球的个数分类.组合证法组合证法:(0,0)到(m+n-r)点的路径.(0,0)(m-r+l,r-l)(m+n-r,r)()()()=()()m+n m n m n m n r 0 r 1 r-1 r 0m nr-l lm+n m n r r-l lP(m-r,r)(m+n-r,r)(m-r+l,r-l)l=0,1,2,r Q(m,0)rl=01.8若干等式及其组合意义李善兰(18111882），清代数学家李善兰恒等式：()()()=()()k l n+k+l-j n+k n+l j j k+l k lj0证：证：利用Vandermonde恒等式及 ()()=()()=()()(接下页)n v n n-p n n-pv p p n-v p v-p 1.8若干等式及其组合意义有()()()=()()()()=()()()()=()()()()