重複組み合わせ

$ {_{n+r-1}}C_r

$ n種類のものがそれぞれたくさんある。それらから、重複を許して$ r個とるときの組み合わせ

例：3種類の果物から6個選ぶ組み合わせは何通りか

$ x + y + z = 6の非負整数解は何通りか

直感的な理解

〇〇〇｜〇〇〇｜

$ r個のものを$ n-1個のしきりで分ける通り数と同じ。

これは$ r+(n-1)個の枠のなかから、$ r個のものを置く場所を決めるということと同じなので

$ {_{n+r-1}}C_r

また、

3種類の果物から、それぞれ1つ以上選び、合計6個選ぶ組み合わせは何通りか$ \iff x + y + z = 6の正整数解は何通りか

というとき、これはまず1つ以上選んでから、残りを同じように考えると、

〇〇〇｜｜

〇〇〇●｜●｜●

$ {_{n+r-1-n}}C_{r-n}={_{r-1}}C_{r-n}