重複組合せについて

重複組合せ$_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}$ と計算してもよい

  3. $_{4}\mathrm{H}_{3}=\ _{4+3-1}\mathrm{C}_{3}=\dfrac{6\cdot5\cdot4}{3\cdot2\cdot1}=\boldsymbol{20}$
  4. $_{4}\mathrm{H}_{3}=\dfrac{4\cdot5\cdot6}{3\cdot2\cdot1}$ と計算してもよい

  5. $_{5}\mathrm{H}_{3}=\ _{5+3-1}\mathrm{C}_{3}=\dfrac{7\cdot6\cdot5}{3\cdot2\cdot1}=\boldsymbol{35}$
  6. $_{5}\mathrm{H}_{3}=\dfrac{5\cdot6\cdot7}{3\cdot2\cdot1}$ と計算してもよい

  7. $_{3}\mathrm{H}_{5}=\ _{3+5-1}\mathrm{C}_{5}=\dfrac{7\cdot6\cdot5\cdot4\cdot3}{5\cdot4\cdot3\cdot2\cdot1}=\boldsymbol{21}$
  8. $_{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$ 同じものを含む順列

  3. 【解1:重複組合せで考える】
  4. まず,りんご,かき,なしから1つずづ計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}$ 通り