離散數(shù)學中的排列

1、 排列 在實際中，很多問題和計數(shù)有關. 而大量的計數(shù)問題分為兩類： 1. 計算事物的有序安排或有序選擇數(shù). 這又分為如下兩種情況： a. 不允許任何事物重復；b. 允許事物重復 2. 計算事物的無序安排和無序選擇數(shù). 這又分為如下兩種情況： a.不允許任何事物重復；b. 允許事物重復 第一類就是本節(jié)要討論的排列問題，第二類就是下節(jié)要討論的組合問題. 其實，一一對應也是計數(shù)常用的一種技巧. 最有趣而且直觀的一個例子， 比如有100位乒乓球選手通過淘汰賽，最后產(chǎn)生一名冠軍，先分50對比賽，第 一輪結束留下50名勝利者. 第二輪將50名第一輪勝出的選手分成25對進行比賽， 25名勝利者參加第三輪比賽

2、，分12組，其中一人直接參加第四輪比賽. 第四 輪開始時13名選手，分6對比賽，一人直接進入第五輪，第五輪有7人，分3組， 同樣有一個直接進入第六輪；第六輪有四人，分兩組，其中勝者參加最后的 決賽. 現(xiàn)統(tǒng)計共進行多少對比賽，總比賽臺數(shù)50+25+12+6+3+2+1=99. 其實比賽的臺數(shù)和每一場比賽淘汰一名選手一一對應，100名選手要選出 一名單打冠軍，必須淘汰99名，故必須進行99臺比賽. 1000位選手要選出一 名單打冠軍，不必猶豫回答要進行999臺比賽. 研究排列問題的主要目的是求出根據(jù)已知的條件所能作出的不同排列的種數(shù). 排列按照元素的排列方式可分為三種排列：1.線排列；2.圓排列；

3、3.重排列. 一、線排列一、線排列 定義定義1.1 1.1 設 是具有 個元素的集合， 是正整數(shù). 從這 個 不同的元素中取 個按照一定的次序排列起來 ，稱為集合 的 -排列. 其排列數(shù)記為 . 換言之， 的 -排列為 的 有序子集. 另外，為了處理問題的方便，我們定義 例如，集合 ，則集合 有6個2-排列： 和 6個3-排列： ，故有 . 定理定理1.1 1.1 對于正整數(shù) ，有 (1.3) 證明證明：在構造集合 的 -排列時，可以從集合 的 個元素 中 任選一個元素作為排列的第一項，這可以有 種選法. 當?shù)谝豁椷x定后，又可以 從剩下的 個元素中任選一個元素作為排列的第二項，這又有 種選法.

4、 照此下去，只要選定了前 項，則就有 種選法來選擇排列的第 項. 由乘法法則，這 個項可以有 種選法. 故有 12 , n Aa aanrn r()rnAr ,P n r AAr 10 , 0 nr P n r nr , ,Aa b cA,ab ac ba ca bc cb ,abc acb bac bca cab cba3,26,3,36PP , ,n r rn ! ,11 ! n P n rn nnr nr A r An 12 , n a aa n 1n1n 1r 1nr r r 11n nnr ! ,11 ! n P n rn nnr nr 證畢. 注意，當 時，則稱 的 -排列為全排列

5、，于是由公式(1.3)有 推論推論1 1 當 時，有 (1.4) 證明證明：在集合 的 個元素中，任何一個元素都可以排在它的 -排列的首 位，故首元有 種取法. 當首元取定后，其他位置上的元正好是從 的另 個 元素中取 個的排列，因此有 種取法. 由乘法規(guī)則知有 證畢. 推論推論2 2 當 時，有 (1.5) 證明證明：當 時，把集合 的 -排列分為兩大類：一類含有 中的某固定 元，比如是 ；另一類不含 . 如果先從 中選取 個元進行排列， 共有 個這樣的排列. 對于每一個上述排列，可將 放入而得到 第一類排列. 由于對任一上述排列， 都有 種放入方法，因此第一類排列 rnA n ,12 1!

6、P n nn nn 2nr ,1,1P n rnP nr An r nA1n 1r 1,1P nr ,1,1P n rnP nr 2nr ,1,11,P n rrP nrP nr 2r ArA 1 a 1 a 1 Aa 1r 1,1P nr 1 a 1 ar 共有 個，再由加法法則有 證畢. 例1 由數(shù)字1,2,3,4,5,6可以構成多少個數(shù)字互不相同的四位數(shù). 解：由于所有的四位數(shù)字互不相同，故一個四位數(shù)就是集合 的一個4-排列，因而符合題目要求的四位數(shù)個數(shù)是 例2 將具有9個字母的單詞FRAGMENTS進行排列，要求字母A總是緊跟在字 母R的右邊，問有多少種這樣的排法？ 解：由于A總在R的

