入れ替えの偶奇

いよいよ15パズルの謎に向けた準備だ。15パズルの1手は、空白とタイルの入れ替えだったね。何手か動かすと、タイルが並べ替えられる。この「並べ替え」そのものを計算する道具を作ろう。1 から n の番号を、重ならないように別の番号に付け替えることを置換という。たとえば、1 を 2 に、2 を 3 に、3 を 1 に付け替える置換を (1 2 3) と書く。かっこの中の番号を右どなりの番号に付け替え、いちばん右の番号は左はしの番号に付け替える。かっこに入っていない番号はそのままだ。

そう。置換も、続けて行うことを積として、群になる。何もしない置換が単位元で、付け替えを逆にたどるのが逆元だ。n 個の番号の置換は、全部で何個あるかな？

そう。その数を n! と書いて「n の階乗」と読む。n 個の番号の置換全体の群を、n 次の対称群といい、Sₙ と書く。正三角形の6つの操作は、頂点の位置 1, 2, 3 の付け替えと見ると、S₃ そのものだ。r は位置を 1→2→3→1 と付け替えるから (1 2 3)、s₁ は位置 2 と 3 を入れ替えるから (2 3) だね。この (2 3) のように、2つの番号だけを入れ替える置換を互換という。互換を組み合わせると、どんな置換が作れるかな。(1 2) のあとに (1 3) をしてごらん。

そう。同じように考えると、k 個の番号が回る (1 2 … k) は、(1 2)(1 3)…(1 k) と k−1 個の互換の積で書ける。では、どんな置換でも互換の積で書けるかな？

その通り。ただし、書き方は1通りではない。互換の個数も、書き方で変わる。では、個数が偶数か奇数かは、書き方で変わるかな？

そう。それを確かめる道具が転倒数だ。カードを1列に並べたとき、左にあるカードのほうが大きい番号になっている2枚の組、つまり順番が逆になっているペアの個数をいう。2, 3, 1, 4 の転倒数を数えてごらん。

そう。では、となりどうしの2枚を入れ替えると、転倒数はどう変わるかな？

そう。では、となりどうしでない2枚の入れ替えはどうかな。左から i 番目と j 番目（i＜j）のカードを入れ替えることを、となりどうしの入れ替えだけで行ってごらん。

そう。となりどうしの入れ替えを1回するたびに、転倒数は 1 増えるか 1 減る。すると、どの2枚を入れ替えても、転倒数の偶奇はどうなるかな？

そう。では仕上げだ。1, 2, …, n と並んだカードに、互換を k 回続けて行ったとしよう。

その通り。偶数個の互換の積で書ける置換を偶置換、奇数個の互換の積で書ける置換を奇置換という。どの置換も、どちらか一方にだけなる。1, 2, …, n に置換をしてできる並びの転倒数が偶数なら偶置換、奇数なら奇置換だ。S₃ の6つを分けてごらん。

そう。偶置換を全部集めると、部分群になる。確かめてごらん。

そう。これを交代群といい、Aₙ と書く。そして Aₙ は、Sₙ のちょうど半分の大きさだ。n が 2 以上なら、なぜそうなるか分かるかな？

そう。STAGE4 のラグランジュの等分割でいうと、Sₙ が、偶置換の部分群 Aₙ と、それをずらしたコピーである奇置換全体の、2つの組にぴったり分かれているんだ。これで15パズルの謎を解く準備がそろった。次のステージで、15パズルの1手1手を互換として数えよう。