数学における順列の定義 📂レンマ

数学における順列の定義

定義¹

有限集合$S$の各元をちょうど一度ずつ含むリストを$S$の順列^permutationという。特に$S$の濃度が$|S| = n$であり、部分集合$T \subset S$の濃度が$|T| = k$であるとき、$T$の順列となり得る場合の数を次のように表す。 $$ _{n} P _{k} = {\frac{ n! }{ (n - k) ! }} $$ ここで$n!$は$n$の階乗である。

簡単な定義

互いに異なる$n$個の中から$k$個を選んで順に並べる場合の数を順列^permutationといい、$_{n}P_{k}$で表す。

$$ {}_{n}P_{k} = n (n-1) \cdots (n-k+1) = \frac{ n! }{ (n-k)! } $$

ここで$n!$は階乗である。

説明

順列とは数学全般で頻繁に登場する概念であり、具体的な定義は細部で異なり得るが、基本的には配列$[1, \cdots , n]$をシャッフル^shuffleする全単射とみなすことが多い。このように使われる場合には「順序を入れ替えただけで本質的には同じ」という言及が多く、こうした文脈では証明の途中で「一般性を失うことなく、きちんと整列しているとしよう」という仮定を置きやすい。

行列代数

置換行列の定義:各行においてただ一つの成分だけが$1$で残りが$0$である正方行列$P \in \mathbb{R}^{n \times n}$を置換行列^{permutation matrix}という。

抽象代数

対称群の定義:集合$A$に対して全単射$\phi : A \to A$を置換^permutationという。$S_{A}$は$A$のすべての置換を集めた集合であり、関数の合成$\circ$に関して群$\left< S_{A} , \circ \right>$をなし、対称群^{symmetric group}と呼ばれる。