7、右邊，故這樣的排列可以看成是具有8個元素的集合 的一個全排列，其個數(shù)為 例3 5面不同顏色的旗幟，20種不同的盆花，排成兩端是兩面旗幟，中間 放3盆花的形式，試問有多少種不同的方案數(shù)？ 解：5面旗取2面的排列數(shù)為 20盆花取3盆的排列數(shù)為 根據(jù)乘法法則，共有的方案數(shù)為 1,P nr ,1,11,P n rrP nrP nr 1,2,3,4,5,6 6! 6,4360 64 ! P , ,F RA G M E N T S8,88!40320P 5,25 420P 20,320 19 186840P 20 6840136800N 例4 求2000到7000間的偶數(shù)中，由不同數(shù)字組成的4位數(shù)的個數(shù).

8、 解：設這4位數(shù)為 ， 由于偶數(shù)，故 只能取0,2,4,6,8五個數(shù)字. 限制在2000到7000之間的數(shù)，故 只能取2,3,4,5,6五位數(shù)字. 分別討論 如下： (1) 當 取2,4或6時， 只能有4種選擇，而 則只能從余下的8位數(shù)字取 2個進行排列，故符合條件的數(shù)，根據(jù)乘法法則有 個 (2) 若 不取2,4,6，則 有5種選擇， 為余下的8位數(shù)字取2個進行排列， 故有符合條件的偶數(shù)個數(shù)為 個 根據(jù)加法法則，所求的偶數(shù)數(shù)目為 672+560=1232個 例5 求由1,3,5,7不重復出現(xiàn)組成的整數(shù)的和. 解：這樣的整數(shù)最多只能有4位數(shù). 1位數(shù)4個：1,3,5,7， 2位數(shù)的個數(shù)為 個：1

9、3,15,17,31,35,37,51,53,57,71,73,75， 3位數(shù)有 個：135,137,315,317,513,517,713,715 153,173,351,371,531,571,731,751 157,175,357,375,537,573,735,753 3210 n n n n 0 n 3 n 3 n 0 n 2 1 n n 3 48,212 8 7672P 3 n 0 n 2 1 n n 2 58,2560P 4,212P 4,324P 4位數(shù)有 個：1357,1375,1537,1573,1735,1753 3157,3175,3517,3571,3715,3751

10、 5137,5173,5317,5371,5713,5731 7135,7153,7315,7351,7513,7531. 求這些數(shù)的和. 直接對這些數(shù)求和不是目的，這是枚舉，枚舉只是在毫無 辦法時才用. 現(xiàn)在設法找出其中的規(guī)律性來. 注意個位、十位、百位、千位中 1,3,5,7的分布特點，以三位數(shù)為例，第1位為1的135,153,137,173,157,175， 其中35,53,37,73,57,75是從3,5,7中取兩個的排列. 令 表示個位數(shù)之和， 表示十位數(shù)之和，同理 分別是百位、千位數(shù)之 和. 求得 ，則問題所求的和數(shù) (1) 的計算： 一位數(shù)中個位數(shù)之和=1+3+5+7=16 兩位

11、數(shù)中個位數(shù)之和= 三位數(shù)中個位數(shù)之和= 四位數(shù)中個位數(shù)之和= (2) 的計算 兩位數(shù)中十位數(shù)之和= 三位數(shù)中十位數(shù)之和= 四位數(shù)中個位數(shù)之和= 4!24 1 S 2 S 34 ,S S 1234 ,S S S S 1234 101001000SSSSS 1 S 3,1163 1648P 3,2166 1696P 3,3166 1696P 1 16 48 96 96256S 2 S 3,1163 1648P 3,2166 1696P 3,3166 1696P 2 48 96 96240S (3) 的計算： 三位數(shù)中百位數(shù)之和= 四位數(shù)中百位數(shù)之和= (4) 的計算： 四位數(shù)中千位數(shù)之和= 所以

12、3 S 3,2166 1696P 3,3166 1696P 3 96 96 192S 4 S 3,3166 1696P 256240 10 192 10096 1000S 2562400 1920096000 117856 二、圓排列二、圓排列 定義定義1.2 1.2 從集合 的 個不同元素中取出 個元素按照某 種順序（如逆勢針）排成一個圓圈，稱這樣的排列為圓排列（或稱循環(huán)排列）. 一般用 表示. 圓排列與線排列不同之處在于圓排列頭尾相鄰，比如4個元素 的 排列 是不同的排列，但將它圍成圓排列，其實是一回 事，屬于同一個圓排列，如圖1-1 而且不難理解 定理定理1.2 1.2 集合 中的 個元

