중복 없는 조합이란?
중복 없는 조합이란 서로 다른 n개의 원소로 이루어진 집합에서 r개를 골랐을 때 만들 수 있는 서로 다른 그룹의 개수를 뜻합니다. 이때 뽑는 순서는 따지지 않으며, 같은 원소를 두 번 이상 고를 수도 없습니다. 예를 들어 "포커에서 5장으로 만들 수 있는 패는 몇 가지인가?" 혹은 "10명 중 3명으로 위원회를 구성하는 방법은 몇 가지인가?" 같은 질문에 답하는 개념입니다.
계산기 사용 방법
전체 원소의 개수를 n에, 뽑고자 하는 원소의 개수를 r에 입력하세요. 계산기가 곧바로 서로 다른 조합의 수인 \(C(n, r)\)를 알려 줍니다. 단, \(r\)은 \(n\)보다 클 수 없습니다. 존재하는 개수보다 많이 뽑을 수는 없으므로, \(r\)이 \(n\)을 넘으면 결과는 0이 됩니다.
공식 풀이
공식은 다음과 같습니다.
$$C(n, r) = \frac{\text{n}!}{\text{r}!\,\left(\text{n} - \text{r}\right)!}$$여기서 "!"는 팩토리얼을 뜻하며, 1부터 그 수까지 모든 양의 정수를 곱한 값입니다. 분자 \(n!\)은 모든 순서를 고려한 배열의 수이고, \(r!\)로 나누면 뽑은 그룹 안에서의 순서 차이가 사라지며, \((n - r)!\)로 나누면 선택하지 않고 남겨 둔 원소들의 순서 차이가 제거됩니다. 큰 수에서도 정확도를 유지하기 위해, 이 도구는 거대한 팩토리얼을 직접 계산하지 않고 반복적인 방식으로 결과를 구합니다.
예제로 알아보기
5가지 토핑 중에서 2가지를 고르는 방법은 몇 가지일까요?
$$C(5, 2) = \frac{5!}{2!\cdot 3!} = \frac{120}{2\cdot 6} = \frac{120}{12} = \mathbf{10}$$즉, 서로 다른 토핑 조합이 10가지 존재합니다.
파스칼의 삼각형과 주요 C(n, r) 값
표는 n = 0부터 10까지의 C(n, r)을 나타냅니다. 빈칸은 r > n인 경우로, 선택이 불가능하므로 값은 0입니다.
| n \ r | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | ||||||||||
| 1 | 1 | 1 | |||||||||
| 2 | 1 | 2 | 1 | ||||||||
| 3 | 1 | 3 | 3 | 1 | |||||||
| 4 | 1 | 4 | 6 | 4 | 1 | ||||||
| 5 | 1 | 5 | 10 | 10 | 5 | 1 | |||||
| 6 | 1 | 6 | 15 | 20 | 15 | 6 | 1 | ||||
| 7 | 1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | |||
| 8 | 1 | 8 | 28 | 56 | 70 | 56 | 28 | 8 | 1 | ||
| 9 | 1 | 9 | 36 | 84 | 126 | 126 | 84 | 36 | 9 | 1 | |
| 10 | 1 | 10 | 45 | 120 | 210 | 252 | 210 | 120 | 45 | 10 | 1 |
- 대칭성: \(C(n,r)=C(n,n-r)\). r개의 항목을 고르는 것은 남겨 둘 n − r개의 항목을 고르는 것과 같습니다. 각 행은 앞으로 읽으나 뒤로 읽으나 같습니다.
- 파스칼의 법칙: \(C(n,r)=C(n-1,r-1)+C(n-1,r)\). 각 항은 바로 위에 있는 두 항의 합입니다. 예를 들어 10행의 120 = 36 + 84입니다.
- 각 행의 합은 \(2^n\)입니다. 예를 들어 10행의 합은 1,024입니다.
nCr을 손으로 계산하는 방법
- 대칭성을 이용하세요. r과 n − r을 비교하여 더 작은 쪽으로 계산합니다. \(C(n,r)=C(n,n-r)\)이므로 예를 들어 C(50,48) = C(50,2)입니다.
- n에서 시작하여 내림차순으로 r개의 인수를 쓰세요: \(n\cdot(n-1)\cdot(n-2)\cdots(n-r+1)\). 이것이 분자입니다.
- 분모에는 r!을 쓰세요: \(r\cdot(r-1)\cdots 2\cdot 1\).
- 곱하기 전에 공통 인수를 약분하세요. 분자의 항과 분모의 항이 인수를 공유하면 나눕니다. 이렇게 하면 수가 작게 유지되고 결과가 정확해지며, 최종 답은 항상 정수이기 때문입니다.
- 남은 항을 곱하여 결과를 구하세요.
- 작은 예로 검산하세요. C(7,3)의 경우: \(\frac{7\cdot 6\cdot 5}{3\cdot 2\cdot 1}=\frac{210}{6}=35\). 대칭성 검산: C(7,4) = \(\frac{7\cdot 6\cdot 5\cdot 4}{24}=35\)로, 위 표와도 일치합니다.
자주 묻는 질문
조합과 순열은 어떻게 다른가요? 순열은 순서를 따집니다(AB ≠ BA). 반면 조합은 순서를 따지지 않습니다(AB = BA). 그래서 조합의 수는 항상 순열의 수보다 작거나 같습니다.
\(C(n, 0)\)은 얼마인가요? 1입니다. 아무것도 고르지 않는 방법은 정확히 한 가지뿐이기 때문입니다.
"중복 없음"이 여기서 중요한가요? 네. 중복이 없다는 것은 한 그룹 안에 같은 원소가 최대 한 번만 등장할 수 있다는 뜻으로, 이 계산기가 다루는 표준적인 nCr 상황입니다.