중복조합이란?
중복조합은 영어로 'multichoose'라고도 부르며, 서로 다른 n가지 종류에서 r개를 고를 때 순서를 따지지 않고 같은 종류를 여러 번 골라도 되는 경우의 수를 뜻합니다. 그 결과는 하나의 다중집합(multiset)이 됩니다. 예를 들어 3가지 맛 중에서 아이스크림 2스쿱을 중복을 허용해 고른다면 {바닐라, 바닐라}나 {바닐라, 초콜릿}과 같은 선택이 가능합니다.
계산기 사용 방법
고를 수 있는 서로 다른 대상(종류)의 개수 \(n\)과, 뽑으려는 표본의 크기 \(r\)을 입력하세요. 두 값 모두 0 이상의 정수여야 합니다. 계산 버튼을 누르면 크기가 \(r\)인 서로 다른 다중집합의 수, 즉 \(C^R(n,r)\) 값을 알려 줍니다.
공식 풀이
경우의 수는 이항계수 \(C(n + r - 1, r)\)과 같으며, 이는 다음과 같이 전개됩니다.
$$C^R(n, r) = \binom{n + r - 1}{r} = \frac{(n + r - 1)!}{r!\,(n - 1)!}$$이것이 바로 잘 알려진 '별과 막대(stars and bars)' 원리입니다. 즉 \(r\)개의 똑같은 별을 \(n - 1\)개의 막대로 구분된 \(n\)개의 칸에 나누어 담는 방법의 수이지요. 이 계산기는 팩토리얼 자릿수 폭주를 막기 위해, \(i\)를 1부터 \(r\)까지 돌리면서 누적 곱에 \((n - 1 + i)\)를 곱하고 \(i\)로 나누는 방식으로 값을 구합니다.
$$C^R(n,r) = \prod_{i=1}^{r} \frac{n - 1 + i}{i}$$
예제로 살펴보기
\(n = 10\), \(r = 3\)인 경우를 보겠습니다.
$$C^R(10,3) = C(12,3) = \frac{12 \times 11 \times 10}{3 \times 2 \times 1} = \frac{1320}{6} = 220$$따라서 10가지 종류에서 중복을 허용해 3개를 고르는 방법은 모두 220가지입니다.
자주 묻는 질문
일반 조합과는 무엇이 다른가요? 일반 조합 \(C(n,r)\)은 중복을 허용하지 않습니다. 반면 중복조합은 같은 항목을 여러 번 고를 수 있기 때문에 일반적으로 경우의 수가 더 큽니다.
r = 0이면 어떻게 되나요? 아무것도 고르지 않는 방법은 정확히 한 가지뿐입니다. 따라서 \(n \ge 1\)인 모든 경우에 \(C^R(n,0) = 1\)입니다.
n = 0이면 어떻게 되나요? 고를 항목이 없고 \(r > 0\)이면 결과는 0입니다. 다만 \(n = 0\), \(r = 0\)인 빈 경우는 관례적으로 1로 봅니다.
