順列 $(p_1, p_2, ..., p_n)$ を互換によって $(1, 2, ..., n)$ に並び替えるとき、互換の回数が常に偶数であるか、または常に奇数であるかのいずれかが成り立つことを示す問題です。

1. 問題の内容

順列 $(p_1, p_2, ..., p_n)$ を互換によって $(1, 2, ..., n)$ に並び替えるとき、互換の回数が常に偶数であるか、または常に奇数であるかのいずれかが成り立つことを示す問題です。

2. 解き方の手順

順列の転倒数という概念を利用します。順列 $(p_1, p_2, ..., p_n)$ の転倒数とは、$i < j$ かつ $p_i > p_j$ を満たす $(i, j)$ の組の個数のことです。

* **転倒数と互換:** 互換を行うと、転倒数の偶奇が変わります。つまり、ある互換によって転倒数が奇数個増えるか、奇数個減るかのどちらかです。したがって、転倒数の偶奇が変化します。

* **恒等置換の転倒数:** 順列 $(1, 2, ..., n)$ は、転倒数が0です。つまり、偶数です。

* **証明:** 順列 $(p_1, p_2, ..., p_n)$ を互換によって $(1, 2, ..., n)$ に並び替えることを考えます。$(1, 2, ..., n)$ の転倒数は0であり、これは偶数です。初期の順列 $(p_1, p_2, ..., p_n)$ の転倒数を $I$ とします。互換を1回行うごとに転倒数の偶奇が変化するので、$(1, 2, ..., n)$ に並び替えるのに必要な互換の回数を $k$ とすると、$I$ と $k$ の偶奇は一致します。つまり、$I$ が偶数なら $k$ も偶数、$I$ が奇数なら $k$ も奇数です。

$I \equiv k \pmod{2}$

したがって、順列 $(p_1, p_2, ..., p_n)$ を $(1, 2, ..., n)$ に並び替えるために必要な互換の回数は、常に偶数であるか、または常に奇数であるかのどちらかです。

3. 最終的な答え

順列 $(p_1, p_2, ..., p_n)$ を互換によって $(1, 2, ..., n)$ に並び替えるとき、互換の回数は常に偶数であるか、または常に奇数であるかのいずれかが成り立つ。