814: ファイナイト（有限）要素たちのシーケンス（列）に対して、パーミュテーション（並べ替え）たちのセット（集合）は同一数の偶パーミュテーション（並べ替え）たちと奇パーミュテーション（並べ替え）たちを持つ

<このシリーズの前の記事 | このシリーズの目次 | このシリーズの次の記事>

ファイナイト（有限）要素たちのシーケンス（列）に対して、パーミュテーション（並べ替え）たちのセット（集合）は同一数の偶パーミュテーション（並べ替え）たちと奇パーミュテーション（並べ替え）たちを持つことの記述/証明

---

話題

About: セット（集合）

---

この記事の目次

• 開始コンテキスト
• ターゲットコンテキスト
• オリエンテーション
• 本体
• 1: 構造化された記述
• 2: 自然言語記述
• 3: 証明
• 4: 注

---

開始コンテキスト

• 読者は、セット（集合）の定義を知っている。
• 読者は、シーケンス（列）の定義を知っている。
• 読者は、シーケンス（列）のパーミュテーション（並べ替え）の定義を知っている。

---

ターゲットコンテキスト

• 読者は、任意のファイナイト（有限）要素たちの任意のシーケンス（列）に対して、パーミュテーション（並べ替え）たちのセット（集合）は同一数の偶パーミュテーション（並べ替え）たちと奇パーミュテーション（並べ替え）たちを持つという命題の記述および証明を得る。

---

オリエンテーション

本サイトにてこれまで議論された定義たちの一覧があります。

本サイトにてこれまで議論された命題たちの一覧があります。

---

本体

---

1: 構造化された記述

ここに'構造化された記述'のルールたちがある。

エンティティ（実体）たち:
$n$: $\in \mathbb{N}$, $2\le n<\mathrm{\infty }$
$S$: $\subseteq \mathbb{N}$, $=\{j_1,...,j_n\}$
$f$: $\in \{S\text{ 上方の全てのシーケンス（列）たち }\}$, $=(e_1,...,e_n)$
$P_{+}$: $=\{f\text{ の全ての偶パーミュテーション（並べ替え）たち }\}$
$P_{-}$: $=\{f\text{ の全ての奇パーミュテーション（並べ替え）たち }\}$
//

ステートメント（言明）たち:
$|P_{+}|=|P_{-}|=(1/2)n!$.
//

---

2: 自然言語記述

任意のファイナイト（有限）サブセット（部分集合）$S\subseteq \mathbb{N}$$=\{j_1,...,j_n\}$、ここで、$2\le n<\mathrm{\infty }$、以下を満たす任意のシーケンス（列）$f=(e_1,...,e_n)$、つまり、$domf=S$、に対して、$f$の偶パーミュテーション（並べ替え）たちのセット（集合）$P_{+}$と$f$の奇パーミュテーション（並べ替え）たちのセット（集合）$P_{-}$は同一カーディナリティ（濃度）を持つ、つまり、$|P_{+}|=|P_{-}|=(1/2)n!$。

---

3: 証明

全体戦略: $n$に関してインダクティブ（帰納的）に証明する; ステップ1: $n=2$であると仮定し、$|P_{+}|=|P_{-}|=(1/2)2!$であることを見る; ステップ2: ある$n$に対して, $|P_{+}|=|P_{-}|=(1/2)n!$であると仮定し、$n+1$に対して、$|P_{+}|=|P_{-}|=(1/2)(n+1)!$であることを見る。.

$n$に関してインダクティブ（帰納的）に証明しよう。

ステップ1:

$n=2$であると仮定しよう。

$P_{+}=\{(j_1,j_2)\}$; $P_{-}=\{(j_2,j_1)\}$。したがって、$|P_{+}|=|P_{-}|=(1/2)2!$。

ステップ2:

ある$n$に対して$|P_{+}|=|P_{-}|=(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)!$個の奇パーミュテーション（並べ替え）たちを持つ。

したがって、インダクションプリンシプル（帰納法）によって、$|P_{+}|=|P_{-}|=(1/2)n!$、各$n$に対して。

---

4: 注

当該シーケンス（列）の要素たちの間の重複の存在は問題にならない、なぜなら、任意のパーミュテーション（並べ替え）はシーケンス（列）のドメイン（定義域）上方自己バイジェクション（全単射）についてのものである（シーケンス（列）のパーミュテーション（並べ替え）の定義の"注"を参照）。

---

参考資料

<このシリーズの前の記事 | このシリーズの目次 | このシリーズの次の記事>