重複組み合わせ nHr の求め方

n 種類から重複を許して r 個選ぶ場合の数 nHr = (n + r − 1)Cr を求めます。3 種類のアイスから 2 個選ぶ（同じ味を 2 個でもよい）ような数え方です。

解説

重複組み合わせは、 $n$ 種類のものから 同じものを何個選んでもよい ことにして、 $r$ 個選ぶ場合の数です。

_nH_r = {}_{n+r-1}C_r

ふつうの組み合わせ（1 種類につき 1 個まで）とは別ものです。

例

3 種類のアイス（バニラ、チョコ、抹茶）から 2 個買います。同じ味を 2 個でもかまいません。

_3H_2 = {}_{3+2-1}C_2 = {}_4C_2 = \dfrac{4 \times 3}{2 \times 1} = 6

実際に並べてみると、バニラ 2 個、チョコ 2 個、抹茶 2 個、バニラとチョコ、バニラと抹茶、チョコと抹茶の 6 通りです。

仕切りを使うと分かります。買う 2 個を「○」、種類の境目を「|」で表すと、たとえば「○|○|」はバニラ 1 個とチョコ 1 個、「○○||」はバニラ 2 個です。

3 種類なら仕切りは 2 本。○ が 2 個と | が 2 本、合わせて 4 個の場所から、○ を置く 2 か所を選べばよいので $_4C_2$ 通りになります。一般に、 $r$ 個の ○ と $n-1$ 本の仕切りを並べる問題なので $_{n+r-1}C_r$ です。