서로 다른 $n$개에서 $r$개를 골라 순서 있게 나열하는 것을 순열이라 하고, 그 가짓수를 $_nP_r$로 쓴다:
$$_nP_r = n(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n-r)!}$$
특히 $n$개 전부를 나열하는 가짓수는 $n! = n \times (n-1) \times \cdots \times 1$이다.
경우의 수의 곱의 법칙을 "자리 채우기"에 적용한 것이다. 첫 자리에 올 수 있는 것이 $n$가지, 다음 자리는 하나가 빠져 $n-1$가지, … 이렇게 $r$개의 자리를 채우면 곱셈이 자연히 나온다. 핵심은 순서가 다르면 다른 결과로 센다는 것 — 금·은·동 시상처럼 "누가 어느 자리인가"가 중요한 상황이 순열이다.
순열에서 학생들이 자주 멈추는 지점은 "순서를 고려한다"가 정확히 무슨 뜻인가다. 같은 사람을 뽑았어도 자리가 다르면 다른 경우로 센다는 말이다. $3$명 중 회장·부회장을 뽑을 때 "A가 회장, B가 부회장"과 "B가 회장, A가 부회장"은 뽑힌 사람은 똑같지만 역할이 달라 서로 다른 결과다. 이렇게 자리(순서)에 이름표가 붙어 있으면 순열이다.
이때 흔히 하는 착각이 순열과 조합을 문제 유형으로 통째 외우려는 것이다. 그보다 "뽑고 나서 자리(순서)를 구분하나?"라는 질문 하나만 던지면 된다. 회장·부회장은 자리를 구분하니 순열, 그냥 대표 $2$명은 자리 구분이 없으니 조합이다. 같은 "$2$명 뽑기"라도 이 질문의 답에 따라 가짓수가 달라진다.
한 가지 더, $n!$이 얼마나 빠르게 커지는지도 감을 잡아두면 좋다. $5$명을 한 줄로 세우는 방법이 벌써 $120$가지다. 사람이 하나 늘 때마다 앞의 결과에 그 수를 통째로 곱하기 때문에, 줄 세우기 경우의 수는 순식간에 커진다.
$_nP_r$의 공식은 자리를 하나씩 채워 보면 그대로 나온다. 새로 필요한 것은 경우의 수의 곱의 법칙 하나뿐이다.
① 자리를 차례로 채운다. 채워야 할 자리가 $r$개 있다. 첫 자리에 놓을 수 있는 것은 $n$가지. 둘째 자리에는 이미 쓴 하나를 뺀 $n-1$가지. 이렇게 한 자리 채울 때마다 후보가 하나씩 줄어든다.
② 마지막 자리의 후보 수를 센다. $r$번째 자리를 채울 때에는 앞에서 $r-1$개를 이미 썼으므로 남은 후보는 $n-(r-1) = n-r+1$가지다. 곱의 법칙으로 전부 곱하면
$$_nP_r = n(n-1)(n-2)\cdots(n-r+1) \quad (\text{인자 } r \text{ 개})$$
가 된다. 인자의 개수가 정확히 $r$개라는 점이 검산의 기준이다 — $r=1$이면 $n$ 하나, $r=n$이면 $1$까지 내려가 $n!$이 된다.
③ 계승 꼴로 바꾼다. ②의 곱에는 $n-r$부터 $1$까지가 빠져 있다. 그 빠진 부분을 곱하고 다시 나누면(같은 값을 곱하고 나누므로 값은 그대로)
$$_nP_r = \frac{n(n-1)\cdots(n-r+1) \times (n-r)(n-r-1)\cdots 1}{(n-r)(n-r-1)\cdots 1} = \frac{n!}{(n-r)!}$$
계승 하나로 통일되기 때문에 조합·이항정리와 같은 언어로 이어 붙일 수 있다. 참고로 $r = n$을 넣으면 $_nP_n = \dfrac{n!}{0!}$인데, ②에서 이 값이 $n!$이어야 하므로 $0! = 1$로 약속해야 앞뒤가 맞는다. $0!=1$은 임의의 규칙이 아니라 이 일관성이 요구하는 값이다.
④ 원순열도 같은 셈에서 나온다. $n$명을 한 줄로 세우는 방법은 $n!$가지다. 그런데 원탁에서는 모두가 한 칸씩 돌아앉은 배치를 같은 것으로 보므로, 한 배치마다 회전으로 겹치는 것이 $n$가지씩 생긴다. 부풀려진 만큼 나누면
$$\frac{n!}{n} = (n-1)!$$
이는 "한 사람을 기준으로 고정하고 나머지 $n-1$명을 줄 세운다"는 풀이와 정확히 같은 답이다.
⑤ 중복순열은 후보가 줄지 않는 경우다. 뽑은 것을 되돌려 놓으면 ①에서 후보가 줄어드는 이유가 사라진다. 매 자리마다 후보가 $n$가지씩이고 자리가 $r$개이므로 $n^r$이다.
MATH의 네 글자로 만들 수 있는 배열: $4! = 24$가지"몇 가지로 늘어놓을 수 있나"를 세는 문제는 확률보다 훨씬 오래됐다. 인도의 바스카라 2세는 12세기 저작 『릴라바티』에서 자릿수와 배열의 가짓수를 묻는 문제를 다뤘고, 시의 운율이나 향료의 조합 같은 실제 상황을 세는 계산이 인도·이슬람 수학에 두루 남아 있다.
이 셈을 하나의 주제로 묶어 이름을 붙인 사람은 라이프니츠다. 그는 1666년 『조합론』에서 "대상들을 짝짓고 늘어놓는 방법을 세는 학문"을 독립된 분야로 구상했다. 이어 야코프 베르누이가 『추측술』(1713)에서 순열과 조합의 규칙을 체계적으로 정리해, 이후 확률 계산의 표준 도구가 되었다.
표기는 훨씬 나중에 굳었다. 계승 기호 $n!$은 1808년 크리스티안 크람프가 도입했고, $_nP_r$·$_nC_r$ 같은 표기는 19세기 이후 교과서를 거치며 자리를 잡았다. 그래서 오늘날에도 나라와 분야에 따라 $_nC_r$과 $\binom{n}{r}$이 함께 쓰인다.