1.1.6.重複組合せ

$\newcommand{\lnl}{\\[8pt]}$ $\newcommand{\Lnl}{\\[18pt]}$ $\newcommand{\delt}{\mathrm{d}}$ $\newcommand{\comb}{\mathrm{C}}$ $\DeclareMathOperator*{\ssum}{\Sigma}$ $\DeclareMathOperator*{\sprod}{\Pi}$

順列

相異なる$n$個の物から重複を許して$k$個を選ぶことを重複組合せ(combination with repetition)といいます.この場合の重複組合せの総数を${}_n\mathrm{H}_k$と表します.

重複組合せの計算

重複組合せの計算はちょっと技巧的です.
マルと仕切り論法というものを使って説明します.

まず, 仕切りを$n-1$個用意します.

この仕切りの間または両端の$n$個のスペースにマルを$k$個置くことを考えます.

上の図のように,一つの隙間に複数のマルがあってもいいですし,$1$個も無い隙間があってもかまいません.両端も同じく複数のマルがあってもいいですし,$1$個も無くてもかまいません.

このマルの置き方の総数が重複組合せの総数と等しくなります.
なぜならば, これは$n$個のマルを置けるスペースから重複を許して$k$個のスペースを選ぶことに他なりません.重複組合せの定義の「物」を「スペース」に置き換えただけですね.

次に,具体的な計算をします.
先ほどは先にスペースが与えられ,そこにマルを入れていくという考え方をしました.
これは考え方を変えると, 仕切り$n-1$個とマル$k$個を合わせた$n+k-1$個のスペースにどのようにマルを置くかを選び,その他のスペースは仕切りを入れると考えることと同じです.

つまり,この総数は$n+k-1$個から$k$個選ぶ組合せの総数ですから, ${}_{n+k-1}\mathrm{C}_{k}$に等しくなります.

\begin{align}
{}_{n}\mathrm{H}_k = {}_{n+k-1}\mathrm{C}_{k}
\end{align}

また,上記は階乗の記号を使って次のようにも表せます.

\begin{align}
{}_{n}\mathrm{H}_k = \frac{(n+k-1)!}{k!(n-1)!}
\end{align}

まとめ

相異なる$n$個の物から重複を許して$k$個を選ぶことを重複組合せといい, 重複組合せの総数を${}_n\mathrm{H}_k$と表す.

\begin{align}
{}_{n}\mathrm{H}_k = {}_{n+k-1}\mathrm{C}_{k} = \frac{(n+k-1)!}{k!(n-1)!}
\end{align}