중복조합이란?
중복조합(다중집합 조합이라고도 합니다)은 서로 다른 n가지 종류 중에서 r개를 고를 때, 같은 항목을 여러 번 선택할 수 있고 고르는 순서는 따지지 않는 경우의 가짓수를 세는 방법입니다. 일반 조합과 달리 동일한 항목을 한 번 이상 뽑을 수 있다는 점이 핵심입니다. 이 계산기는 다중집합 공식 \(C(n+r-1, r)\)을 사용해 그 가짓수를 구합니다.
계산기 사용 방법
서로 다른 항목 종류의 수 n(예: 아이스크림 5가지 맛)과 선택할 개수 r(예: 콘에 3스쿱 담기)을 입력하세요. 계산기는 서로 다른 다중집합의 수, 즉 어떤 종류가 몇 번 등장하는지에 따라서만 구분되고 순서는 무시하는 선택 방법의 수를 알려줍니다.
공식 풀이
결과는 다음과 같이 주어집니다.
$$C(n + r - 1, r) = \frac{(n + r - 1)!}{r!\,(n - 1)!}$$직관적으로는 "별과 막대(stars and bars)" 모형으로 이해할 수 있습니다. r개의 똑같은 별을 n−1개의 막대로 나뉜 n개의 칸에 넣는 것이며, 각 배치가 하나의 선택에 대응합니다. 이 계산기는 팩토리얼이 너무 커져서 발생하는 오버플로를 막기 위해 이항계수를 곱셈 방식으로 계산합니다.
예제로 살펴보기
어느 아이스크림 가게가 \(n = 5\)가지 맛을 제공하고, 중복을 허용해 \(r = 3\)스쿱을 한 그릇에 담고 싶다고 해봅시다. 그러면 다음과 같습니다.
$$C(5+3-1, 3) = C(7, 3) = \frac{7!}{3!\cdot 4!} = 35$$즉, 만들 수 있는 서로 다른 그릇은 35가지입니다.
자주 묻는 질문
일반 조합과 무엇이 다른가요? 일반 조합 \(C(n, r)\)은 중복을 허용하지 않지만, 중복조합에서는 같은 종류를 여러 번 고를 수 있습니다.
r이 n보다 커도 되나요? 네, 가능합니다. 중복을 허용하므로 r이 n을 넘어도 됩니다. 예를 들어 3가지 맛에서 10스쿱을 고르는 것도 올바른 경우입니다.
r이 0이면 어떻게 되나요? 아무것도 고르지 않는 방법은 정확히 1가지(공집합 다중집합)이므로 결과는 1입니다.
