1.2　排列

1.2.1　排列的概念

定義1　由1，2，…，n這n個不同的數碼組成的一個有序組稱為一個n級排列.

顯然，1，2，…，n也是一個n級排列，這個排列具有自然順序，即按遞增的順序排列，其他的排列或多或少地破壞自然順序.

例如，12345，14532，13452都是由1，2，3，4，5組成的一個5級排列.

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

排列j1j2…jn的逆序數記為

τ（j1j2…jn）.

例如上面的第一個排列的逆序數τ（12345）=0，因為不存在較大的數字排在較小的數字前面，都是按自然順序排列的，所以沒有逆序，逆序數為0.

一般地，將1，2，…，n這種按照從小到大的自然順序排成的排列稱為標準排列.

例　計算排列14532的逆序數.

解　第一個位置是1，1小于后面的所有數字，所以這里有0個逆序；

第二個位置是4，后面比4小的數有3，2，所以這里有2個逆序；

第三個位置是5，后面比5小的數有3，2，所以這里有2個逆序；

第四個位置是3，后面比3小的數有2，所以這里有1個逆序；

第五個位置是2，2后面沒有數字，所以這里有0個逆序；得，這個排列的逆序數τ（14532）=0+2+2+1+0=5.

定義3　逆序數為偶數的排列稱為偶排列；逆序數為奇數的排列稱為奇排列.

第一個排列12345是偶排列，第二個排列14532是奇排列.

應該指出，同樣可以考慮由任意n個不同的自然數所組成的排列，一般也稱為n級排列，對這樣一般的n級排列，同樣可以類似地定義上面這些概念.