📂보조정리

수학에서 순열의 정의

정의 ¹

유한집합 $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}이라 부른다.