重複組合せについて

重複組合せ$_nH_r$の定義

の目が描いてある正四面体のさいころを2回振って， 出た目の組（順番は考えない）をすべて書き出すと

の10通りとなる．これは，『同じものを含む順列』の考え方を利用し，次のように計算することができる．

無題

無題

まず，各組はの順に並べて表すことにする．例えば， を1個，を1個使って作られる組はと表す．この組に対して，さいころの目を表す2個の $\bigcirc$ と，異なる4文字の“しきり”を表す $(4−1)=3$ 個の $\mid$ からなる順列を，右図のように対応させる． つまり，3つの“しきり” $\mid$ で4つの場所ができるので，その場所にある $\bigcirc$ の個数が，それぞれさいころの の個数を表すものとするのである．

無題

無題

例えば，上の10組のうちの， や や などは， $\bigcirc$ と $\mid$ の順列で右図のように表すことができる．

こうすると，結局，区別しない2個の $\bigcirc$ と区別しない3個の $\mid$ の計5個のものを並べたときの順列を計算すればよいから， 『同じものを含む順列』より

$\text{C}(2,3)=\dfrac{5!}{2!3!}=10$ 通り

と数えることができる．

ここで， $n$ 個のものから，繰り返し用いることを許して， $r$ 個とって作る組について定義しておこう．

重複組合せ $_{n}\mathrm{H}_{r}$ の定義

「区別する $n$ 個のものから，繰り返し用いることを許して， $r$ 個取り出して作った組」 のことを $n-r$ 重複ちょうふく組合せ(combination with repetitions)といい，その組の総数を $\boldsymbol{_{n}\mathrm{H}_{r}}$ と表す．

この例では

\[_{4}\mathrm{H}_{2}=\text{C}(2,~3)=\frac{5!}{2!3!}=10\]

である．

重複組合せ$_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}

である．

以上，まとめると

重複組合せ $_{n}\mathrm{H}_{r}$ の計算

区別する $n$ 個のものから，繰り返し用いることを許して， $r$ 個取り出して作る組の総数 $_{n}\mathrm{H}_{r}$ は，同じものを含む順列の考え方で計算でき

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

となる．

重複組合せの計算練習

次の値を求めよ．

  1. $_{7}\mathrm{H}_{2}$
  2. $_{4}\mathrm{H}_{3}$
  3. $_{5}\mathrm{H}_{3}$
  4. $_{3}\mathrm{H}_{5}$

  1. $_{7}\mathrm{H}_{2}=\ _{7+2-1}\mathrm{C}_{2}=\dfrac{8\cdot7}{2\cdot1}=\boldsymbol{28}$

    2. $_{7}\mathrm{H}_{2}=\dfrac{7\cdot8}{2\cdot1}$ と計算してもよい

  2. $_{4}\mathrm{H}_{3}=\ _{4+3-1}\mathrm{C}_{3}=\dfrac{6\cdot5\cdot4}{3\cdot2\cdot1}=\boldsymbol{20}$

    3. $_{4}\mathrm{H}_{3}=\dfrac{4\cdot5\cdot6}{3\cdot2\cdot1}$ と計算してもよい

  3. $_{5}\mathrm{H}_{3}=\ _{5+3-1}\mathrm{C}_{3}=\dfrac{7\cdot6\cdot5}{3\cdot2\cdot1}=\boldsymbol{35}$

    4. $_{5}\mathrm{H}_{3}=\dfrac{5\cdot6\cdot7}{3\cdot2\cdot1}$ と計算してもよい

  4. $_{3}\mathrm{H}_{5}=\ _{3+5-1}\mathrm{C}_{5}=\dfrac{7\cdot6\cdot5\cdot4\cdot3}{5\cdot4\cdot3\cdot2\cdot1}=\boldsymbol{21}$

    5. $_{3}\mathrm{H}_{5}=\dfrac{3\cdot4\cdot5\cdot6\cdot7}{5\cdot4\cdot3\cdot2\cdot1}$ と計算してもよい

ボールと箱のモデル5

例えば， $_{5}\mathrm{H}_{3}$ の定義は

「区別する5個のものから，繰り返し用いることを許して，3個とりだしてつくる組の総数」

であったが，これはボールと箱のモデルを使って

「区別しない3個のボールを，区別する5個の箱に配る(何個でもよい)場合の総数」

といいかえることができる．それには，次のように考えるとよい．

説明文

説明文

準備として，ボールは区別しないので，それを $\bigcirc,\bigcirc,\bigcirc$ とし， 箱は区別するので番号をつけ，それを としておく．

