[科普中國]-奇排列

逆序數為奇數的排列稱為奇排列。經過一次對換，奇排列變成偶排列，偶排列變成奇排列。在全部n級排列中，奇、偶排列的個數相等，各有（n！/2 ）個。任意一個n級排列與排列 12...n 都可以經過一系列對換互變，并且所作對換的個數與這個排列有相同的奇偶性。1

定義n級排列定義1 由1，2，...，n組成的一個有序數組稱為一個n級排列。1

例如，2431是一個四級排列，45321是一個五級排列。

注：n級排列的總數是

顯然， 也是一個n級排列，這個排列具有自然順序，就是按遞增的順序排起來的；其它的排列都或多或少地破壞自然順序。1

逆序數定義2 在一個排列中，如果一對數的前后位置與大小順序相反，即前面的數大于后面的數，那么它們就稱為一個逆序，一個排列中逆序的總數就稱為這個排列的逆序數。1

例如2431中，21,43，41,31是逆序，2431的逆序數就是4；而45321的逆序數是9.

注：排列 的逆序數記為

奇排列定義3 逆序數為奇數的排列稱為奇排列。（相應地，逆序數為偶數的排列稱為偶排列。）1

例如，2431是偶排列，45321是奇排列， 的逆序數是零，因而是偶排列。

注：1）考慮由任意n個不同的自然數所組成的排列，一般地也稱為n級排列。對這樣一般的n級排列，同樣可以定義上面這些概念。

2）對換：把一個排列中某兩個數的位置互換，而其余的數不動，就得到另一個排列。這樣一個變換稱為一個對換。1

性質定理1 對換改變排列的奇偶性。（經過一次對換，奇排列變成偶排列，偶排列變成奇排列。）1

證明：先看一個特殊的情形，即對換的兩個數在排列中是相鄰的情形。排列（1）

經過 j，k對換變成排列（2）

這里“ ”表示那些不動的數。顯然，在排列（1）中如 j，k 與其他的數構成逆序，則在排列（2）中仍然構成逆序；如不構成逆序則在（2）中也不構成逆序；不同的只是 j，k 的次序。如果原來j，k 組成逆序，那么經過對換，逆序數就減少一個；如果原來 j，k不組成逆序，那么經過對換，逆序數就增加一個。不論增加1還是減少1，排列的逆序數的奇偶性總是變了。因此，在這個特殊的情形，定理是對的。

再看一般的情形。設排列為（記為（3））

經過 j，k 對換，排列（3）變成排列（記為（4））

不難看出，這樣一個對換可以通過一系列的相鄰數的對換來實現。從（3）出發(fā)，把k 與 is對換，再與is-1 對換 ，也就是說，把k 一位一位的向左移動。經過s+1次相鄰位置的對換，排列（3）就變成排列（記為（5））

從（5）出發(fā)，再把j 一位一位地向右移動，經過s次相鄰位置的對換，排列（5）就變成了排列（4）。因此，j，k 對換可以通過2s+1次相鄰位置的對換來實現。2s+1是奇數，相鄰位置的對換改變排列的奇偶性。顯然，奇數次這樣的對換的最終結果還是改變奇偶性。

定理2 在全部n級排列中，奇、偶排列的個數相等，各有個。1

證明：假設在全部n級排列中共有s個奇排列，t個偶排列。將s個奇排列中的前兩個數字對換，得到s個不同的偶排列。因此s≤t. 同樣可證t≤s，于是s=t，即奇、偶排列的總數相等，各有 個。

注：定理2保證了n階行列式的展開式的n! 項中正負項各半。2

定理3 任意一個n級排列與排列都可以經過一系列對換互變，并且所作對換的個數與這個排列有相同的奇偶性。1

證明：我們對排列的級數n作數學歸納法，來證任意一個n級排列都可以經過一系列對換變成 .

1級排列只有一個，結論顯然成立。

假設結論對n-1級排列已經成立，現在來證對n級排列的情形結論也成立。

設 是一個n級排列，如果 ，那么根據歸納法假設，n-1級排列 可以經過一系列變換變成 ，于是這一系列對換也就把 變成 . 如果 ，那么對 作jn，n對換，它就變成 ，這就歸結成上面的情形，因此結論普遍成立。

相仿地， 也可用一系列對換變成 ，因為 是偶排列，所以根據定理1，所做對換的個數與排列 有相同的奇偶性。

本詞條內容貢獻者為:

孫和軍 - 副教授 - 南京理工大學