순열 함수
정의
유한집합 $X$에 대해서 전단사 $\sigma : X \to X$를 $X$의 순열 함수permutation 또는 간단히 순열이라 한다. $|X| = n$일 때는 원소에 번호를 붙여 다음과 같이 두는 것이 관례다.
$$ X = \left\{ 1, 2, \dots, n \right\} $$
설명
사실 정의에서 집합 $X$가 유한집합이어야 할 필요는 없지만 쉬운 설명을 위해 유한집합으로 제한한다.
순열을 전단사 함수로 정의했으므로, 순열은 원소를 겹치지도 빠뜨리지도 않게 다시 늘어놓는 것과 같은 일을 한다. 그래서 $|X| = n$이면 $\sigma(1)$이 될 수 있는 값이 $n$가지, 그것이 정해지면 $\sigma(2)$가 될 수 있는 값이 남은 $n-1$가지이므로 $X$의 순열은 정확히 $n!$개이고 경우의 수로서의 순열 $_{n}P_{n}$과 같다.
$$ {}_{n}P_{n} = \dfrac{n!}{(n-n)!} = n! $$
$X = \left\{ 1, 2, \dots, n \right\}$에 대해서 모든 순열함수 $\sigma : X \to X$의 집합을 $S_{n}$이라 표기한다.
$$ S_{n} = \left\{ \sigma : X \to X \mid \text{$\sigma$ is bijective} \right\} $$
표기
$X = \left\{ 1, 2, \dots, n \right\}$의 순열은 윗줄에 $X$의 원소를, 아랫줄에 그 원소가 옮겨가는 곳을 적어 나타내는 것이 가장 직관적이다. 이를테면 $n = 4$이고 $1 \mapsto 3$, $2 \mapsto 1$, $3 \mapsto 4$, $4 \mapsto 2$인 순열은 다음과 같이 적힌다.
$$ \sigma = \begin{bmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{bmatrix} $$
위 매핑을 이으면 $1 \to 3 \to 4 \to 2 \to 1$이므로 같은 순열을 $\sigma = (1,3,4,2)$와 같이 나타내기도 한다. 다만 모든 순열이 순환 하나로 나타나는 것은 아니다. 예를 들어 $1 \mapsto 2$, $2 \mapsto 1$, $3 \mapsto 4$, $4 \mapsto 3$인 순열 $\tau$는 매핑을 이으면 $1 \to 2 \to 1$과 $3 \to 4 \to 3$의 두 고리로 갈라지므로, 서로소인 두 순환의 곱 $\tau = (1,2)(3,4)$로 나타낸다. 일반적으로 모든 순열은 서로소인 순환들의 곱으로 나타낼 수 있다.
한편 순열을 $X$의 원소를 옮기는 함수로 보는 대신, 변수의 첨자에 작용시켜 $(x_{\sigma(1)}, x_{\sigma(2)}, \dots, x_{\sigma(n)})$과 같이 쓰기도 한다. 위의 예시라면 이 표기는 $(x_{3}, x_{1}, x_{4}, x_{2})$를 뜻한다.