關于十五子的游戲

我們先來介紹一點組合數學的知識.有一堆東西，需要把它們排列出來，我們可以給每一個東西編一個號，例如按某種規定依次編為1，2，…，n.我們稱這個從小到大的序列（1，2，…，n）為順序列，但若出現一個大的數排在小的數的前面，例如（1，3，2，4，…，n），這是一個在順序上發生雜亂的序列，我們不妨稱之為非順序列.人們規定：若在一個序列中，有一個數排在另一個比它還小的數之前，我們稱之為一個倒置.例如非順序列（1，3，2，4，5）有一個倒置，又如（3，1，2，4，5）有兩個倒置，因為3不僅在2之前，而且還排在1之前，再如（3，2，1，4，5）有三個倒置，因為3排在1，2的前面，這有兩個倒置，2排在1的前面，又有一個倒置.我們稱順序列的倒置數為0 ，這是因為順序列沒有發生倒置.根據倒置數的不同，我們可以把所有的序列分成兩類，一類是倒置數為偶數的序列，我們稱之為偶置序列（順序列也應歸為偶置序列）；另一類是倒置數為奇數的序列，我們稱之為奇置序列.

設圖18是一個十五子游戲的初始位置，我們先把這15個數排成一個序列：5，1，4，3，10，8，2，13，6，9，14，

12，7，15，11. 5排在最前面，因而有1，2，3，4這四個比它小的數排在它后面，所以僅僅對5來講，有4個倒置，我們把4寫在橫線下和5對應；1排在第2，雖然5排在它前面，但這個倒置在計算5的倒置數時已經算過了，所以不再計算，而1的后面再也沒有比1小的數了，因而1的倒置數是0，把0記在1的下面；同理，4的后面比 4小的數有3和2兩個，因而在4的下面記下2；依此類推，得圖19.由于4+0+2+1+5+3+0+5+0+1+ 3+2+0+1+0= 27是一個奇數，因而這是一個奇置序列（請注意，這時我們是把空……