ファイナイト（有限）要素たちのシーケンス（列）に対して、パーミュテーション（並べ替え）たちのセット（集合）は同一数の偶パーミュテーション（並べ替え）たちと奇パーミュテーション（並べ替え）たちを持つことの記述/証明
話題
About: セット（集合）
この記事の目次
開始コンテキスト
- 読者は、セット（集合）の定義を知っている。
- 読者は、シーケンス（列）の定義を知っている。
- 読者は、シーケンス（列）のパーミュテーション（並べ替え）の定義を知っている。
ターゲットコンテキスト
- 読者は、任意のファイナイト（有限）要素たちの任意のシーケンス（列）に対して、パーミュテーション（並べ替え）たちのセット（集合）は同一数の偶パーミュテーション（並べ替え）たちと奇パーミュテーション（並べ替え）たちを持つという命題の記述および証明を得る。
オリエンテーション
本サイトにてこれまで議論された定義たちの一覧があります。
本サイトにてこれまで議論された命題たちの一覧があります。
本体
1: 構造化された記述
ここに'構造化された記述'のルールたちがある。
エンティティ（実体）たち:
\(n\): \(\in \mathbb{N}\), \(2 \le n \lt \infty\)
\(S\): \(\subseteq \mathbb{N}\), \(= \{j_1, ..., j_n\}\)
\(f\): \(\in \{S \text{ 上方の全てのシーケンス（列）たち }\}\), \(= (e_1, ..., e_n)\)
\(P_+\): \(= \{f \text{ の全ての偶パーミュテーション（並べ替え）たち }\}\)
\(P_-\): \(= \{f \text{ の全ての奇パーミュテーション（並べ替え）たち }\}\)
//
ステートメント（言明）たち:
\(\vert P_+ \vert = \vert P_- \vert = (1 / 2) n!\).
//
2: 自然言語記述
任意のファイナイト（有限）サブセット（部分集合）\(S \subseteq \mathbb{N}\)\(= \{j_1, ..., j_n\}\)、ここで、\(2 \le n \lt \infty\)、以下を満たす任意のシーケンス（列）\(f = (e_1, ..., e_n)\)、つまり、\(dom f = S\)、に対して、\(f\)の偶パーミュテーション（並べ替え）たちのセット（集合）\(P_+\)と\(f\)の奇パーミュテーション（並べ替え）たちのセット（集合）\(P_-\)は同一カーディナリティ（濃度）を持つ、つまり、\(\vert P_+\vert = \vert P_- \vert = (1 / 2) n!\)。
3: 証明
全体戦略: \(n\)に関してインダクティブ（帰納的）に証明する; ステップ1: \(n = 2\)であると仮定し、\(\vert P_+ \vert = \vert P_- \vert = (1 / 2) 2!\)であることを見る; ステップ2: ある\(n\)に対して, \(\vert P_+ \vert = \vert P_- \vert = (1 / 2) n!\)であると仮定し、\(n + 1\)に対して、\(\vert P_+ \vert = \vert P_- \vert = (1 / 2) (n + 1)!\)であることを見る。.
\(n\)に関してインダクティブ（帰納的）に証明しよう。
ステップ1:
\(n = 2\)であると仮定しよう。
\(P_+ = \{(j_1, j_2)\}\); \(P_- = \{(j_2, j_1)\}\)。したがって、\(\vert P_+ \vert = \vert P_- \vert = (1 / 2) 2!\)。
ステップ2:
ある\(n\)に対して\(\vert P_+ \vert = \vert P_- \vert = (1 / 2) n! := m\)であり、\(f = (e_1, ..., e_{n + 1})\)であると仮定しよう。
全てのパーミュテーション（並べ替え）たちは排他的に以下のケースたちに分割できる: 1) \(j_{n + 1}\)は\(j_{n + 1}\)からマップされる; 2) \(j_{n + 1}\)は\(j_n\)からマップされる; ...; n + 1) \(j_{n + 1}\)は\(j_1\)からマップされる。
ケース1)に対して、パーミュテーション（並べ替え）たちは、\(j_{n + 1}\)を固定した\((j_1, ..., j_{n + 1})\)のパーミュテーション（並べ替え）たちである。
\((j_1, ..., j_{n + 1})\)はサイン（符号）\((-1)^0\)を持つところ、当該パーミュテーション（並べ替え）たちは\((j_1, ..., j_n)\)のパーミュテーション（並べ替え）たちであり、それは、\(m\)個の偶パーミュテーション（並べ替え）たちと\(m\)個の奇パーミュテーション（並べ替え）たちを持つ、インダクション（帰納）仮定によって。
したがって、ケース1)は\(m\)個の偶パーミュテーション（並べ替え）たちと\(m\)個の奇パーミュテーション（並べ替え）たちを持つ。
ケース2)に対して、当該パーミュテーション（並べ替え）たちは、\(j_{n + 1}\)を固定した\((j_1, ..., j_{n - 1}, j_{n + 1}, j_n)\)のパーミュテーション（並べ替え）たちである。
\((j_1, ..., j_{n - 1}, j_{n + 1}, j_n)\)はサイン（符号）\((-1)^1\)を持つ（なぜなら、\(j_n\)と\(j_{n + 1}\)がスイッチされた）ところ、当該パーミュテーション（並べ替え）たちは\((j_1, ..., j_n)\)のパーミュテーション（並べ替え）たちであり、それは、\(m\)個の偶パーミュテーション（並べ替え）たちと\(m\)個の奇パーミュテーション（並べ替え）たちを持つ、インダクション（帰納）仮定によって。
したがって、ケース2)は\(m\)個の偶パーミュテーション（並べ替え）たちと\(m\)個の奇パーミュテーション（並べ替え）たちを持つ。
...
ケースn + 1)に対して、当該パーミュテーション（並べ替え）たちは、\(j_{n + 1}\)を固定した\((j_{n + 1}, j_1, ..., j_n)\)のパーミュテーション（並べ替え）たちである。
\((j_{n + 1}, j_1, ..., j_n)\)はサイン（符号）\((-1)^n\)を持つ（なぜなら、第1に、\(j_n\)と\(j_{n + 1}\)がスイッチされ、次に、\(j_{n - 1}\)と\(j_{n + 1}\)がスイッチされ、...、そして、\(j_1\)と\(j_{n + 1}\)がスイッチされた）ところ、当該パーミュテーション（並べ替え）たちは\((j_1, ..., j_n)\)のパーミュテーション（並べ替え）たちであり、それは、\(m\)個の偶パーミュテーション（並べ替え）たちと\(m\)個の奇パーミュテーション（並べ替え）たちを持つ、インダクション（帰納）仮定によって。
したがって、ケースn + 1)は\(m\)個の偶パーミュテーション（並べ替え）たちと\(m\)個の奇パーミュテーション（並べ替え）たちを持つ。
したがって、\(f\)は、\(m + ... + m = (n + 1) m = (1 / 2) (n + 1)!\)個の偶パーミュテーション（並べ替え）たちと\(m + ... + m = (n + 1) m = (1 / 2) (n + 1)!\)個の奇パーミュテーション（並べ替え）たちを持つ。
したがって、インダクションプリンシプル（帰納法）によって、\(\vert P_+ \vert = \vert P_- \vert = (1 / 2) n!\)、各\(n\)に対して。
4: 注
当該シーケンス（列）の要素たちの間の重複の存在は問題にならない、なぜなら、任意のパーミュテーション（並べ替え）はシーケンス（列）のドメイン（定義域）上方自己バイジェクション（全単射）についてのものである（シーケンス（列）のパーミュテーション（並べ替え）の定義の"注"を参照）。
