重複組合せ$_nH_r$の計算

区別する $n$ 個のものから，繰り返し用いることを許して， $r$ 個取り出して作る組の総数 $_{n}\mathrm{H}_{r}$ も，先程の例と同じように考えることができる．

まず，右図のように， $r$ 個の $\bigcirc$ と，（ $n$ 個の入る場所を作るための） $n−1$ 個の“しきり” $\mid$ を並べる． こうしておいてから，区別しない $r$ 個の $\bigcirc$ と区別しない $n−1$ 個の $\mid$ の計 $r+n−1$ 個のものを並べたときの 『同じものを含む順列』を計算すればよいので

\[_{n}\mathrm{H}_{r}=\text{C}(r,~n-1)=\ _{r+n-1}\mathrm{C}_{r}\]

となる．普通 $_{n}\mathrm{H}_{r}$ を計算するには，このように $\bigcirc$ と $\mid$ の並べ方を考えて $_{r+n−1}\mathrm{C}_{r}$ に帰着してから計算するとよい．

さて，ここでさらに $_{r+n−1}\mathrm{C}_{r}$ の計算をすすめてみると

\begin{align} &_{r+n-1}\mathrm{C}_{r}\\ =\ &\frac{(r+n-1)!}{(n-1)!r!}\\ =\ &\frac{\overbrace{(r+n-1)(r+n-2)\cdots{n}}^{r個の積}(n-1){\cdots}2{\cdot}1}{(n-1)\cdots2\cdot1\cdot{r!}}\\ =\ &\frac{\overbrace{n(n+1)\cdots(n+r-2)(n+r-1)}^{r個の積}}{r(r-1)\cdots2\cdot1} \end{align}

つまり

\begin{align} _{n}\mathrm{H}_{r}=&\frac{\overbrace{n(n+1)\cdots(n+r-2)(n+r-1)}^{r個の積}}{r(r-1)\cdots2\cdot1} \end{align}

と計算することもできる．この式は， $_{n}\mathrm{C}_{r}$ と比較すると覚えやすい．例えば

\begin{align} _{6}\mathrm{C}_{3}&=\frac{\overset{下がっていく}{\overrightarrow{6\cdot5\cdot4}}}{3\cdot2\cdot1},\ _{6}H_{3}=\frac{\overset{上がっていく}{\overrightarrow{6\cdot7\cdot8}}}{3\cdot2\cdot1} \end{align}

である．

以上，まとめると