https://put3y19ea1n0r9er.hatenablog.com/entry/2023/04/12/185130

問題です。解答は下部に載せました。

問題： $\displaystyle { n }$ および $\displaystyle { r }$ を $\displaystyle { 1 }$ 以上の任意の整数とする。このとき、

$\displaystyle { \binom{n + r -1}{r} = \sum_{k = 1}^{\min{[n,r]}} \binom{n}{k} \cdot \binom{r - 1}{r - k} }$

となることを示せ。

解答：題意の式の左辺は重複組合せのよく知られた公式である。ところで、 $\displaystyle { n }$ 種類のものから重複を許して $\displaystyle { r }$ 個選ぶ場合、選ばれるものの種類の数を $\displaystyle { k }$ とすれば、明らかに $\displaystyle { 1 \leq k \leq \min{[n,r]} }$ である。そして、 $\displaystyle { n }$ 種類のものから $\displaystyle { k }$ 種類を選ぶときの選び方の総数は $\displaystyle { \binom{n}{k} }$ 通りであり、それぞれの選び方について重複組合せの総数を考えると、 $\displaystyle { k }$ 種類のものが少なくとも一つずつ選ばれていることに気を付ければ、それは

$\displaystyle { \binom{k + \left( r - k \right) - 1}{r - k} = \binom{r - 1}{r - k} }$

通りある。よって、 $\displaystyle { n }$ 種類のものからまず $\displaystyle { k }$ 種類のものを選び、選ばれた $\displaystyle { k }$ 種類のものから重複を許して $\displaystyle { r }$ 個選ぶ場合の数は

$\displaystyle { \binom{n}{k} \cdot \binom{r - 1}{r - k} }$

となり、これをすべての $\displaystyle { k }$ について考えて足し合わせたものが $\displaystyle { n }$ 種類のものから重複を許して $\displaystyle { r }$ 個選ぶ場合の数となるから、題意の式が成り立つ。