　【SPONSORED LINK】

2017.09.15

場合の数の基本６｜重複組み合わせの考え方と公式

【場合の数の基本５｜同じものを含む順列の考え方と公式】の続きです．

前回の記事で「同じものを含む順列」について書きました．

その際，重複の処理について詳しく説明しました．この記事で解説する「重複組み合わせ」も重複の処理の仕方がキーになります．

たとえば「赤色，青色，白色の3種類のボールから，全部で9個選ぶこと」を重複組み合わせといいます．

このとき，よくある問題設定として「選ばれない色のボールがあっても良い」とする問題と，「選ばれないボールがあってはならない」とする問題があります．この両者で問題の考え方が異なるので，分からなくなってしまう人が多いようです．

この記事では，この両者の違いについて考えます．

【SPONSORED LINK】

目次

1 重複組み合わせの考え方
2 重複組み合わせの公式
3 補足

重複組み合わせの考え方

次の[問]を考えます．

[問]　赤色，青色，白色の3種類のボールから，全部で9個選ぶ．このとき，次の場合の数を求めよ．

選ばれない色のボールがあっても良い場合．
選ばれない色のボールがあってはならない場合．

[解答]

「丸◯」9個と「仕切り｜」2本でボールの選び方を次のように表す．

左の「仕切り｜」より左にある「丸◯」の個数を赤色のボールの選ぶ個数とし，左の「仕切り｜」と右の「仕切り｜」の間にある「丸◯」の個数を青色のボールの選ぶ個数とし，右の「仕切り｜」より右にある「丸◯」の個数を赤色のボールの選ぶ個数とする．

例えば，◯◯◯｜◯◯｜◯◯◯◯の場合は，赤色のボールが3個，青色のボールが2個，白色のボールが4個を表す．また，◯◯◯｜｜◯◯◯◯◯◯の場合は，赤色のボールが3個，青色のボールが0個，白色のボールが6個を表す．

$(3,4,2)$ 　→　◯◯◯｜◯◯◯◯｜◯◯
$(3,0,6)$ 　→　◯◯◯｜｜◯◯◯◯◯◯
$(2,2,5)$ 　→　◯◯｜◯◯｜◯◯◯◯◯
$(0,0,9)$ 　→　◯◯◯◯◯◯◯◯◯｜｜

1．「丸◯」9個と「仕切り｜」2本による「同じものを含む順列」を考えれば良い．

したがって，求める場合の数は

$\dfrac{(9+2)!}{9!2!}=\dfrac{11!}{9!2!}=55$

である．

【参考記事：場合の数の基本５｜同じものを含む順列の考え方と公式】

2．「丸◯」9個を先に並べておいて，9個の「丸◯」の間の8ヶ所の隙間に「仕切り｜」2本を挿す場合の数を考えれば良い．

したがって，求める場合の数は

${}_{8}\mathrm{C}_{2}=28$

である．

[解答終]

さて，1と2の考え方の違いが分かったでしょうか？また，なぜこのように考えれば良いか分かったでしょうか？

1では選ばれないボールがあっても良いので，例えば◯◯◯｜｜◯◯◯◯◯◯という並びはアリです．一方，2では選ばれないボールがあってはならないので，例えば◯◯◯｜｜◯◯◯◯◯◯という並びはナシです．

1では「丸◯」9個と「仕切り｜」2本による「同じものを含む順列」を考えましたが，この中には◯◯◯｜｜◯◯◯◯◯◯といった「仕切り｜」が連続するものが含まれています．

また，2では「丸◯」9個の間のどこに「仕切り｜」2本を挿し込むかという「組み合わせ」を考えましたが，この中には◯◯◯｜｜◯◯◯◯◯◯といった「仕切り｜」が連続するものは含まれていません．

一方，1では「仕切り｜」が隣り合う場合も考える必要があるので，「仕切り｜」を挿し込んで考える「組み合わせ」は使えません．

また，2では「仕切り｜」が隣り合ってはいけないので，「仕切り｜」を挿し込んで考える「組み合わせ」がぴったりきます．

