　【SPONSORED LINK】

場合の数６｜「重複組み合わせ」は２パターンでOK！

2017/9/15 2019/10/30 場合の数

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

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

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

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

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

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

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

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

場合の数の一連の記事はこちら

【場合の数１｜「和の法則」と「積の法則」は超アタリマエ！】
【場合の数２｜「順列_nP_k」の考え方と公式は超カンタン！】
【場合の数３｜実はカンタンな円順列と数珠順列の考え方】
【場合の数４｜「組み合わせ_nC_k」を考え方から性質まで攻略】
【場合の数５｜同じものを含むと順列はどう変わる？】
【場合の数６｜「重複組み合わせ」は２パターンでOK！】
【場合の数７｜二項定理を理解しよう！場合の数を使って導出！】
【場合の数８｜二項係数_nC_kの性質と「パスカルの三角形」】
【場合の数９｜多項定理とは？実は二項定理と同じ考え方！】

【SPONSORED LINK】

重複組み合わせの考え方

次の問題を考えます．

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

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

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

となります．

【場合の数５｜同じものを含むと順列はどう変わる？】

ABCDEFの6文字を一列に並べる場合の数は $6!$ 通りですが，AAAABBの6文字を一列に並べる場合の数は単純に $6!$ 通りではありません．このように，「同じものを含む順列」では，単純に階乗で場合の数を求めることはできません．同じものを含む順列では，重複の処理の仕方がポイントになります．

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

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

◯ ◯ ◯ ◯ ◯ ◯ ◯ ◯ ◯
↓
◯ ◯ ◯｜◯ ◯ ◯ ◯ ◯｜◯

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

$\Co{8}{2}=28$

となります．

[解答終]

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

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

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

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

【次の記事：場合の数７｜二項定理を理解しよう！場合の数を使って導出！】

展開公式の

$(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$ が大きい場合には[二項定理]を使うことになります．[二項定理]を理解するためには，今回の記事の「重複組合せ」(「同じものを含む順列」)の考え方を用います．