奇排列

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

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

註：n級排列的總數是

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

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

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

註：排列 的逆序數記為

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

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

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

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

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

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

經過對換變成排列（2）

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

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

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

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

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

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

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

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

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

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

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

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

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

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