组合数学教程

1、5193724861.1 加法法则与乘法法则 加法法则加法法则 设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言：若 |A| = m , |B| = n , AB = , 则 |AB| = m + n 。 例 某班选修企业管理的有 18 人，不选的有 10 人，则该班共有 18 + 10 = 28 人。 例 北京每天直达上海的客车有 5 次，客机有 3 次， 则每天由北京直达上海的旅行方式有 5 + 3 = 8 种。 乘法法则乘法法则 设事件A有m种产生式，事件B有n种产生方式，则事件A与B有 m n种产生方式。集合论语言：若 |A| = m , |

2、B| = n , AB = (a,b) | a A,b B, 则 |A B| = m n 。例 某种字符串由两个字符组成，第一个字符可选自a，b，c，d，e，第二个字符可选自1，2，3，则这种字符串共有5 3 = 15 个。例 从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6 条道路。1)小于10000的不含1的正整数可看做4位数,但0000除外. 故有999916560个. 含1的有：99996560=3439个另: 全部4位数有10 个,不含1的四位数有9 个, 含1的4位数为两个的差: 10 9 = 3439个4 44 42)“含含0”和和“含含1”不可直接套用。不可直接

3、套用。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个个2342345nrr n!r!(n-r)!5+7+10 2解解 1) 57+510+710=155; 2) C(5,2)+C(7,2)+C(10,2) =10+21

4、+45=76; 3) 155+76=231=( ) n!r1!r2!rt! nr1 r2 rt 12 4 3 1234 12 4 3 2341 12 4 3 3412 12 4 3 4123 1 1 2 3 3 2解解 将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=14851003解一进站方案表

5、示成：00011001010100其中“0”表示人，“1”表示门框，其中“0”是不同元，“1”是相同元。给“1”n个门只用n-1个门框。任意进站方案可表示成上面14个元素的一个排列。令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 k令n! = 135(n-2)n，n是奇数。246(n-2)n，n是偶数。(1-3-2)由(1-3-1)， I1,

6、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 k ， (2k)! (2k-1)! (2k-2)!(2k+1)! (2k)! 2 (2k-1)!1 1. 2 (2k)!(2k-1)! 1 2k+12k+1 2k2klim = , (2k)!(2k-1)! 1 2k+12 2klim = ,(2k)!(2k)! (2k)! 1 2k+12 2klim = 。(1-10-3)2 (k!) (2k)! 1 2k+12 2k2k 2y y=lnx 0 1 2 3 n-1 n xn

7、 n n1 1 11 12 2121 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)1212120AntnTntn=18n12nn n1-bnnen12n1-bnnen简单格路问题 |(0,0)(m,n)|=( )从 (0,0)点出发沿x轴或y轴的正方向每步走一个单位，最终走到(m,n)点，有多少条路径？m+n my (m,n).0 .

8、 . . x(m+n)! m+n m+n m!n! m n(c-a)+(d-b) c-a (c,d)(a,b)y y=x (m,n)0 (1,0) x(0,1). .y x-y=1 (m,n) x(0,0) (1,-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 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 格路也

9、是一种常用模型 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 丙烷 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.n-2 生长点不是叶子,每

10、个生长点是1,n中的任一元.有n种选择。两个顶点的树是唯一的。 | | 41 2 5 3逐个摘去标号最小的叶子，叶子的相邻顶点(不是叶子，是内点)形成一个序列，序列的长度为n-2例例 给定一棵有标号的树边上的标号表示摘去叶的顺序。(摘去一个叶子相应去掉一条边) 第一次摘掉，为相邻的顶点，得到序列的第一个数3以此类推，得到序列31551,长度为72 = 5这是由树形成序列的过程。由序列31551得到一个新序列111233455567生成的过程是首先将31551排序得到11355，因为序列31551的长度为5，得到按升序排序的序列1234567，序列的长度为5+2(即n+2)，然后将11355按照

11、大小插入到序列1234567中，得到111233455567然后将两个序列排在一起 31551111233455567 31551111233455567 15511113455567 55111455567 51115567 11157 17第一步推导：将上下两个序列同时去掉上行序列的第一个元素3(用黄色表示)，去掉下行序列的第一个无重复的元素2(用红色表示)。生成一条边()。依此类推，减到下面剩最后两个元素，这两个元素形成最后一条边。最后形成树。 给定序列b=(b1b2bn-2) 设a=(123n-1 n)将b的各位插入a,得a,对( )做操作。a是2n-2个元的可重非减序列。ba操作是从

12、a中去掉最小无重元，设为a1,再从b和a中各去掉一个b中的第一个元素，设为b1，则无序对(a1,b1)是一条边。重复这一操作，得n-2条边，最后a中还剩一条边，共 n-1条边，正好构成一个树。b中每去掉一个元，a中去掉2个元。ban-2n-2n-2全排列的生成算法全排列的生成算法(A)字典序法(B)递增进位制数法(C)递减进位制数法(D)邻位对换法 一个全排列可看做一个字符串，字符串可有前缀前缀、后缀后缀。7 5 2 1 747 42 2 41 1 在后缀7521中找出比4大的数7 5找出其中比4大的最小数 5 5 4 、5 对换 8396 7 215 4后缀变为7421 将此后缀翻转 12

13、4 7接上前缀83965得到839651247 即839647521的下一个。例为后缀大于4的用橙色表示小于4的用绿色表示 找出比右边数字小的第一个数4n-1kk!k=1另一方面可直接看出其序号为n!-1 n-1 n-1于是n!-1= kk! 即 n!=kk! +1 k=1 k=1P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1Pnj=maxi|PiPj对换Pj，Pk，将Pj+1Pk-1PjPk+1Pn翻转，P= P1P2Pj-1PkPnPk+1PjPk-1Pj+1即P的下一个839647521的序号即先于此排列的排列的个数。将先于此排列的排列按前缀分类按前缀分类。前缀先于8

14、的排列的个数：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此

15、数的特点： 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的序号的中间环节，我们称之为中介数中介数。这是一个很有用的概念。例 由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

16、=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的位置。72642321中未出现0，1在最右边中介数右端加一个0扩成9位，先定1，每定一位，其左边未定位下加一点，从（位

17、位下点数=0）的位中选最左最左的。7 2 6 4 2 3 2 1 0定 1 的位置1223344 55 66 77 8899由72642321推算出839647521已定出上标，找左起第一个0，下标_由72642321推算出839647521 72642321-11111111=61531210_ _ _ _ _ _ _ _ 12 61531210 -11111110=504201003 50420100 -10000000=404201004 40420100 -10110000=303101005 30310100 -10110100=202000006 20200000 -1010000

18、0=101000007 10100000 -10100000=000000008 000000009以上两种从中介数求排列的算法都比较麻烦。给定一排列与下一个排列各自的中介数进位链（中介数的后继）递增进位制数 在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。 在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2n)一致。为方便起见，令ai+1=kn-I，i=1,2,n-1(k1k2kn-1)=(anan-1a2)ai：i的右边比i小的数字的个数由(anan-1a2)求p1p2pn。从大到小求出n,n-1,2,1的位置

