순열

이 문서는 수학에 관한 것입니다. 입술갈림증에 대해서는 언청이 문서를 참조하십시오.

순열(順列, permutation)은 서로 다른 n 개의 원소 중에서 r 개($n \geq r$)를 뽑아서 한 줄로 세우는 경우의 수이다.

_nP_r, 혹은 $P(n,r)$ 라고 쓴다. 이 기호는 순열을 나타내는 permutation의 앞글자를 딴 것이다.

$P(n,r)$의 수는 다음과 같이 구할 수 있다.

$P(n,r) = n(n-1)(n-2)\cdots (n-r+1)$

이를 계승을 이용하면 다음과 같은 식으로 나타낼 수 있다.

$P(n,r) = \frac{n!}{(n-r)!}$

예를 들어, 네 개의 문자 A,B,C,D 에서 두 개를 뽑아 나열하는 방법은 $P(4,2)=\frac{4!}{(4-2)!}=4\times 3 = 12$이므로 12가지가 된다. 일일이 나열하면 다음과 같다.

1. A B
2. A C
3. A D
4. B A
5. B C
6. B D
7. C A
8. C B
9. C D
10. D A
11. D B
12. D C

같은 것이 있는 순열

n개 중에 같은 것이 각각 p개, q개, …, r개가 있을 때, n개 모두를 일렬로 배열하는 순열의 수로 다음과 같다.

$\frac{n!}{p!q!\cdots r!}$

중복순열

중복순열(重複順列) _n$\Pi$_r은 n 개의 서로 다른 원소 중에서 중복을 허용하여 r개를 뽑아서 한 줄로 나열하는 경우의 수이다. r 개를 선택하는 경우, 최초에 n 개를 선택할 수 있고 이후에도 계속 n 개를 선택할 수 있기 때문에 이 순열의 개수는 $n^r$임을 알 수 있다.

예를 들어, 1부터 4까지의 자연수 4개를 이용하여 만들 수 있는 세자리 수는 모두 4³ = 64 가지가 있다.

원순열

원순열(圓順列, circular permutation)은 n개를 원형으로 나열하는 방법의 경우의 수이다. n개를 일렬로 나열하는 경우의 수는 n!인데, 원은 돌렸을 때 같아지는 것이 생기기 때문에, 여기서 중복되는 것이 n배 있음을 알 수 있다.

따라서 다음과 같이 수를 정의한다.

$\frac{n!}{n}$ = $\frac{n(n-1)!}{n}$ = $\frac{(n-1)!}{1}$

염주순열

염주순열(念珠順列)은 n개의 서로 다른 종류의 구슬로 목걸이를 만드는 방법의 수이다. n의 원순열은 $\frac{n!}{n}$인데, 목걸이는 뒤집어도 같은 것으로 취급하므로, 여기에서 중복되는 것이 2배가 있는 것을 알 수 있다. 따라서 n의 염주순열의 수는 $\frac{n!}{2n}$ = $\frac{n(n-1)!}{2n}$ = $\frac{(n-1)!}{2}$ 이다.

완전순열

이 부분의 본문은 완전순열입니다.

완전순열(complete permutation)은 교란(derangement)이라고도 불리며, 영어 단어 그대로 서브팩토리얼(subfactorial)이라고도 한다. 기호로는 !n과 같은 방법으로 사용한다. 수학의 순열 중, 원래 순열의 모든 요소를 변화시켜서 얻는 순열을 가리킨다.

같이 보기

• 조합