13、素的 圓排列的個數(shù)為 (1.6) 證明：由于把一個圓排列旋轉(zhuǎn)所得到的另一個圓排列視為相同的圓排列， 因此排列 在圓排列 中是同一個，即一個圓排列可以產(chǎn)生 個線排列，而總共有 個線排列. 故圓排列的個數(shù)為 12 , n Aa aa n r ,Q n r , , P n r Q n r r , , ,a b c d ,abcd dabc cdab bcda ,!P n rrnr nr An r 122313412121 , rrrrr a aaa aa aa aa a aa a aa r ,P n r ,!P n rrnr nr 例6 4男4女圍圓桌交替就坐有多少種方式？ 解：顯然，這是一個圓排列

14、問題. 先讓4個男的圍圓桌而坐，由公式(1.6) 共有 種就坐方式. 然后加入一個女的進去就坐就有4種方式，加入第二個女 的又有3種方式，加入第三個女的又有2種方式，加入第四個女的只有一種方式. 由乘法法則知，4男4女圍圓桌交替就坐的方式數(shù)為 例7 5個男生，3個女生圍一圓桌而坐. 若沒加任何要求，則 . 若要求男生 不和女生 相鄰而坐有多少種方案？若要求 3個女生不相鄰，又有多少方案數(shù)？ 解：方法1 先將 排除在外，7個人圍一圓桌而坐，然后 插入. 插入 有5種選擇，故 和 不相鄰的方案數(shù)為 . 方法2 先求出 和 相鄰而坐的方案數(shù)： ， 5040-1440=3600. 若3位女生不相鄰.

15、先考慮5個男生圍圓桌而坐的方案數(shù)，然后3個女生依次 插入，其方案數(shù)位 例8 對夫妻圍一桌而坐，求每對夫妻相鄰而坐的方案數(shù). 解：夫妻相鄰而坐但可交換位置所求的方案數(shù) 4! 4 (4! 4) 4 3 2 1144 8,87!5040Q 1 G 1 B 1 G 1 G 1 G 1 B 1 G5 6!5 7203660 1 B 1 G2 6!2 7201440 4! 5 4 31440 n 1 ! 2 n Nn 例9 (1)有12個人分兩桌，每桌6人，圍成圓桌而坐，問幾種安排方案？ (2)若有12對夫妻平分為兩桌，圍圓桌而坐問幾種方案？ 解：(1)根據(jù)乘法法則，從12個人中取6個組各作圍圓桌排列，故

16、 (2) . 三、重排列 上面我們討論了從集合 （ 中的元素是互不相同的）中選 個元素進行排列， 在每種排列中每個元素至多只出現(xiàn)一次的情況. 現(xiàn)在考慮元素允許重復出現(xiàn)的 情況，即考慮在重集 中選 個元素進行的排列. 定義定義1.3 1.3 從重集 中選取 個元素按照一定的順序 排列起來，稱這種 -排列為重排列. 定理定理1.3 1.3 重集 的 -排列的個數(shù)為 . 證明：構造集合 的 排列可用如下方法：在選擇 -排列的第一項時， 可以從 個元素中任選一個，因此有 種選法. 在選擇 -排列的第二項時，由 于可以重復選取，仍有 種選法. .同理，在選擇這樣排列的第 項時仍有 種選法，由乘法法則可求

17、得 -排列的數(shù)目為 . 這個定理也可敘述為：在一個具有 個不同元素的集合 中，每一個元素 都可以重復選取無限多次的 -排列的個數(shù)等于 . 同時， 的 個不同元素的 重復數(shù)都至少是 ，則定理的結論仍然成立. 2 12,65!C 2 6 12,65!2C A Ar 1122 , nn Bka kakar 1122 , nn Bk b kbkb r r 12 , n Bbbb r r n Brr nn r n r nr r n B r r n Bn r 例10 由1,2,3,4,5,6這六個數(shù)字能組成多少個五位數(shù)？又可組成多少大于 34500的五位數(shù)？ 解：一個五位數(shù)，數(shù)字可以重復出現(xiàn)，這是一個重排

