순열은 서로 다른 n개 요소 중에서 r개를 선택하여 순서대로 나열하는 방법을 의미한다. 순열에선 순서가 결과에 영향을 미치기 때문에 순서가 중요하다. 동일한 요소를 서로 다른 순서로 나열하면, 각각을 별개의 순열로 간주한다. 예를 들어 A, B, C에서 A, B 두 요소를 선택하는 경우 AB와 BA는 서로 다른 순열이다.
ABACBABCCACBA, B, C 3가지 문자(n=3)로 만들 수 있는 2자리 순열(r=2)의 수는 총 6가지다. 첫 번째 자리에 올 수 있는 문자는 A, B, C 3가지를 선택할 수 있다. 두 번째 자리에는 남은 두 문자가 위치할 수 있으므로 2가지를 선택할 수 있다. 따라서 모든 순열의 수는 $3 \times 2 = 6$이 된다. 즉, n부터 n-1씩 r번 곱하면 순열의 수를 계산할 수 있다.
n = 3 (A, B, C)
r = 2
3(n) ✕ 2(n-1) = 6
---- ----
r₁ r₂
이처럼 순열은 각 단계에서 선택할 수 있는 모든 수를 곱한 것과 같으므로 팩토리얼의 개념을 부분적으로 포함하여 $n \times (n-1) \times (n-2) \times ... \times (n-r+1)$ 식으로 표현할 수 있다. 마지막 선택을 $n-r+1$로 표현한 이유는 r번째 요소를 선택할 시점은 r-1개의 요소를 선택한 상태이기 때문이다.
예를들어 n=5, r=3일 때 r(3)번째 요소를 선택할 차례에선 이미 r-1(2)개의 요소를 선택한 상태이다. 따라서 마지막 선택(r번째)의 남은 요소의 수는 n(5)에서 r-1(2)를 뺀 3이 된다. 이를 식으로 표현하면 $n-(r-1)$이 되고 분배 법칙으로 단순화하면 $n-r+1$이 되는 것.
순열을 수학적 공식으로 표기하면 $P(n,r)=\frac{n!}{(n-r)!}$ 이 된다. $\frac{n!}{(n-r)!}$ 식을 계산해보면 $(n-r)!$에 해당하는 항은 약분된 후 지워져서 $n \times (n-1) \times (n-2) \times ... \times (n-r+1)$ 형태가 되기 때문이다.
$$ P(3, 2) = \frac{3!}{(3-2)!} = \frac{3 \cdot 2 \cdot \cancel{1}}{\cancel{1}} = 3 \cdot 2 = 6
$$
$$ P(5, 3) = \frac{5!}{(5-3)!} = \frac{5 \cdot 4 \cdot 3 \cdot \cancel{2 \cdot 1}}{\cancel{2 \cdot 1}} = 5 \cdot 4 \cdot 3 = 60
$$
<aside>
<img src="/icons/search_gray.svg" alt="/icons/search_gray.svg" width="40px" /> 약분은 분자/분모가 공통된 인수를 가질 때, 이 인수로 분자와 분모를 나눠서 분수를 더 간단한 형태로 만드는 과정. ①분자/분모의 최대공약수(GCD)를 찾고, ②분자/분모를 최대공약수로 나눈 후, ③그 결과를 새로운 분자/분모에 사용하여 분수를 간소화한다. 다항식으로 된 분수는 분모와 분자를 인수분해(주어진 정수를 더 이상 나눌 수 없는 소수들의 곱으로 표현)하여 다항식(1개 이상의 항, e.g. 2x + 4는 항 2개)의 곱으로 나타낸 뒤 분자/분모에 모두 존재하는 다항식을 약분해서 없앤다.
</aside>
<aside> <img src="/icons/search_gray.svg" alt="/icons/search_gray.svg" width="40px" /> 순열은 $P(n,r)$ 혹은 $_nP_r$로 표기할 수 있다. P는 영단어 Permutation의 첫 글자를 가리킨다.
</aside>