경우의 수 - 순열과 조합

 

순열(Permutation)과 조합(Combination)은 경우의 수를 계산하는데 쓰이는 가장 일반적인 방법이다.

---

순열이란

순열은 쉽게 말해 $n$명중에서 $r$명을 임의로 뽑아 일렬로 나열할 수 있는 경우의 수이다. 예를 들어 5명 중에서 3명을 임의로 뽑아 나열하는 경우가 순열이다.

순열은 $P$를 이용하여 표현하며 $n$명중 $r$명을 뽑아 나열하는 순열은 다음과 같이 계산한다.

${}_n\mathrm P_r = \frac{n!}{(n-r)!}$

예를 들면 구분되는 5명 중에서 임의의 3명을 뽑아 줄 세우는 경우의 수는 ${}_5\mathrm P_3=\frac {5!}{2!}=60$가지이다.

참고로, ${}_n\mathrm P_r$은 $P(n, r)$로도 쓰며 모두 같은 의미이다.

---

조합이란

순열은 $n$명중에 $r$개를 뽑아 배열하였지만 조합은 그냥 뽑기만 하는 것이다. 즉, 사람 5명을 그냥 임의로 뽑을 수 있는 경우의 수를 구하는 것이다.

조합은 $C$를 이용하여 표현하며 $n$명중 $r$명을 뽑기만 하는 조합은 다음과 같이 계산한다.

${}_n\mathrm C_r = \frac{n!}{(n-r)!r!}$

예를 들어 순열과 같이 구분되는 5명 중에서 3명을 뽑는 경우의 수는 $_{5}^{}\textrm{C}_{3}=\frac{5!}{2!3!}=10$가지이다.

참고로, ${}_n\mathrm C_r$은 $C(n, r)$, 혹은 $\dbinom nr$으로 쓰기도 하며 모두 같은 의미이다.

 

 

순열, 조합의 성질

1. 조합은 순열에서 나열하는 것만 뺀 경우이므로 순열의 계산 방법에서 나열하는 경우를 제외해주기 위해 $\frac{1}{r!}$을 곱해준 것이다. 따라서 일반적으로 ${}_n\mathrm P_r=r!{}_n\mathrm C_r$의 관계가 성립한다.
2. 조합에서 ${}_n\mathrm C_r={}_n\mathrm C_{(n-r)}$이 성립한다. 이는 5개 중 1개를 뽑아서 결정하든 5개 중 4를 뽑고 안 뽑힌 1개로 결정하든 차이가 없다는 것이다.
3. ${}_n\mathrm C_0, {}_n\mathrm C_n$은 둘 모두 1이다. (이는 대수적으로도, 경우의 수의 논리로도 증명이 가능하다)
4. ${}_n\mathrm C_r={}_{(n-1)}\mathrm C_r+{}_{(n-1)}\mathrm C_{(n-1)}$가 성립한다.
   위 식의 우변에서는 $n$명중에서 1명을 선택하게 된다. 그 후 그 사람을 선택하지 않고 나머지 $n-1$명중에서 $r$명을 뽑은 경우의 수(${}_{(n-1)}\mathrm C_r$)와 그 사람을 반드시 선택하기로 하고 나머지 $n-1$명중에서 $r-1$명을 뽑는 경우의 수(${}_{n-1}\mathrm C_{r-1}$)를 더하여 전체 경우의 수를 구하는 것이다. (물론, 식을 정리하여 정리할 수 있다. 하지만 이런 방식의 증명은 경우의 수에서 중요한 것이 아니니 생략한다.)