组合数学-第一章-排列组合6

1、1.5全排列的生成算法这里介绍全排列算法三种：(A)序数法(B)字典序法(C) 邻位对换法1.5.1 序数法 把n-1个元素的序列 和n个元素的排列建立一一对应关系，从而得到一种生成排列的算法序数法。规则：令n个元素为1，2,n. 是这n个数的任意一个排列，我们可以找到一个序列和它对应，其中 可以看作是排列P中数i+1所在位置右边比i+1小的数的个数。 1.5.2字典序法一般而言，设P是1,n的一个全排列。P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1PnI) j=maxi|PiPjIII) 对换Pj，Pk，IV) 将Pj+1Pk-1PjPk+1Pn翻转，P= P1P2Pj

2、-1PkPnPk+1PjPk-1Pj+1即P的下一个1.5.3邻位对换法序数法和字典排序法，求下一个排列在不进位的情况下很容易。这就启发我们，能不能设计一种算法，下一个排列总是上一个排列某相邻两位对换得到的。活动状态以12 3 4为初始排列，箭头所指一侧，相邻的数比它小时，则称该数组处在活动状态，1 2 3 4的2，3，4都处于的活动状态。算法步骤（1）若P=P1P2Pn 没有处于活动则结束（2）将处于活动状态的各数中值最大者设为m,则m和它的箭头所指一侧相邻的数互换位置， (3) 比m大的所有数的箭头改变方向，即 改成或改成，转向（1）。 求 839647521下一个排列求 93864752

3、1下一个排列1.6 组合的生成 对于某一个特定组合的生成，我们可以看出组合的生成比较容易，规律很容易找到。例如，1,2,3,4中取3个组合：123 ，124，134，2341.6 组合的生成设从1,n中取r元的组合全体为C(n,r).1)C1C2CrC(n,r).不妨设C1C2CriCi(nr+i), i=1,2,r2)令j=maxi|Cinr+i.则C1C2Cr的下一个组合为C1C2Cj-1(Cj+1)(Cj+2)(Cj + r-j+1)显然，1 2 r的序号为0，n-r+1 n-r+2 n的序号为( )1 n r1.6 组合的生成例 在1,2,9中选五个元素的一个组合 34789的下一个组

4、合是什么？1.7若干等式及其组合意义组合意义或组合证明，含意强弱的不同。承认组合证明与其他证明有相同的“合法性”。1.7若干等式及其组合意义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.7若干等式及其组合意义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-

5、1)中方案，故C(n,r)=C(n-1,r)+C(n-1,r-1)1.7若干等式及其组合意义3.( )+( )+( )+( )=( ) (1.7.3)n n+1 n+2 n+r n+r+10 1 2 r r1.7若干等式及其组合意义 从(0,0)到(n+1,r),过且仅过一条带箭头的边,而过这些边的路径有(从下到上) ( ),( ),( )故有.( )+( )+( )+( )=( ) n n+1 n+rn n n n n+1 n+2 n+r n+r+1n n n n nr (n+1,r) . . .(0,0) n n+11.7若干等式及其组合意义4. ( )( )=( )( ) (1.7.4)

6、选政治局,再选常委,n个中央委员选出l名政治局委员,再从其中选出r名常委选常委,再选非常委政治局委员两种选法都无遗漏,无重复地给出可能的方案，应该相等。n l n n-rl r r l-r1.7若干等式及其组合意义5. ( )+( )+( )=2 , m0, (1.7.5)证1(x+y) =()x y ,令x=y=1,得(1.7.5)组合证1 1,m的所有方案.每一子集都可取k1,m或不取.这样有2 个方案.另可有0-子集(空集),1-子集,m-子集.组合证2 从(0,0)走m步有2 种走法,都落在直线x+y=m上,而到(m,0),(m-1,1),(m-2,2),(2,m-2),(1,m-1)

7、,(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.7若干等式及其组合意义6. ( )-( )+( )-( )=0 (1.7.6)证1 在(x+y)=( )x y 中令x=1,y=-1即得.n n n n0 1 2 n n n-k knk nk=01.7若干等式及其组合意义证2 在1,n的所有组合中,含1的组合不含1的组合.有11对应关系。在任一含1组合及与之对应的不含1组合中，必有一奇数个元的组合与一偶数个元的组合。将含奇数个元的组合做成集，将含偶数阁

8、元的组合做成另一集。此二集的元数相等。()=()n ni ii奇 i偶1.7若干等式及其组合意义7. ( )=( )( )+( )( )+( )( ) (1.7.7) 即Vandermonde恒等式证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

9、,0) rl=01.8应用举例例 脱氧核糖核酸(DNA)的分子由A(腺嘌呤),G(鸟嘌呤),C(胞嘧啶)和T(胸腺嘧啶)4种碱基核糖核苷酸，以不同数目和种类排列成两条多核苷酸单链，这两条单链之间通过氢键把配对的碱基连接起来，形成双螺旋结构。连接过程总是A和T配对，G和C配对。显然长度为n的核苷酸链共有4 种不同方式。n1.8应用举例生物遗传信息是由DNA分子中4个碱基核苷酸象电报密码似的以不同的排列顺序记录下来，它载着人类的全部基因或全部遗传信息。所谓基因就是DNA上一小段, 平均长度为900-1500个碱基对。人的DNA约有310 碱基对。核糖核酸(RNA)也是一种遗传物质，它是由A,G,C

10、,U(尿嘧啶)4种碱基核苷酸排列而成的多核苷酸单链。91.8应用举例通过基因将它的遗传信息传递给RNA,然后再传给蛋白质来表现其功能。(1)蛋白质分子中有20种氨基酸，在RNA 中以一定顺序相连的3个核苷酸决定1种氨基酸，三联体遗传密码有4 =64个排列方式。它保证了20种氨基酸密码的需要。(2)例如RNA链：CCGGUCCGAAAG酶将它分解成为G片断(即利用G将RNA分解)。CCG,G,UCCG,AAAG.31.8应用举例显然有4!=24种不同的RNA链有与此相同的G片段。若利用U,C酶将上述的RNA链分解成U,C片段：C,C,GGU,C,C,GAAAG由于GAAAG片段只能在最后出现，而且 C出现4次，故有C(5,4)=5种不同的核苷酸链，它的U,C片段是上述的C,C,C,C,GGU, GAAAG,它们是1.8应用举例CC