18、列問題. 由于五位數(shù)的每一位在重集 中有6種選擇， 由定理1.3知，這六個數(shù)字可以組成 個五位數(shù). 又大于34500的五位數(shù)可由下面三種情況組成： 1）萬位上的數(shù)字是4,5或6，其余四位上的數(shù)字中的每一個數(shù)字都可以從重 集 中選取6個數(shù)字，由乘法法則知，共有 個這樣的數(shù). 2）萬位數(shù)是3，千位上是5,6，其余三位上的數(shù)字中的每一個都可以從重集 中選取6個數(shù)字，故共有 個這樣的數(shù). 3）萬位和千位上的數(shù)字分別是3和4，百位上的數(shù)字是5,6，其余兩位上的 數(shù)字中的每一個都可以從重集 中選取6個數(shù)字，故共有 個這樣的數(shù). 由 加法法則知，大于34500的五位數(shù)的個數(shù)為 定理定理1.4 1.4 重集

19、的全排列的個數(shù)為 式中 . 1,2,3,4,5,6B 5 6 B 4 3 6 B 3 2 6 B 2 2 6 432 3 62 62 64392 1122 , kk Bn b nbnb 12 ! ! k n nnn 1 k k i nn 證明：將 中 個 分別賦予上標 ，即 . 這樣一來，重集 就變成具有 個不同的元素的集合 . 顯然，集合 的全排 列個數(shù)為 . 又由于 個 賦予上標 的辦法有 種，于是對于重集 的任 一個全排列，都可以產(chǎn)生集合 的 個排列（由乘法法則），故 重集 的全排列個數(shù)為 證畢. 例11 由四面紅旗，三面藍旗，二面黃旗，五面綠旗可以組成多少由14 面旗子組成的一排彩旗？

20、 解：這是一個重排列問題，它是求重集4紅旗,3藍旗,2黃旗,5綠旗 的全排列的個數(shù)，由定理1.4知，組成一排彩旗的種數(shù)為 B i n i b1,2, i n 12 121212 111222 , k nnn kkk Ab bbbbbbbb B 12k nnnn A !n i n1,2, i n i b! i nB A 12 ! k n nn B 12 ! ! k n nnn 14! 4! 3! 2! 5! 例12 用字母 組成五個字母的符號，要求在每個符號里， 至多 出現(xiàn)2次， 至多出現(xiàn)1次， 至多出現(xiàn)3次，求此類符號的個數(shù). 解：這也是一個重排列的問題. 根據(jù)分析，符合題目要求的符號只有三種

21、 情況： 和 . 由定理1.4知，各 種情況對應的符號個數(shù)分別為 ， 和 由加法法則知，此類符號的個數(shù)為 , ,A B CA BC 2,0,3, 1,1,3ABCABC2,1,2ABC 5! 2!1! 2! 5! 1!1! 3! 5! 2! 0! 3! 5!5!5! 60 2! 0! 3!1!1! 3!2!1! 2! 排列的生成算法 若說以前討論了排列的個數(shù)，這一節(jié)則將這些排列一一羅列出來. 實際工作中有時要在計算機上模擬各種排列狀態(tài)下出現(xiàn)的情況加以分析， 下面介紹若干排列的生成算法. 序數(shù)法 同樣理由可得 代人上式可得 可得0到 的整數(shù) 可以唯一地表示為 其中 滿足 . !=1 !111 !

22、 11 !1 ! nn nnn nnn 1 !=22 !2 !nnnn 1 1 !=11 !22 !2 ! 11 !22 !33 !2 2! 2! ! 1 ! 111 !22 !33 !2 2! 1 1! n k nnnnnn nnnnnn k k nnnnnnn ! 1n m 1221 1 !2 !2! nn mananaa k a0,1,2,1 k ak kn 所以可以證明0到 的 個整數(shù)和序數(shù) 一一對應. 下面討論從 求序數(shù) 的方法. 除以2，令 ，故 除以2，余數(shù) 即 . 類似 令 . ! 1n !n 1221 , nn aaa a m 1221 1 !2 !2! nn mananaa

23、 1221 , nn aaa a m 1 nm 1 n 1 r 1 a 1 212211 1 !2 ! , 222 nn nnn naaa ra 2 312322 1 !2 ! , 333 nn nnn naaa ra 1 ,1,2,1 1 i iii n nra in i 1654321 1 2654321 2 3654322 3 46 40006!5!4!3!2! 40006!5!4!3! 2000,0 222222 20006!5!4! 666,2 333!3!3! 6666 166 44 naaaaaa n naaaaa a n naaaa ar n na 5433 4 56544 6

