중복조합 계산기

아이스크림 가게에 맛이 8가지 있고, 컵에 세 스쿱을 담으려고 한다. 세 가지 다른 맛을 고를 수도 있고, 초콜릿 맛 두 스쿱과 피스타치오 맛 한 스쿱을 고를 수도 있으며, 바닐라 맛만 세 스쿱을 고를 수도 있다. 순서는 상관없다. 초콜릿 맛이 맨 위에 있든 아래에 있든 같은 아이스크림이다. 고르는 방법은 모두 몇 가지일까? 이것을 구하는 것이 중복조합이다. 즉 중복을 허락하여 n가지 종류에서 k개를 택하는 방법의 수이다.

같은 종류를 두 번 고를 수 없다면 보통의 조합이 되고, 조합의 수 계산기로 구하면 된다.

계산 방법

계산기는 다음 공식으로 계산한다.

$${}_n{\mathrm{H}}_k={}_{n+k-1}{\mathrm{C}}_k$$

8가지 맛에서 세 스쿱을 고르는 것은 공 3개와 맛을 구분하는 칸막이 7개를 한 줄로 늘어놓는 것으로 생각할 수 있다. 첫 번째 칸막이 앞의 공은 바닐라 맛, 첫 번째와 두 번째 칸막이 사이의 공은 초콜릿 맛, 이런 식이다. 아이스크림을 고르는 방법 하나하나가 이런 배열 하나에 대응하므로, 10개의 자리 중에서 공을 놓을 3자리를 택하는 방법의 수를 구하면 된다.

$${}_8{\mathrm{H}}_3={}_{8+3-1}{\mathrm{C}}_3={}_{10}{\mathrm{C}}_3=\frac{10\cdot 9\cdot 8}{3\cdot 2\cdot 1}=120$$

8가지 맛에서 세 스쿱을 고르는 방법은 120가지이다. 공식을 자세히 유도하는 과정은 중복조합 글에서 볼 수 있다.