중복조합

nHr = (n+r-1)Cr 으로 적을 수 있다.

가장 기본적인 예제를 설명해보자면. 중국집에 짬짜볶 3가지의 메뉴가 있다. 5명의 손님이 왔을 때 손님이 주문한 메뉴의

조합을 고르는 경우가 중복조합 문제가 된다. 먼저 그릇 다섯 개를 준비한다고 가정해보자.

ㅇㅇㅇㅇㅇ 

그리고 다음과 같이 경계선을 그릇 사이에 임의로 둬 보겠다.

ㅇㅇ/ㅇ/ㅇㅇ 

이렇게 만들었을 때 경계선으로 구분된 그룹을 앞에서부터 짜장면, 짬뽕, 볶음밥 그룹으로 나눌 수 있는 것이다.

메뉴가 3가지이기 때문에 3가지 그룹을 만들면 된다. 이 때 필요한 경계선의 개수는 메뉴의 개수 -1 이다. 즉 위의 예에서는 3-1인 2가 된다.

결국 그릇의 갯수 + 경계선의 갯수인 7개 중에 접시 5개를 선택하면 되겠다.