중복조합(combination with repetition)

중복조합(combination with repetition)

서로 다른 n개의 원소중에서 중복을 허락하여 r개를 뽑는 방법

ex) r개의 똑같이 생긴 초콜랫을 n 명에게 나눠주는 방법

결론: nHr = n+r-1Cr

문제) 1,2를 중복을 허락해서 3개를 선책!

가지수:
111, 112, 122, 222 // 4가지가 나온다. 하지만 일일히 이렇게 생각하기는 너무 힘들다.
그래서 C 조합을 이용해서 생각을 해보자!
선택 된, 첫 번째 원소에 0을 더하고 두 번째 원소에 1 세 번째 2를 더한다.

즉,
111, 112, 122, 222 는
123, 124, 134, 234 로 변환이 된다.

이렇게 봤더니 숫자 1,2,3,4중 3개를 선책하는 방법과 같더라.
4C3

다른 예,

과일가게에 사과, 배, 귤이 있는데 9개를 사야한다.
3H9 = 11C9


문제

출처: Codeforces C. On Number of Decompositions into Multipliers