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

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

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

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

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

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

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

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

逆に,この2パターンをしっかり区別して解法を選べることができるようになれば,「重複組合せ」は全く怖くありません.

この記事では,この2パターンをどのように区別して考えるかを説明します.

重複組み合わせの考え方

次の問題を考えます.

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本による「同じものを含む順列」を考えれば良いですね.

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

\begin{align*} \frac{(9+2)!}{9!2!}=\dfrac{11!}{9!2!}=55 \end{align*}

となります.

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

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

◯ ◯ ◯ ◯ ◯ ◯ ◯ ◯ ◯

◯ ◯ ◯|◯ ◯ ◯ ◯ ◯|◯

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

\begin{align*} \Co{8}{2}=28 \end{align*}

となります.

(1)と(2)で考え方を変えなければならないのは,

  • (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$個による「同じものを含む順列」を考えれば良いから,

\begin{align*} \dfrac{\{r+(n-1)\}!}{r!(n-1)!}=\dfrac{(n+r-1)!}{r!(n-1)!} \end{align*}

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

(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本による「同じものが含まれる順列」を考えればよく,

\begin{align*} \frac{8!}{6!2!}=28 \end{align*}

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

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

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

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

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

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

最後までありがとうございました!

参考になった方は是非シェアをお願いします!

フォローする

以下の関連記事もいかがですか?

SPONSORED LINK
関連記事

記事一覧はこちらからどうぞ!

記事

一覧へ

Twitterを

フォロー

TouTube

を見る

オススメ

参考書

大学数学の

姉妹ブログ