問題は2つの部分からなります。 (1) 任意の置換に対して、それを実現するアミダクジが存在することを示せ。 (2) アミダクジの横棒の本数の偶奇は、そのアミダクジが与える置換の偶奇と一致することを示せ。

1. 問題の内容

問題は2つの部分からなります。

(1) 任意の置換に対して、それを実現するアミダクジが存在することを示せ。

(2) アミダクジの横棒の本数の偶奇は、そのアミダクジが与える置換の偶奇と一致することを示せ。

2. 解き方の手順

(1) 任意の置換は互換の積で表せることを利用します。また、隣接互換はアミダクジの横棒1本に対応することを利用します。

* 任意の置換 $\sigma$ を考えます。

* $\sigma$ は互換の積で表せます。すなわち、$\sigma = \tau_1 \tau_2 \dots \tau_k$ (ただし、$\tau_i$ は互換) と表せます。

* さらに、任意の互換は隣接互換の積で表せます。例えば、$(i, j)$ (ただし $i < j$) は $(i, i+1)(i+1, i+2)\dots(j-1, j)(j-2, j-1)\dots(i, i+1)$ と表せます。

* 隣接互換 $(i, i+1)$ は、アミダクジの $i$ 番目の縦線と $i+1$ 番目の縦線の間に横棒を1本引くことに対応します。

* したがって、任意の置換は隣接互換の積で表せるので、対応するアミダクジを作成できます。

(2) アミダクジの横棒の数は隣接互換の数に対応し、隣接互換1つは置換の符号を反転させます。

* アミダクジの横棒の本数を $n$ とします。これはアミダクジが実行する隣接互換の回数に相当します。

* 各隣接互換は置換の符号を $-1$ 倍します。

* したがって、$n$ 回の隣接互換の結果、置換の符号は $(-1)^n$ 倍されます。

* 置換の符号が $(-1)^n$ であることは、$n$ が偶数ならば置換は偶置換、奇数ならば奇置換であることを意味します。

* すなわち、横棒の数が偶数ならば偶置換、奇数ならば奇置換となります。

3. 最終的な答え

(1) 任意の置換に対して、それを実現するアミダクジが存在する。

(2) アミダクジの横棒の本数の偶奇は、そのアミダクジが与える置換の偶奇と一致する。