組合數(shù)學(xué)-第一章-排列組合6

1、1.5全排列的生成算法這里介紹全排列算法三種：(A)序數(shù)法(B)字典序法(C) 鄰位對換法1.5.1 序數(shù)法 把n-1個元素的序列 和n個元素的排列建立一一對應(yīng)關(guān)系，從而得到一種生成排列的算法序數(shù)法。規(guī)則：令n個元素為1，2,n. 是這n個數(shù)的任意一個排列，我們可以找到一個序列和它對應(yīng)，其中 可以看作是排列P中數(shù)i+1所在位置右邊比i+1小的數(shù)的個數(shù)。 1.5.2字典序法一般而言，設(shè)P是1,n的一個全排列。P=P1P2Pn=P1P2Pj-1PjPj+1Pk-1PkPk+1PnI) j=maxi|PiPjIII) 對換Pj，Pk，IV) 將Pj+1Pk-1PjPk+1Pn翻轉(zhuǎn)，P= P1P2Pj

2、-1PkPnPk+1PjPk-1Pj+1即P的下一個1.5.3鄰位對換法序數(shù)法和字典排序法，求下一個排列在不進位的情況下很容易。這就啟發(fā)我們，能不能設(shè)計一種算法，下一個排列總是上一個排列某相鄰兩位對換得到的?；顒訝顟B(tài)以12 3 4為初始排列，箭頭所指一側(cè)，相鄰的數(shù)比它小時，則稱該數(shù)組處在活動狀態(tài)，1 2 3 4的2，3，4都處于的活動狀態(tài)。算法步驟（1）若P=P1P2Pn 沒有處于活動則結(jié)束（2）將處于活動狀態(tài)的各數(shù)中值最大者設(shè)為m,則m和它的箭頭所指一側(cè)相鄰的數(shù)互換位置， (3) 比m大的所有數(shù)的箭頭改變方向，即 改成或改成，轉(zhuǎn)向（1）。 求 839647521下一個排列求 93864752

3、1下一個排列1.6 組合的生成 對于某一個特定組合的生成，我們可以看出組合的生成比較容易，規(guī)律很容易找到。例如，1,2,3,4中取3個組合：123 ，124，134，2341.6 組合的生成設(shè)從1,n中取r元的組合全體為C(n,r).1)C1C2CrC(n,r).不妨設(shè)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若干等式及其組合意義組合意義或組合證明，含意強弱的不同。承認(rèn)組合證明與其他證明有相同的“合法性”。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)的一個一一對應(yīng)。故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.設(shè)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名常委選常委,再選非常委政治局委員兩種選法都無遺漏,無重復(fù)地給出可能的方案，應(yīng)該相等。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對應(yīng)關(guān)系。在任一含1組合及與之對應(yīng)的不含1組合中，必有一奇數(shù)個元的組合與一偶數(shù)個元的組合。將含奇數(shù)個元的組合做成集，將含偶數(shù)閣

8、元的組合做成另一集。此二集的元數(shù)相等。()=()n ni ii奇 i偶1.7若干等式及其組合意義7. ( )=( )( )+( )( )+( )( ) (1.7.7) 即Vandermonde恒等式證1 從m個互異紅球和n個互異藍球中取r個球,按r個球中紅球的個數(shù)分類.組合證法: (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應(yīng)用舉例例 脫氧核糖核酸(DNA)的分子由A(腺嘌呤),G(鳥嘌呤),C(胞嘧啶)和T(胸腺嘧啶)4種堿基核糖核苷酸，以不同數(shù)目和種類排列成兩條多核苷酸單鏈，這兩條單鏈之間通過氫鍵把配對的堿基連接起來，形成雙螺旋結(jié)構(gòu)。連接過程總是A和T配對，G和C配對。顯然長度為n的核苷酸鏈共有4 種不同方式。n1.8應(yīng)用舉例生物遺傳信息是由DNA分子中4個堿基核苷酸象電報密碼似的以不同的排列順序記錄下來，它載著人類的全部基因或全部遺傳信息。所謂基因就是DNA上一小段, 平均長度為900-1500個堿基對。人的DNA約有310 堿基對。核糖核酸(RNA)也是一種遺傳物質(zhì)，它是由A,G,C

10、,U(尿嘧啶)4種堿基核苷酸排列而成的多核苷酸單鏈。91.8應(yīng)用舉例通過基因?qū)⑺倪z傳信息傳遞給RNA,然后再傳給蛋白質(zhì)來表現(xiàn)其功能。(1)蛋白質(zhì)分子中有20種氨基酸，在RNA 中以一定順序相連的3個核苷酸決定1種氨基酸，三聯(lián)體遺傳密碼有4 =64個排列方式。它保證了20種氨基酸密碼的需要。(2)例如RNA鏈：CCGGUCCGAAAG酶將它分解成為G片斷(即利用G將RNA分解)。CCG,G,UCCG,AAAG.31.8應(yīng)用舉例顯然有4!=24種不同的RNA鏈有與此相同的G片段。若利用U,C酶將上述的RNA鏈分解成U,C片段：C,C,GGU,C,C,GAAAG由于GAAAG片段只能在最后出現(xiàn)，而且 C出現(xiàn)4次，故有C(5,4)=5種不同的核苷酸鏈，它的U,C片段是上述的C,C,C,C,GGU, GAAAG,它們是1.8應(yīng)用舉例CC