これらは考え方が分かっていれば間違えることはありません．「仕切り｜」が隣り合っていいのか，隣り合ってはいけないのか，そしてそれぞれの場合にどう考えるのかを確認するようにしてください．

重複組み合わせでは，「選ばれないものがあって良い場合」と「選ばれないものがあってはならない場合」の2種類を考えることが多い．それぞれどのような考え方をするのか理解する．

重複組み合わせの公式

[問]の[解答]と同様にして，次の公式が分かります．

[重複組み合わせの公式]　 $n$ 種類のものから全部で $r$ 個選ぶ場合の数は，

選ばれないものがあっても良い場合は $\f{(n+r-1)!}{(n-1)!r!}$ である．
選ばれないものがあってはならない場合は ${}_{r-1}\mrm{C}_{n-1}$

念のため証明しておきます．

1．選ばれないものがあっても良い場合，「丸◯」 $r$ 個と「仕切り｜」 $n-1$ 個による「同じものを含む順列」を考えれば良いから，

$\dfrac{\{r+(n-1)\}!}{r!(n-1)!}=\dfrac{(n+r-1)!}{r!(n-1)!}$

が求める場合の数となります．

2．選ばれないものがあってはならない場合， $r$ 個の「丸◯」による $r-1$ 個の隙間に「仕切り｜」 $n-1$ 個を挿し込む場所を選ぶ「組み合わせ」を考えれば良いから，

${}_{r-1}\mathrm{C}_{n-1}$

が求める場合の数となります．注意は，

「丸◯」を $n$ 種類に分けるために必要な「仕切り｜」は $n-1$ 本である
$r$ 個の「丸◯」の隙間は $r-1$ 個である

というところですね．ここで間違える人がよくいるので注意してください．

公式を覚えるのではなく，考え方を理解して使うようにしてください．

補足

「選ばれないものがあってはならない問題」を「選ばれないものがあっても良い問題」として解くこともできます．

個人的には，そのように変えて考えるのは不自然だとは思うのですが，それなりに広まっている解き方のようなので念のためここで説明しておきます．

先ほどの[問]の2を「選ばれないものがあっても良い問題」として解いてみます．

[問]　赤色，青色，白色の3種類のボールから，全部で9個選ぶ．このとき，次の場合の数を求めよ．

選ばれない色のボールがあってはならない場合．

[別解]

2．選ばれない色のボールがあってはならないから，全ての色のボールを前もって1つずつ選んでおく．

こうすると，残り6個は選ばれないものがあっても良いから，「丸◯」6個と「仕切り」2本による「同じものが含まれる順列」を考えればよく，

$\dfrac{8!}{6!2!}=28$

が求める場合の数である．

[別解終]

確かに， $\dfrac{8!}{6!2!}={}_{8}\mrm{C}_{2}$ ですから，[解答]のときと同じ式が出てきていることが分かります．

このように，重複組み合わせの問題を全て「選ばれないものがあっても良い場合」に変えて解くこともできます(が，)．

逆に，元から1つずつ持っていると考えて，「選ばれないものがあっても良い問題」を「選ばれないものがあってはならない問題」として解くこともできます．興味がある人は考えてみても良いでしょう．

「選ばれないものがあってはならない問題」を「選ばれないものがあっても良い問題」として解くことができる，またその逆もできる．

【場合の数の基本７｜二項定理の考え方と公式】に続きます．

コメント

ヒロより:

2018年8月9日 11:30 AM

1．「丸◯」9個と「仕切り｜」2本による「同じものを含む順列」を考えれば良い．したがって，求める場合の数は $\frac{9!}{7!2!}=36$ である．
とありますが、この理由がわかりません。。。

返信
1. 山本拓人より:
  
  2018年8月9日 11:40 AM
  
  ご質問ありがとうございます．この部分は私の誤植でした．
  
  全部で「丸◯」9個と「仕切り｜」2本の計11個の同じものを含む順列なので， $\frac{11!}{9!2!}$ ですね．
  ご指摘をありがとうございます．
  
  返信

コメントを残すコメントをキャンセル

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。