鴛鴦の問題 その３

 　全部の石を違った色にして考える場合には、石に色をつけるよりも、番号を書いたほうが手っ取り早い。先ず左から、順に１２３４５－－と石を並べ、隣り合った２つを一緒に動かして、数字の順序を逆にしてみよう。この解は、左の図のように七手の解が２通りある。最後の形が右寄りに来るようにするには、八手が必要である。これらの解が最少手数であることは、人手によるしらみつぶしで確かめることが出来る。
 
　逆にする並べ替えが出来たら、でたらめに並べたものを番号順に並べなおしてみよう。やってみると、どうしてもうまくゆかない場合がある。例えば、　１２３５４－－　のように、二つだけ入れ替えたものはどうしてもどうしても元に戻すことが出来ない。
　番号順に並べ替えができるのは「偶順列」の場合だけである。偶順列とは大きさ順の転倒が偶数個ある順列のことである。例えば、　２５４１３－－　では、１の前には自分より大きい数字が３個（２・５・４）、３の前には２個（５・４）、４の前には１個（５）で合計　３＋２＋１＝６　で合計６個あるから、「順列の転倒は偶数個、つまり偶順列」というのである。隣り合った石を２個一緒に動かせば、順序の転倒は必ず偶数個（０も含めて）増減するから、何回動かしても偶順列ばかりが出来るわけである。
　しかし、「偶順列ならすべて順序通りに並べ替えが出来ることの証明」はやや難しいので、ここでは省略する。