排列與逆序排列與逆序將由n個不同的自然數m1,m2,…,mn組成的一個有序數組稱為一個n級排列.由于這里主要考慮這n個數的前后次序關系，不妨設這n個數就為1,2,…,n.于是，上面的定義可以寫成如下定義.定義1-3排列與逆序定義1-3′將由自然數1,2,…,n組成的一個有序數組稱為一個n級排列.人們通常按照定義1-3′給出n級排列，并且具體寫n級排列時，在不發(fā)生混淆的情況下，只是將數字并排放在一起.例如，23541即為一個5級排列.由中學排列組合的知識可知，n級排列的總個數為n·(n－1)·(n－2)·…·2·1=n!排列與逆序試寫出所有的3級排列.解由上面的討論可知，總共有3!=6個不同的3級排列，它們分別是123,132,213,231,312,321注意在【例1-1】的3級排列里，除了123中的數是按從小到大的遞增順序排列以外，其余的排列中，都有較大的數排在較小的數前面.例如，213中，2比1大，但是2排在1的前面.同樣，在n級排列中，也只有排列12…n中的數是按從小到大的遞增順序排列的，其他的排列都或多或少地破壞了這種順序.【例1-1】排列與逆序定義1-4在一個n級排列中，如果某兩個數的前后位置與大小順序相反，即前面的數大于后面的數，那么就稱它們?yōu)橐粋€逆序，一個排列中逆序的總數就稱為這個排列的逆序數.通常，將j1j2…jn的逆序數記成τ(j1j2…jn)，并且我們將逆序數為奇數的排列稱為奇排列，將逆序數為偶數的排列稱為偶排列.排列與逆序一般地，可以利用如下方法計算一個n級排列的逆序數：設j1j2…jn是一個n級排列，如果把排在ji（i=1,2,…,n）前面且比ji大的數的個數記為si，則j1j2…jn的逆序數為

τ(j1j2…jn)=s1+s2+…+sn例如，τ(23541)=0+0+0+1+4=5，τ(32541)=0+1+0+1+4=6，因此，23541是一個5級奇排列，而32541是一個5級偶排列.更一般地，τ(12…n)=

0+0+…+0=0，從而12…n是一個n級偶排列.一般地，在n!個n級排列中，偶排列和奇排列各占一半.為了說明這個事實，還需要進一步研究排列的奇偶性.排列與逆序定義1-5在一個n級排列中，如果把這個排列里的任意兩個數i和j交換一下位置，而其余的數保持不動，那么就得到了一個新的n級排列.對排列施行這樣的一個變化稱為n級排列的一次對換，用符號(i,j)表示.例如，經過對換(2,3)，可以將排列23541變成32541，將52431變成53421.容易驗證，對一個排列連續(xù)實施兩次相同的對換，就將這個排列還原，變回原來的排列了.由此可知，一個對換把全部n級排列兩兩配對，使每兩個配成對的n級排列在這個對換下互變.排列與逆序關于排列的奇偶性，可以不加證明地給出如下定理.定理1-1任何一個對換都可以改變排列的奇偶性，也就是說，經過一次對換，偶排列變成奇排列，奇排列變成偶排列.這個定理說明了：當n≥2時，n級排列的奇排列和偶排列個數相等，各為n!2個.定理1-2設j1j2…jn是任意一個n級排列，則j1j2…jn與12…n可以經過一系列對換互變，并且所作對換的個數n(j1j2…jn)的奇偶性與τ(j1