중복조합이란?
중복조합은 서로 다른 n가지 종류 중에서 같은 종류를 두 번 이상 골라도 되고 고르는 순서는 따지지 않을 때, r개를 선택하는 경우의 수를 세는 것입니다. 이 값은 흔히 nHr로 표기하며, 다중집합 계수(multiset coefficient)라고도 부릅니다. 예를 들어 "아이스크림 4가지 맛 중에서 같은 맛을 중복으로 떠도 될 때, 2스쿱을 담는 방법은 몇 가지일까?"와 같은 물음에 답할 수 있습니다.
계산기 사용 방법
서로 다른 종류의 개수 n(1 이상)과 고르려는 항목의 개수 r(0 이상)을 입력하세요. 계산 버튼을 누르면 서로 다른 다중집합의 정확한 개수인 nHr 값을 알려줍니다. 두 입력값 모두 음이 아닌 정수이며, 단위를 변환할 필요는 없습니다.
공식 풀이
핵심 항등식은 $$\overline{C}(n,r) = \binom{n + r - 1}{r} = \frac{\left(\text{Types }(n) + \text{Choose }(r) - 1\right)!}{\text{Choose }(r)!\,\left(\text{Types }(n) - 1\right)!}$$ 입니다. 직관적으로 보면, 선택한 \(r\)개의 항목과 종류를 나누는 \((n - 1)\)개의 칸막이를 한 줄로 늘어놓으면 모두 \(n + r - 1\)개의 자리가 생기고, 그중 어디에 항목(혹은 칸막이)을 놓을지 고르는 것과 같습니다. 이 계산기는 거대한 팩토리얼 계산을 피하기 위해 안정적인 곱셈 반복으로 이항계수를 구합니다. 즉 \(m = n + r - 1\), \(k = \min(r, n - 1)\)로 두고 \(i = 1..k\)에 대해 \((m - k + i)\)를 곱하고 \(i\)로 나누는 방식을 사용합니다.
예제 풀이
기본값 \(n = 4\), \(r = 2\)인 경우: $$\overline{C}(4,2) = \binom{4 + 2 - 1}{2} = \binom{5}{2} = \frac{5 \cdot 4}{2 \cdot 1} = 10$$ 입니다. \(\{a, b, c, d\}\) 네 종류로 만들 수 있는 열 가지 조합은 다음과 같습니다: aa, ab, ac, ad, bb, bc, bd, cc, cd, dd.
자주 묻는 질문
일반 조합과 어떻게 다른가요? 일반 조합 \(C(n, r)\)은 중복을 허용하지 않으므로 각 항목을 최대 한 번만 고를 수 있습니다. 반면 중복조합은 같은 항목을 여러 번 고를 수 있어 경우의 수가 더 많아집니다.
r = 0이면 어떻게 되나요? 아무것도 고르지 않는 공집합 선택 한 가지가 존재하므로 \(nHr = 1\) 입니다.
n = 1이면 어떻게 되나요? 종류가 하나뿐이면 그 종류를 \(r\)번 고를 수밖에 없으므로, \(r\) 값과 상관없이 다중집합은 단 하나, 즉 \(nHr = 1\) 입니다.
