순열과 조합: 순서와 중복을 가려 센다

핵심 정리

서로 다른 n 개에서 r 개를 골라 순서대로 늘어놓는 방법의 수를 순열이라 하고 {}_n\mathrm{P}_r=\dfrac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1) 로 쓴다. 첫 자리에 n 가지, 둘째 자리에 n-1 가지가 올 수 있으므로, 각 자리의 경우의 수를 곱하면 이 공식이 성립한다. 순서를 따지지 않고 r 개만 뽑는 방법의 수는 조합이라 하며 {}_n\mathrm{C}_r=\dfrac{n!}{r!\,(n-r)!} 로 쓴다. 순열은 순서를 세고 조합은 순서를 세지 않는다. 이 구분이 문제를 가른다. 한 조합마다 r! 가지 배열이 생기므로 {}_n\mathrm{P}_r=r!\times{}_n\mathrm{C}_r 이다. 문장에 '뽑는다'만 나오면 조합이고, '자리에 놓는다'나 '순서대로'가 나오면 순열이다. 한마디로 순서가 있으면 순열, 없으면 조합 이다. 같은 것이 p 개, q 개, \cdots 씩 섞인 n 개를 일렬로 세우는 경우의 수는 \dfrac{n!}{p!\,q!\cdots} 이다. 같은 것끼리 자리를 바꿔도 같은 나열이 되므로, 같은 것끼리의 순서 수로 나눈다. 같은 것이 있는 나열은 같은 것끼리의 순서 수로 나눈다. 원순열은 n 개를 원형으로 세우되 회전하여 일치하는 것을 같다고 본다. 그래서 회전이 같으면 한 개를 고정한다. 그 한 개를 빼고 나머지를 일렬로 세우면 (n-1)! 가지다. 같은 것을 여러 번 고를 수 있으면 자리마다 곱한다. 주사위를 세 번 던지는 경우는 6^3 이다. 중복조합 {}_n\mathrm{H}_r 은 같은 것을 여러 번 고르되 순서를 세지 않는 방법이며 {}_n\mathrm{H}_r={}_{n+r-1}\mathrm{C}_r 과 같다. 기본 성질인 {}_n\mathrm{C}_0=1 과 {}_n\mathrm{C}_r={}_n\mathrm{C}_{n-r} 도 함께 익혀 두면 계산이 짧아진다.

자세히

공식이 나오는 과정을 보자. 서로 다른 5명 가운데 회장과 부회장을 뽑으면, 회장 자리에 5명 중 한 명을 놓고 부회장 자리에 남은 4명 중 한 명을 놓으므로 5\times4=20 가지다. 같은 두 명을 뽑더라도 역할을 정하지 않으면 한 가지로 세므로 {}_5\mathrm{C}_2=10 이다. 두 역할을 구별하는 만큼 2! 배가 되어 {}_5\mathrm{P}_2=2!\times{}_5\mathrm{C}_2=20 이 성립한다. 조합으로 뽑은 두 명마다 두 역할을 나누는 방법이 두 가지씩 생긴다. 아래 표는 여섯 가지 셈법을 한 번에 비교한다. 짧은 예의 값은 모두 손으로 확인할 수 있다.

같은 것이 섞인 나열을 보자. 문자 A, A, B 세 개를 일렬로 세우면 3!=6 가지 배열 가운데 AAB, ABA, BAA는 두 A를 바꿔도 같은 나열이다. 그래서 두 A를 구별해 6가지로 세고 2! 로 나누어 \dfrac{3!}{2!}=3 가지를 얻는다. 같은 문자가 두 종류 이상 섞이면 각 종류의 순서 수로 모두 나눈다. 원순열은 한 자리를 고정하면 회전과 상관없이 일렬 배열과 일대일로 대응한다. 4명을 원탁에 앉히면 한 명을 고정하고 나머지 3명을 배열하므로 3!=6 가지다. 중복순열은 자리마다 후보 수를 곱한다. 6가지 눈 가운데 중복을 허락해 두 번 고르면 6\times6=36 가지다. 중복조합은 같은 것을 여러 번 고르되 순서를 세지 않는다. 종류가 3가지인 빵에서 2개를 고르면 AA, BB, CC, AB, AC, BC 여섯 가지이고, 이는 {}_3\mathrm{H}_2={}_4\mathrm{C}_2=6 이다. 종류 사이에 칸막이 n-1 개를 두고 물건 r 개를 한 줄에 놓으면, 전체 n+r-1 자리에서 r 자리를 고르는 문제가 된다. 즉 중복조합은 칸막이를 세워 조합으로 바꾼다 이다. 계산 순서를 정리한다. 먼저 순서를 세는지, 같은 것이 있는지, 중복을 허락하는지, 원형인지를 차례로 확인한다. 그다음 해당하는 식을 고른다. 특정 원소의 위치 같은 조건이 있으면 그 원소를 먼저 자리에 놓고 나머지를 센다. 확률을 구할 때는 전체 경우의 수를 분모에 둔다. 검산은 {}_6\mathrm{C}_2=\dfrac{6\cdot5}{2\cdot1}=15 처럼 약분 전후를 확인하면 충분하다.