前回の記事では,「AAAABBの順列」のように「同じものを含む順列」について説明しました.
その際,「重複で割る」ということがとても便利な考え方であることをみました.
この記事では,「A,B,Cの3文字から全部で7個選ぶ場合の数」のように,同じものがいくつかあってよい「重複組み合わせ」の考え方を説明します.
「重複組合せ」の問題設定としては
- 選ばれない色のボールがあっても良い場合
- 選ばれないボールがあってはならない場合
の2パターンが考えられます.
「重複組合せ」が苦手な人は,この両者を混同してしまうことが多いですね.
逆に,この2パターンをしっかり区別して解法を選べることができるようになれば,「重複組合せ」は全く怖くありません.
この記事では,この2パターンをどのように区別して考えるかを説明します.
一連の記事はこちら
【場合の数1|[和の法則]と[積の法則]は超アタリマエ!】
【場合の数2|[順列]のnPrの考え方と公式は超カンタン!】
【場合の数3|実はカンタンな円順列と数珠順列の考え方】
【場合の数4|[組み合わせ]のnCrの求め方から性質まで攻略】
【場合の数5|同じものを含むと順列の場合の数はどう変わる?】
【場合の数6|[重複組み合わせ]は2パターンでOK!】←今の記事
【場合の数7|二項定理を理解しよう!場合の数を使って導出!】
【場合の数8|展開が楽にできる「パスカルの三角形」の考え方】
【場合の数9|多項定理とは?実は二項定理と同じ考え方!】
重複組み合わせの考え方
次の問題を考えます.
A, B, Cの3種類のボールから,全部で9個選ぶ.このとき,次の場合の数を求めよ.
- 選ばれない種類のボールがあっても良い場合
- 選ばれない種類のボールがあってはならない場合
「丸◯」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本による「同じものを含む順列」を考えれば良いですね.
したがって,求める場合の数は
となります.
ABCDEFの6文字を一列に並べる場合の数は$6!$通りですが,AAAABBの6文字を一列に並べる場合の数は単純に$6!$通りではありません.このように,「同じものを含む順列」では,単純に階乗で場合の数を求めることはできません.同じものを含む順列では,重複の処理の仕方がポイントになります.
(2) 選ばれない種類のボールがあってはならない場合は,(1)と考え方が変わってきます.
◯9個を先に並べておいて,8ヶ所の◯の間に|を2本を挿す場合の数を考えれば,求める状況が出来上がります.
◯ ◯ ◯ ◯ ◯ ◯ ◯ ◯ ◯
↓
◯ ◯ ◯|◯ ◯ ◯ ◯ ◯|◯
したがって,求める場合の数は「8個の隙間から2個の隙間を選ぶ場合の数」なので,
となります.
(1)と(2)で考え方を変えなければならないのは,
- (1)では選ばれないボールがあっても良いので,例えば◯◯◯||◯◯◯◯◯◯という並びはアリ
- (2)では選ばれないボールがあってはならないので,例えば◯◯◯||◯◯◯◯◯◯という並びはナシ
という違いがあるからですね.
(1)では◯9個と|2本による「同じものを含む順列」を考えたので,こう考えると◯◯◯||◯◯◯◯◯◯といった|が連続するものが含まれることになります.
一方,(2)では◯9個の間のどこに|2本を挿し込むかという「組み合わせ」を考えたので,この中には◯◯◯||◯◯◯◯◯◯といった「仕切り|」が連続するものは含まれていません.
「重複組合せ」の問題では,
- 仕切り|が隣り合っていいのか
- 仕切り|が隣り合ってはいけないのか
ということをいつでも確認するようにしてください.
重複組み合わせでは,
- 選ばれないものがあって良い場合
- 選ばれないものがあってはならない場合
の2種類を考えることが多い.それぞれどのような考え方をするのか理解する.
重複組み合わせの公式
問題のの考え方と同様にして,次の公式が分かります.
[重複組み合わせ] $n$種類のものから全部で$r$個選ぶ場合の数は,
- 選ばれないものがあっても良い場合は$\dfrac{(n+r-1)!}{(n-1)!r!}$である.
- 選ばれないものがあってはならない場合は$\Co{r-1}{n-1}$
(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!}=\Co{8}{2}$ですから,先ほどの解答と同じ式が出てきていることが分かります.
このように,重複組み合わせの問題を全て「選ばれないものがあっても良い場合」に変えて解くこともできます.
逆に,元から1つずつ持っていると考えて,「選ばれないものがあっても良い問題」を「選ばれないものがあってはならない問題」として解くこともできます.
興味がある人は考えてみても良いでしょう.
「選ばれないものがあってはならない問題」を「選ばれないものがあっても良い問題」として解くこともできる,
【次の記事:場合の数7|二項定理を理解しよう!場合の数を使って導出!】
展開公式の
- $(a+b)^2=a^2+2ab+b^2$
- $(a+b)^3=a^3+2a^2b+3ab^2+b^3$
などは単純に展開することで得られますが,$(a+b)^7$など$(a+b)^n$で$n$が大きい場合には[二項定理]を使うことになります.[二項定理]を理解するためには,今回の記事の「重複組合せ」(「同じものを含む順列」)の考え方を用います.