場合の数6
重複組み合わせの問題2パターンを攻略する!

場合の数と確率
場合の数と確率

前回の記事では「A,A,A,A,B,Bの6文字を一列に並べてできる文字列の数は何通りあるか?」という同じものを含む順列について説明しました.

この同じものを含む順列では「重複で割る」という考え方ができるととても便利なのでした.

さて,この記事では「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)$ → ◯◯◯◯◯◯◯◯◯||

ですね.

  • ボールの選び方
  • 「丸◯」9個と「しきり|」2本の並べ方

は1つずつ対応していますから,問われているボールの選び方に対応する「丸◯」9個と「しきり|」2本の並べ方を数えればいいことになりますね.

重複組み合わせの解法

(1)の選ばれない種類のボールがあってもいい場合には,前回の記事で説明した同じものを含む順列を用いて解くことができます.

一方,(2)の選ばれない種類のボールがあってはいけない場合には,前々回の記事で説明した組み合わせを用いて解くことができます.

場合の数4|[組み合わせ]の$\Co{n}{r}$の求め方から性質まで攻略
前々回の記事では,「$n$個のものから$r$個選んで並べる場合の数」である順列について説明しました. 「モノを選びとること」を組み合わせといい,「$n$個のものから$r$個選ぶ場合の数」を$\Co{n}{r}$で表します. 順列...
場合の数5|同じものを含むと順列の場合の数はどう変わる?
例えば,A, B, C, D, E, Fの6文字を一列に並べてできる文字列の数は!$通りあります.このことは以前の順列の記事で説明しましたね. それではA, A, A, A, B, Bの6文字を一列に並べてできる文字列の数はどれく...

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

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

(1) ◯9個と|2本の同じものを含む順列を考えればよい.よって,求める場合の数は

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

となる.

(2) ◯9個を先に並べておいて,8ヶ所の◯の間に|を2本を挿す場合の数を考えればよい.

◯ ◯ ◯ ◯ ◯ ◯ ◯ ◯ ◯

◯ ◯ ◯|◯ ◯ ◯ ◯ ◯|◯

よって,求める場合の数は

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

となる.

(1)と(2)で解き方を変えなければならない理由は

  • 選ばれないボールがあっても良い場合,例えば◯◯◯||◯◯◯◯◯◯という並びはアリ
  • 選ばれないボールがあってはならない場合,例えば◯◯◯||◯◯◯◯◯◯という並びはナシ

という違いがあるからですね.

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

一方,(2)では◯9個の間のどこに|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}$が求める場合の数となります.

選ばれないものがあってもよい場合の$\dfrac{(n+r-1)!}{(n-1)!r!}$は${}_{n}H_{r}$と表すこともあります.

なお,

  • 「丸◯」を$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つずつ持っていると考えて,「選ばれないものがあっても良い問題」を「選ばれないものがあってはならない問題」として解くこともできます.

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

コメント

タイトルとURLをコピーしました