例えば，区別しない3個のボールを，区別する5個の箱に，図のように配ったとする．

このときは，5−3重複組合せのうちの $\{2,2,5\}$ と対応すると考えることができる．

また逆に，5−3重複組合せのうちの $\{2,2,5\}$ は，図のようなボールの配り方に対応すると考えることができる．

これ以外の5−3重複組合せも，ボールの箱への配り方と1対1に対応するので， 結局，ボールの箱への配り方の総数は $_{5}\mathrm{H}_{3}$ と一致するといえる．

一般に，次のようにまとめることができる．

重複組合せ $_{n}\mathrm{H}_{r}$ のボールと箱のモデル

重複組合せ $_{n}\mathrm{H}_{r}$ はボールと箱のモデルを用いて

「区別しない $r$ 個のボールを，区別する $n$ 個の箱に配る(何個でもよい)場合の総数」

と考えることができる．

吹き出し無題

ただし，この考え方ではうまく計算できないので，実際に計算するときには重複組合せ $_{n}\mathrm{H}_{r}$ の定義でみたように，“ $\bigcirc$ と $\mid$ の並べ方”の問題へ帰着することになる．

重複組合せ

  1. 3種類の果物，りんご，かき，なしを使って，7個入りの果物かごを作る．1つも入らない種類があってもよいとすると，何通りの果物かごができるか求めよ．
  2. 1. で，3種類の果物を最低1個は入れるものとすると，何通りの果物かごができるか求めよ．

  1. 【解1：重複組合せで考える】

    2. 区別する3種類のものを，重複を許して7つ取り出し組を作ればよいので

    $_{3}\mathrm{H}_{7}=\ _{3+7-1}\mathrm{C}_{7}=\boldsymbol{36}$ 通り

    $\uparrow\ _{3}\mathrm{H}_{7}=\dfrac{3\cdot4\cdot5\cdot6\cdot7\cdot8\cdot9}{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}$

    と計算してもよい

    【解2：同じものを含む順列に帰着させる】

    7個のものを $\bigcirc$ を使って

    と表すことにする．

    これらを2つの“しきり” $\mid$ によって，3つの区間に分け，左から順にりんご，かき，なしと対応させる． こうすると，例えば

    \begin{align} \bigcirc\mid\bigcirc\bigcirc\mid\bigcirc\bigcirc\bigcirc\bigcirc \end{align}

    は，りんご1個，かき2個，なし4個を表し

    \begin{align} \bigcirc\bigcirc\bigcirc\mid\mid\bigcirc\bigcirc\bigcirc\bigcirc \end{align}

    は，りんご3個，かき0個，なし4個を表す．

    7個の $\bigcirc$ と2個の $\mid$ の計9個のものを1列に並べる並べ方の数が，考える果物かごの数である． よって

    $\text{C}(7,2)=\ _{7+2}\mathrm{C}_{2}=\boldsymbol{36}$ 通り

    $\uparrow$ 同じものを含む順列

  2. 【解1：重複組合せで考える】

    3. まず，りんご，かき，なしから１つずづ計3個取り出しておく．残りの4つについて，重複を許して組を作ればよいので

    $_{3}\mathrm{H}_{4}=\ _{3+4-1}\mathrm{C}_{4}=\boldsymbol{15}$ 通り

    $\uparrow\ _{3}\mathrm{H}_{4}=\dfrac{3\cdot4\cdot5\cdot6}{4\cdot3\cdot2\cdot1}$

    と計算してもよい

    【解2：『資源配分』に帰着させる】

    $\uparrow$ この解法について詳しくは，次の資源配分を参照のこと

    1. と同様に，7個のものを $\bigcirc$ を使って

    と表すことにする．

    りんご，かき，なしそれぞれから，最低1個はとりだすので，今度は2つの“しきり” $\mid$ を6ヶ所ある $\bigcirc$ の“すきま”にいれ，3つの区間に分け，左から順にりんご，かき，なしと対応させる．こうすると，例えば

    \begin{align} \bigcirc\mid\bigcirc\bigcirc\mid\bigcirc\bigcirc\bigcirc\bigcirc \end{align}

    は，りんご1個，かき2個，なし4個を表し

    \begin{align} \bigcirc\bigcirc\bigcirc\bigcirc\mid\bigcirc\mid\bigcirc\bigcirc \end{align}

    は，りんご4個，かき1個，なし2個を表す．

    7個の $\bigcirc$ によって作られる，6ヶ所の“すきま”から2個の $\mid$ の入る場所を選ぶ選び方の数が，考える果物かごの数である．よって

    $_{6}\mathrm{C}_{2}=\boldsymbol{15}$ 通り