📂レンマ

数学における順列の定義

定義 ¹

有限集合 $S$ の各要素を正確に一度ずつだけ含む一覧を $S$ の 順列^permutationという。特に $S$ の基数が $|S| = n$ であり部分集合 $T \subset S$ の基数が $|T| = k$ であるとき、$T$ の順列になりうる場合の数を次のように表す。 $$ _{n} P _{k} = {\frac{ n! }{ (n - k) ! }} $$ ここで $n!$ は $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}と呼ぶ。