シーケンス（列）のパーミュテーション（並び替え）の定義
話題
About: セット（集合）
この記事の目次
開始コンテキスト
- 読者は、シーケンス（列）の定義を知っている。
ターゲットコンテキスト
- 読者は、シーケンス（列）のパーミュテーション（並び替え）の定義を得る。
オリエンテーション
本サイトにてこれまで議論された定義たちの一覧があります。
本サイトにてこれまで議論された命題たちの一覧があります。
本体
1: 構造化された記述
ここに'構造化された記述'のルールたちがある。
エンティティ（実体）たち:
\( \mathbb{N}\):
\( S\): \(\subseteq \mathbb{N}\)
\( f\): \(\in \{S \text{ からの全てのシーケンス（列）たち }\}\)
\(*\sigma\): \(: S \to S\),
\( f \circ \sigma\): \(\sigma\)の\(f\)への結果、\(S\)からのあるシーケンス（列）である
\( \sigma (f)\): \(= f \circ \sigma\)
\( \sigma (f)_j\): \(= (f \circ \sigma) (s_j)\)、ここで、\(s_j \in S\)は\(S\)を昇順に並べたものの\(j\)番目要素
//
コンディションたち:
\(\sigma \in \{\text{ 全てのバイジェクション（全単射）たち }\}\).
//
\(S\)がファイナイト（有限）である時は、\(\widetilde{S} := \{(s_1, s_2) \in \{S \text{ の全てのオーダード（順序付き）ペアたち }\} \vert s_1 \lt s_2 \land \sigma (s_2) \lt \sigma (s_1)\}\)のことを考えよう、そして、\(sgn (\sigma) = + 1 \text{ 、 } \vert \widetilde{S} \vert \in \{\text{ 全ての偶数たち }\} \text{ である時 }; = - 1 \text{ 、 } \vert \widetilde{S} \vert \in \{\text{ 全ての奇数たち }\} \text{ である時 }\)は、"\(\sigma\)のサイン（符号）"と呼ばれる。
2: 注
本定義は、\(f \circ \sigma\)を"パーミュテーション（並び替え）"とは呼ばない、\(f \circ \sigma\)がしばしば"パーミュテーション（並び替え）"によって意図されるものであるが。その理由は以下の通り。
\(S = \{1, 2\}\)、当該シーケンス（列）が\((3, 3)\)、\(\sigma = id\)および\(\sigma', 1 \mapsto 2; 2 \mapsto 1\)である時、\(f \circ \sigma = f \circ \sigma'\)、したがって、私たちは、"2つのパーミュテーション（並び替え）たちがある。"と言えないであろう、もしも、\(f \circ \sigma\)を"パーミュテーション（並び替え）"と呼んでいたら。実のところ、\(\sigma \neq \sigma'\)、したがって、2つのパーミュテーション（並び替え）たちがある。
したがって、本定義によれば、当該シーケンス（列）の要素たちの間の何らの重複の存在も何の問題でもない、なぜなら、本定義は、当該シーケンス（列）のドメイン（定義域）上方の自己バイジェクション（全単射）についてのものであって、ドメイン（定義域）は何の重複も持たない。
例えば、私たちが\(\sum_{\sigma} sgn \sigma A^{\sigma (f)_1, ..., \sigma (f)_n}\)のような表現を使う時、当該シーケンス（列）は何らの重複要素たちを持ち、何らかの\(\sigma \neq \sigma'\)に対して\(f \circ \sigma = f \circ \sigma'\)かもしれないが、その表現は全てのパーミュテーション（並び替え）たちを取るのである、任意の重複に関わらず。
したがって、私たちは、\(f \circ \sigma\)を"パーミュテーション（並び替え）結果"と呼ぶ、厳密に言って、しかし、時には、それを"パーミュテーション（並び替え）"と呼ぶことがあるかもしれない、破壊的な混乱が起こらないであろうときは。
パーミュテーション（並び替え）\(\sigma\)はあるシーケンス（列）\(f\)に関して定義される、しかし、それは任意のシーケンス（列）\(f': S \to f' (S)\)のパーミュテーション（並び替え）でもある、ドメイン（定義域）が\(S\)である限りは、なぜなら、\(f' \circ \sigma\)は意味をなす。したがって、"\(\sigma\)は\((j_1, ..., j_k)\)のあるパーミュテーション（並び替え）であって、私たちは、\(\sum_{(j_1, ..., j_k)} M_{\sigma ((j_1, ..., j_k))_1, ..., \sigma ((j_1, ..., j_k))_k}\)を取る"のような私たちの表現は意味をなさないように思われるかもしれない（なぜなら、\(\sigma\)はある特定の\((j_1, ..., j_k)\)についてのものであって、そのような様々な\((j_1, ..., j_k)\)たちについてのものではないはず）、しかし、その表現が意味するのは、その同一\(\sigma\)が本当にそうした様々な\((j_1, ..., j_k)\)たちに作用できるということである。
任意のスイッチング\(\sigma_{j, l}\)、ここで、\(j \lt l\)、それは、以下を満たすパーミュテーション（並び替え）、つまり、\(\sigma (s_j) = s_l\)、\(\sigma (s_l) = s_j\)、\(\sigma (s_m) = s_m\)、各\(m \neq j, l\)に対して、である、は、当該パーミュテーション（並び替え）のサイン（符号）を変える、それが意味するのは、\(S\)上方の各パーミュテーション（並び替え）\(\sigma\)に対して、\(sgn (\sigma_{j, l} \circ \sigma) = - sgn (\sigma)\)、下に見られるとおり。
\((s, s')\)を、\(S\)の以下を満たす任意のオーダード（順序付き）ペア、つまり、\(s \lt s'\)、としよう。
以下の排他的ケースたちがある: 1) \(\sigma (s), \sigma (s') \notin \{s_j, s_l\}\); 2) \(\sigma (s) = s_j \land \sigma (s') \notin \{s_j, s_l\}\); 3) \(\sigma (s) = s_l \land \sigma (s') \notin \{s_j, s_l\}\); 4) \(\sigma (s) \notin \{s_j, s_l\} \land \sigma (s') = s_j\); 5) \(\sigma (s) \notin \{s_j, s_l\} \land \sigma (s') = s_l\); 6) \(\sigma (s) = s_j \land \sigma (s') = s_l\); 7) \(\sigma (s) = s_l \land \sigma (s') = s_j\): 1)は、\(\{\sigma (s), \sigma (s')\}\)の内のどれも\(\{s_j, s_l\}\)内にないケースである; 2)、3)、4)、5)は、\(\{\sigma (s), \sigma (s')\}\)の内の厳密に\(1\)個が\(\{s_j, s_l\}\)内にあるケースたちである; 6)および7)は、\(\{\sigma (s), \sigma (s')\}\)の内の\(2\)個が\(\{s_j, s_l\}\)内にあるケースたちである。
コンディションA\(\sigma (s) \lt \sigma (s') \land \sigma_{j, l} \circ \sigma (s') \lt \sigma_{j, l} \circ \sigma (s)\)またはコンディションB\(\sigma (s') \lt \sigma (s) \land \sigma_{j, l} \circ \sigma (s) \lt \sigma_{j, l} \circ \sigma (s')\)が満たされるペアたちをカウントする、各ケースに対して: それが意味するのは、\((s, s')\)がある反転されるペアとしてカウントされるか否かが\(\sigma\)と\(\sigma_{j, l} \circ \sigma\)の間で変更されるということである。
1)のことを考えよう。
\(\sigma_{j, l} \circ \sigma (s) = \sigma (s)\)および\(\sigma_{j, l} \circ \sigma (s') = \sigma (s')\)、したがって、そのようなペアはない。
2)のことを考えよう。
\(\sigma (s) = s_j\)および\(\sigma_{j, l} \circ \sigma (s) = s_l\)および\(\sigma_{j, l} \circ \sigma (s') = \sigma (s')\)。
注意として、\(s\)は、既に\(\sigma^{- 1} (s_j)\)として決定されている、したがって、これは、当該コンディションたちの内の\(1\)個を満たす\(s'\)たちを見つけるという問題である。
コンディションAに対して、\(\sigma (s) = s_j \lt \sigma (s') = \sigma_{j, l} \circ \sigma (s') \lt \sigma_{j, l} \circ \sigma (s) = s_l\)。
したがって、マッチングする\(s'\)たちは、\(s_j\)と\(s_l\)の間の\(l - 1 - j\)個要素たちの内の\(s \lt s'\)を満たすものたちである。
コンディションBに対して、\(s_l = \sigma_{j, l} \circ \sigma (s) \lt \sigma_{j, l} \circ \sigma (s') = \sigma (s') \lt \sigma (s) = s_j\)。
したがって、マッチングする\(s'\)は無い、なぜなら、\(s_j \lt s_l\)。
3)のことを考えよう。
\(\sigma (s) = s_l\)および\(\sigma_{j, l} \circ \sigma (s) = s_j\)および\(\sigma_{j, l} \circ \sigma (s') = \sigma (s')\)。
注意として、\(s\)は、既に、\(\sigma^{- 1} (s_l)\)として決定されている、したがって、これは、当該コンディションたちの内の\(1\)個を満たす\(s'\)たちを見つけるという問題である。
コンディションAに対して、\(\sigma (s) = s_l \lt \sigma (s') = \sigma_{j, l} \circ \sigma (s') \lt \sigma_{j, l} \circ \sigma (s) = s_j\)。
したがって、マッチングする\(s'\)は無い、なぜなら、\(s_j \lt s_l\)。
コンディションBに対して、\(s_j = \sigma_{j, l} \circ \sigma (s) \lt \sigma_{j, l} \circ \sigma (s') = \sigma (s') \lt \sigma (s) = s_l\)。
したがって、マッチングする\(s'\)たちは、\(s_j\)と\(s_l\)の間の\(l - 1 - j\)個要素たちの内の\(s \lt s'\)を満たすものたちである。
4)のことを考えよう。
\(\sigma_{j, l} \circ \sigma (s) = \sigma (s)\)および\(\sigma (s') = s_j\)および\(\sigma_{j, l} \circ \sigma (s') = s_l\)。
注意として、\(s'\)は、既に\(\sigma^{- 1} (s_j)\)として決定されている、したがって、これは、当該コンディションたちの内の\(1\)個を満たす\(s\)たちを見つけるという問題である。
コンディションAに対して、\(s_l = \sigma_{j, l} \circ \sigma (s') \lt \sigma_{j, l} \circ \sigma (s) = \sigma (s) \lt \sigma (s') = s_j\)。
したがって、マッチングする\(s\)は無い、なぜなら、\(s_j \lt s_l\)。
コンディションBに対して、\(s_j = \sigma (s') \lt \sigma (s) = \sigma_{j, l} \circ \sigma (s) \lt \sigma_{j, l} \circ \sigma (s') = s_l\)。
したがって、マッチングする\(s\)たちは、\(s_j\)と\(s_l\)の間の\(l - 1 - j\)個要素たちの内の\(s \lt s'\)を満たすものたちである。
5)のことを考えよう。
\(\sigma_{j, l} \circ \sigma (s) = \sigma (s)\)および\(\sigma (s') = s_l\)および\(\sigma_{j, l} \circ \sigma (s') = s_j\)。
注意として、\(s'\)は、既に\(\sigma^{- 1} (s_j)\)として決定されている、したがって、これは、当該コンディションたちの内の\(1\)個を満たす\(s\)たちを見つけるという問題である。
コンディションAに対して、\(s_j = \sigma_{j, l} \circ \sigma (s') \lt \sigma_{j, l} \circ \sigma (s) = \sigma (s) \lt \sigma (s') = s_l\)。
したがって、マッチングする\(s\)たちは、\(s_j\)と\(s_l\)の間の\(l - 1 - j\)個要素たちの内の\(s \lt s'\)を満たすものたちである。
コンディションBに対して、\(s_l = \sigma (s') \lt \sigma (s) = \sigma_{j, l} \circ \sigma (s) \lt \sigma_{j, l} \circ \sigma (s') = s_j\)。
したがって、マッチングする\(s\)は無い、なぜなら、\(s_j \lt s_l\)。
6)のことを考えよう。
\(\sigma (s) = s_j\)および\(\sigma_{j, l} \circ \sigma (s) = s_l\)および\(\sigma (s') = s_l\)および\(\sigma_{j, l} \circ \sigma (s') = s_j\)。
注意として、\(s\)および\(s'\)は、既に\(\sigma^{- 1} (s_j)\)および\(\sigma^{- 1} (s_l)\)として決定されている、したがって、これは、\(\sigma^{- 1} (s_j) \lt \sigma^{- 1} (s_l)\)であるか否かおよび既に決定された当該ペアが当該コンディションたちの内の\(1\)個を満たすか否かをチェックするという問題である。
実のところ、それは、コンディションAを満たす、\(\sigma (s) = s_j \lt s_l = \sigma (s') \land \sigma_{j, l} \circ \sigma (s') = s_j \lt s_l = \sigma_{j, l} \circ \sigma (s)\)として。
7)のことを考えよう。
\(\sigma (s) = s_l\)および\(\sigma_{j, l} \circ \sigma (s) = s_j\)および\(\sigma (s') = s_j\)および\(\sigma_{j, l} \circ \sigma (s') = s_l\)。
注意として、\(s\)および\(s'\)は、既に\(\sigma^{- 1} (s_l)\)および\(\sigma^{- 1} (s_j)\)として決定されている、したがって、これは、\(\sigma^{- 1} (s_l) \lt \sigma^{- 1} (s_j)\)であるか否かおよび既に決定された当該ペアが当該コンディションたちの内の\(1\)個を満たすか否かをチェックするという問題である。
実のところ、それは、コンディションBを満たす、\(\sigma (s') = s_j \lt s_l = \sigma (s) \land \sigma_{j, l} \circ \sigma (s) = s_j \lt s_l = \sigma_{j, l} \circ \sigma (s')\)として。
2)と4)を合わせて考えよう。
2)に対して、マッチングするペアたちは、\(s_j\)と\(s_l\)の間の\(l - 1 - j\)個要素たちの内の\(s \lt s'\)を満たす何らか\(m \le l - 1 - j\)個要素たちだけである（ここで、\(\sigma (s) = s_j\)および\(s_j \lt \sigma (s') \lt s_l\)）ところ、残っている\(l - 1 - j - m\)要素たち\(s_j \lt \sigma (s'') \lt s_l\)は、\(s'' \lt s\)である、すると、4)に対して、\(\sigma (s') = s_j\)であるから、\(s'' \lt s'\)（2)に対する\(s\) は4)に対する\(s'\)である）、したがって、残っている\(l - 1 - j - m\)個要素たちは、4)に対するマッチングするペアたちに他ならない。
したがって、2)と4)合わせて、\(l - 1 - j\)個ペアたちがある。
3)と5)を合わせて考えよう。
3)に対して、マッチングするペアたちは、\(s_j\)と\(s_l\)の間の\(m \le l - 1 - j\)個要素たちの内の\(s \lt s'\)を満たす何らか\(l - 1 - j\)個要素たちだけである（ここで、\(\sigma (s) = s_l\)および\(s_j \lt \sigma (s') \lt s_l\)）ところ、残っている\(l - 1 - j - m\)要素たち\(s_j \lt \sigma (s'') \lt s_l\)は、\(s'' \lt s\)である、すると、5)に対して、\(\sigma (s') = s_l\)であるから、\(s'' \lt s'\)（3)に対する\(s\)は5)に対する\(s'\)である）、したがって、残っている\(l - 1 - j - m\)個要素たちは、5)に対するマッチングするペアたちに他ならない。
したがって、3)と5)合わせて、\(l - 1 - j\)個ペアたちがある。
6)および7)に対して、もしも、\(\sigma^{- 1} (s_j) \lt \sigma^{- 1} (s_l)\)である場合、6)は当該\(1\)個ペアを持ち、7)はペアを持たない; もしも、\(\sigma^{- 1} (s_l) \lt \sigma^{- 1} (s_j)\)である場合、6)はペアを持たず、7)は当該\(1\)個ペアを持つ、したがって、いずれにせよ、6)と7)合わせて\(1\)個ペアがある。
したがって、全体で、\(2 (l - 1 - j) + 1\)個マッチングするペアたちがある。
当該ペアたちの数が奇数なので、当該パーミュテーション（並び替え）のサイン（符号）は、\(\sigma_{j, l}\)を適用することによって変化した: \(\sigma\)の\(\widetilde{S}\)に対して、何らか\(m\)個ペアたちが除かれ、何らか\(2 (l - 1 - j) + 1 - m\)個ペアたちが追加された、したがって、\(\vert \widetilde{S} \vert\)は、\(\vert \widetilde{S} \vert - m + 2 (l - 1 - j) + 1 - m = \vert \widetilde{S} \vert - 2 m + 2 (l - 1 - j) + 1\)へ変化した。
