No.100

あみだくじは置換とみなすことができる.

置換は複数のループから成り立っている. たとえば, $(1 \rightarrow 3 \rightarrow 5 \rightarrow 6 \rightarrow 1)$, $(2 \rightarrow 4 \rightarrow 2)$ という感じである.

直列あみだくじの場合, この置換を2回繰り返すことになる.

ループが $n$ 個の異なる数字からなりなっているとすると, 置換を2回繰り返したとき置換は以下のようになる.

$n$ が奇数のとき:

$$(1 \rightarrow 3 \rightarrow 2 \rightarrow 5 \rightarrow 6 \rightarrow 1) \Rightarrow (1 \rightarrow 2 \rightarrow 6 \rightarrow 3 \rightarrow 5 \rightarrow 1)$$

同じ長さのループに変わる.

$n$ が偶数のとき:

$$(1 \rightarrow 3 \rightarrow 5 \rightarrow 6 \rightarrow 1) \Rightarrow (1 \rightarrow 5 \rightarrow 1), (3 \rightarrow 6 \rightarrow 3)$$

$n / 2$ の長さのループ2つに分かれる.

よって, 置換を2回繰り返したあとの $n$ が奇数のループは置換を1回行うときのループに戻すことができる. 単独のループでもいいし, 同じ $n$ のループを2つ組み合わせてもいい.

また置換を2回繰り返したあとの $n$ が偶数のループは同じ $n$ のループを2つ組み合わせることでのみ置換を1回行うときのループに戻すことができる.

したがって, 直列あみだくじが存在するための条件は, $n$ が偶数のループが偶数個存在することである.