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