24、655 766 !5! ,2 4!4! 1666! 33,1 555! 33 5,3 6 5 0,5 7 aa ar n naa ar na ar nar 例13 ，以 作為例子，方法可推及一 般. 令 所以 4000,6!40007!m 4000n 40005 6! 3 5! 4! 2 3! 2 2! 綜上所述，滿足條件 的序數(shù) (*) 序數(shù)和 間 個整數(shù)一一對應. 下面試圖將 個元素的全排列和序數(shù) 建立起一一對應關系，不失一般性， 個元素不妨令 為 . 對應的規(guī)則如下：式(*)中第一個數(shù) 表示排列中數(shù) 的右（或左） 端比 小的數(shù)的個數(shù)，將 在排列的位置確定下來，接著取 ，它表示在排列 中

25、這個數(shù)在排列中的右（或左）端比 小的數(shù)的個數(shù)，依此類推， 表 示 這個數(shù)在排列中的位置其右方（或左方）比 小的數(shù)的個數(shù)， . 以1,2,3,4的排列4213為例，排列4213，4的右方比它小的數(shù)有3位，故 3的右方比3小的數(shù)為0，故 ；2的右方比2小的數(shù)為1，故 . 故排列4213 對應于序數(shù)(301)，反過來從(301)可推得排列4213. ，故4在排列中所在位 右方比4小的數(shù)有3個，故在下列4格的排列中第一格為4. ，故3的右方?jīng)]有比它小的，故在第4格填上3， ，表示2的右方有一個 比2小的，故在第2格填上2，剩下的一格填上1，便得排列4213. 現(xiàn)將 的序 數(shù) 與對應的排列，列于下表.

26、0,1,2,1 i ai in 1221 , nn aaa a !n0! 1n n 1221 , nn aaa a n i 1,2,n 1n a n nn 2n a 1n1n i a 1i 1i 1,2,2,1inn 3=3 a 2=0 a 1=1 a 3=3 a 4 42 21 13 3 2=0 a 1=1 a =4n 321 a a a N N排列排列N N排列排列 10 0 01 2 3 4132 0 01 4 2 3 20 0 12 1 3 4142 0 12 4 1 3 30 1 01 3 2 4152 1 01 4 3 2 40 1 12 3 1 4162 1 12 4 3 1 5

27、0 2 03 1 2 4172 2 02 4 1 2 60 2 13 2 1 4182 2 13 4 2 1 71 0 01 2 4 3193 0 04 1 2 3 81 0 12 1 4 3203 0 14 2 1 3 91 1 01 3 4 2213 1 04 1 3 2 101 1 12 3 4 1223 1 14 2 3 1 111 2 03 1 4 2233 2 04 3 1 2 121 2 13 2 4 1243 2 14 3 2 1 上面的討論將“右”改為“左”也可以得另一種對應關系. 字典序法： 以下圖為例，高度為4的樹，按從樹根到樹葉讀出邊的標號順序得一排列， 自左至右，依此

28、為 1234,1243,1324,1342,1423,1432,4321 它是按字典的順序排列的. 由前面一個排列 到下一個排列的生成算 法，歸納其規(guī)律為： 1 12 23 3 4 4 2 2 3 34 4 1 13 3 4 4 1 1 2 24 41 12 2 3 3 3 34 42 24 4 2 2 3 33 34 41 14 41 13 32 24 41 1 4 4 1 1 2 2 2 23 31 1 3 3 1 1 2 2 4 43 34 42 23 32 24 43 34 41 13 31 14 42 24 41 12 21 13 32 23 31 12 21 1 1234 p p

29、p p S1.求滿足關系式 的 的最大值，設為 ，即 S2.求滿足關系式 的 的最大值，設為 ，即 S3. 與 互換得 S4.令 的 的順序逆轉(zhuǎn)便得下一個排列 例如 S1. S2. S3. 和 互換得4321 S4. 將4321中321的順序逆轉(zhuǎn)得下一個排列4123 以 的排序利用字典序生成法，可從 開始，直到 結束，即直到不存在 為止. 換位法： 下面介紹一種比較直觀的排列生成法，以 為初始排列，箭頭所指一 側，相鄰的數(shù)若比它小時，則稱該數(shù)處在活動狀態(tài)， 的2,3,4都處在活動 狀態(tài). 下面敘述從 生成下一個排列的步驟： S1.若 沒有數(shù)處于活動狀態(tài)則結束. S2.將處于活動狀態(tài)的各數(shù)中值最大者設為 ，則 和它的箭頭所指一側相 1jj pp j i 1 max jj ij pp 1ik pp kh 1 max ik hk pp 1i p h p 12n p pp 1211iiin p ppp pp 1iin p pp 1211inni p ppp pp 1234 3421p p p p 1 max2 jj ij pp 1 max2 ik hk pp 1 p 2 p 12n 121n n 1jj pp 1,2,n 1234