【SPONSORED LINK】

場合の数6|「重複組み合わせ」は2パターンでOK!

前回の記事では,「AAAABBの順列」のように「同じものを含む順列」について説明しました.

その際,「重複で割る」ということがとても便利な考え方であることをみました.

この記事では,「A,B,Cの3文字から全部で7個選ぶ場合の数」のように,同じものがいくつかあってよい「重複組み合わせ」の考え方を説明します.

「重複組合せ」の問題設定としては

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

の2パターンが考えられます.

「重複組合せ」が苦手な人は,この両者を混同してしまうことが多いですね.

逆に,この両者をしっかり区別して解法を選べれば,「重複組合せ」は全く怖くありません!

【SPONSORED LINK】

重複組み合わせの考え方

次の問題を考えます.

A,B,Cの3種類のボールから,全部で9個選ぶ.このとき,次の場合の数を求めよ.

  1. 選ばれない種類のボールがあっても良い場合
  2. 選ばれない種類のボールがあってはならない場合

「丸◯」9個と「しきり|」2本でボールの選び方を,次のように表しましょう.

例えば,

  • ◯◯◯|◯◯|◯◯◯◯は,ボールAが3個,ボールBが2個,ボールCが4個
  • ◯◯◯||◯◯◯◯◯◯は,ボールAが3個,ボールBが0個,ボールCが6個

ということにします.つまり,

  • 左にある◯の個数をボールAの個数
  • |の間にある◯の個数をボールBの個数
  • 右にある◯の個数をボールCの個数

と表しています.

たとえば,他には

  • (A,B,C)=(3,4,2)→ ◯◯◯|◯◯◯◯|◯◯
  • (A,B,C)=(3,0,6) → ◯◯◯||◯◯◯◯◯◯
  • (A,B,C)=(2,2,5) → ◯◯|◯◯|◯◯◯◯◯
  • (A,B,C)=(0,0,9) → ◯◯◯◯◯◯◯◯◯||

ですね.

[解答]

(1) 選ばれない種類のボールがあってもいい場合には,単純に◯9個と|2本による「同じものを含む順列」を考えれば良いですね.

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

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

となります.

(2) 選ばれない種類のボールがあってはならない場合は,(1)と考え方が変わってきます.

◯9個を先に並べておいて,8ヶ所の◯の間に|を2本を挿す場合の数を考えれば,求める状況が出来上がります.

◯ ◯ ◯ ◯ ◯ ◯ ◯ ◯ ◯

◯ ◯ ◯|◯ ◯ ◯ ◯ ◯|◯

したがって,求める場合の数は「8個の隙間から2個の隙間を選ぶ場合の数」なので,

\Co{8}{2}=28

となります.

[解答終]

(1)では選ばれないボールがあっても良いので,例えば◯◯◯||◯◯◯◯◯◯という並びはアリです.

一方,(2)では選ばれないボールがあってはならないので,例えば◯◯◯||◯◯◯◯◯◯という並びはナシです.

これが考え方を変えなければならない理由です.

(1)では◯9個と|2本による「同じものを含む順列」を考えたので,こう考えると◯◯◯||◯◯◯◯◯◯といった|が連続するものが含まれることになります.

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

「重複組合せ」の問題では,

  • しきり|が隣り合っていいのか
  • しきり|が隣り合ってはいけないのか

ということをいつでも確認するようにしてください.

重複組み合わせでは,

  • 選ばれないものがあって良い場合
  • 選ばれないものがあってはならない場合

の2種類を考えることが多い.それぞれどのような考え方をするのか理解する.

重複組み合わせの公式

問題のの考え方と同様にして,次の公式が分かります.

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

  1. 選ばれないものがあっても良い場合は\dfrac{(n+r-1)!}{(n-1)!r!}である.
  2. 選ばれないものがあってはならない場合は\Co{r-1}{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個を挿し込む場所を選ぶ「組み合わせ」を考えれば良いから,

\Co{r-1}{n-1}

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

[証明終]

なお,

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

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

補足

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

個人的には,わざわざ言い換えなくても解けるので,少々不自然な気はするのですが,それなりに広まっている解法なのでここで説明しておきます.

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

A,B,Cの3種類のボールから9個選ぶとき,選ばれない種類のボールがあってはならない場合,全部で何通りの選び方があるか

[解答]

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

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

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

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

[解答終]

確かに,\dfrac{8!}{6!2!}=\Co{8}{2}ですから,先ほどの解答と同じ式が出てきていることが分かります.

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

逆に,元から1つずつ持っていると考えて,「選ばれないものがあっても良い問題」を「選ばれないものがあってはならない問題」として解くこともできます.

興味がある人は考えてみても良いでしょう.

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

 

最後まで読んで頂きありがとうございました! YouTubeの授業動画もあります【授業をみてみる

SNSでもご購読できます。

コメント

  1. ヒロ より:

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

    1. 山本 拓人 より:

      ご質問ありがとうございます.この部分は私の誤植でした.

      全部で「丸◯」9個と「仕切り|」2本の計11個の同じものを含む順列なので,\frac{11!}{9!2!}ですね.
      ご指摘をありがとうございます.

コメントを残す

*

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

ページ

トップへ

記事

一覧へ

オススメ

参考書

Twitterを

フォロー

TouTube

を見る