19、_ . _ n _ _ _ an个空格n的右边有an个空格。n-1的右边有an-1个空格。2的右边有a2个空格。最后一个空格就是1的位置。_ _/ V 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=22把递增进位制数翻转,就得到递减进位制数。(anan-1a2)(a2a3an-1an) 839647521 (12224376) n nm=akn!/k!=n!ak/k! k=2 k=2(1

20、2224376)=13+2)4+2)5+2)6+4)7+3)8+7)9+6=340989 求下一个排列十分容易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 b

21、91 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的中介数为10121372a9(p)=9a8(p)+b9(p) =9(8a7(p)+b8(p)+b9(p)an(p)，bn(p)简写成an，bn9的位置由b9和a8的奇偶性决定。a

22、8的奇偶性同b8的奇偶性。a7的奇偶性同b7+b6的奇偶性。b2=0,1。b8奇9，b6+b7偶8，b6奇7，b4+b5奇6，b4奇58 83 39 96 64 47 75 52 21 1字字典典序序法法递递增增进进位位制制法法递递减减进进位位制制法法邻邻位位对对换换法法下下一一个个8 83 39 96 65 51 12 24 47 78 84 49 96 61 17 75 52 23 38 89 93 36 64 47 75 52 21 18 83 36 69 94 47 75 52 21 1中中介介数数7 72 26 64 42 23 32 21 1 6 67 73 34 42 22 22

23、 21 1 1 12 22 22 24 43 37 76 6 1 10 01 12 21 13 37 72 2序序 号号 297191279905340989203393 _ _ n r_ _ _ / / 共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-1n-r r n-r n-r n-r+1r-1 r r (n-1+r)! r!(n-1)!n+r-1 r r个相同的球 / 001001100 / /n-1个相同的盒壁-1-11)(0,0)(m-1,n)(

24、-1) ( )|r|-1|n|-1n+r nr r!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的不断分类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+1n+r+1 rn+1 n+1 n+1 n+1 r r-1 r-2 0 n+r

25、 n+r-1 n+r-2 n r r-1 r-2 0n l n n-rl r r l-rm 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 mn n n n0 1 2 nn n-k knk nk=0n ni ii奇 i偶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=0k l n+k+l-j n+k n+l j j k+l k lj0证：证：利用Vandermonde恒等式

26、及 ( )( )=( )( )=( )( ) (接下页)n v n n-p n n-pv p p n-v p v-p 有 ( )( )( ) =( )( )( )( ) ) =( )( )( )( ) =( )( )( )( ) =( )( )( ) =( )( )( ) =( )( )( ) =( )( )k l n+k+l-j j j k+l k l n+k l-j j j k+v l-v n+k k l l-jk+v j j l-v n+k k l vk+v j v ln+k l k+vk+v v kn+k n l k n-v vn+k n l k n-v vn+k n+l k l j0 j0 vj v0 j0 v0 j0 v0 v0 v0m mk m-km+n m n m n m n m 0 0 1 1 m m 73 钥 匙 A 人 B C D 22 能级k 0 1 2 3 4 A) k +1 1 2 5 10 17 状B)2(k +1) 2 4 10 20 34 态22能量分布 0,0,0,4 0,0,1,3 0,0,2,2 A) 11117 11210 11C(5,2) B) C(2,3)34