중복 조합 nHr 은 왜 n+r-1Cr 일까?

왜 중복조합과 조합 사이에

nHr = n+r-1Cr 관계가 성립하는지

과외돌이에게 설명하기 위해 고안한 예시.

[문제]

가게에서 n가지 사탕을 판다.

나는 사탕 r개를 사려고 한다.

같은 사탕을 중복해서 골라도 된다면

사탕을 고르는 방법은 몇 가지인가?

.

.

.

[풀이]

사탕 진열대를 살펴보면서

맘에 드는 사탕을 장바구니에 담자.

내가 할 수 있는 행동은

①사탕을 담기

②한 칸 옆으로 이동하기

이렇게 두 가지 뿐.

쇼핑을 마치기 위해서는
[담기]를 r번

[이동]을 n-1번

해야한다.

[담기]와 [이동]을 섞는 가짓수와

장바구니 내용물이 1:1로 대응한다.

따라서 정답은

[담기] r개와

[이동] n-1개를

배열하는 가짓수와 같다.

이는 n+r-1Cr 이다.

(같은 것을 포함한 순열)