組合せと重複組合せの公式

 

組合せ Combination

 まずは 順列 の復習です。4 種類のアルファベット {a, b, c, d} から 3 つを取り出して 1 列に並べる方法は何通りあるか計算してみましょう。
 
\[_4\mathrm{P}_3=4\times 3\times 2=24\]
通りですね。この中に含まれる順列は

[a, b, c], [a, b, d], [a, c, d], [b, c, d]

のいずれかの文字セットで構成されています。各文字セットごとに整理分類して全部並べてみましょう。

abc, acb, bac, bca, cab, cba

abd, adb, bad, bda, dab, dba

acd, adc, cad, cda, dac, dca

bcd, bdc, cbd, cdb, dbc, dcb

 ちゃんと 24 通りありますね。そこで今度は使われている文字が同じものを区別しないで選び出す方法が何通りあるか考えます。つまり各行はまとめて 1 種類のものと考えて左端にある

abc, abd, acd, bcd

だけを抜き出します。その総数は 24 ÷ 6 = 4 となります。各行にある順列の数は 3! と書くこともできるので、求める数 $x$ は

\[x=\frac{_4\mathrm{P}_3}{3!}=\frac{24}{6}=4\]
と表すこともできます。

 一般に $n$ 個の異なったものから $r$ 個取り出して 1 組としたものを

$n$ 個のものから $r$ 個とった組合せ

とよび、この組合せの総数 $_n\mathrm{C}_r$ は
\[_n\mathrm{C}_r=\frac{_n\mathrm{P}_r}{r!}=\frac{n!}{r!(n-r)!} \tag{A}\]によって計算されます。

 組合せ $_n\mathrm{C}_r$ の計算について1つ補足しておきます。
 たとえば、ある 10 個のものから 3 個を取り出すとき、取り出す 3 個を決めることは、あとに残る 7 個を決めているのと等しいことになります。つまり
 
\[_{10}\mathrm{C}_3=_{10}\mathrm{C}_7=120\]
です。これは公式 (A) の $r$ を $n-r$ で置き換えても簡単に確かめることができます。すなわち
 
\[_n\mathrm{C}_{n-r}=\frac{n!}{(n-r)!r!}=_n\mathrm{C}_r\]
となっています。
 

重複組合せ Combination with Repetition

 この記事を書いているのは 6 月半ばです。そろそろアイスが食べたくなる季節ですね。さて、コンビニに行って、チョコアイス、バニラアイス、抹茶アイスの 3 種類から選んで 5 つを買うとしたら、その組合せは何通りあるでしょうか。ただしバニラを1つも買わないというような選択肢もありだとします。こうした問題を考えるときは「仕切り」を使うのが定石です。アイスを 〇 で表し、チョコ、バニラ、抹茶の間に適当に仕切りを入れてみましょう。

 Excel重複組合せ(アイスと仕切り)

 (A) はチョコ 2 個、バニラ 1 個、抹茶 1 個という状態を表しています。また、(B) は仕切りが一番左端にあり、これはチョコは1つも買わずに、バニラ 2 個、抹茶 3 個を選ぶという意味です。つまり 〇 と | を合わせた 7 個の順列を考えて、そこから 〇 と | の重複を取り除くことで選び方の総数を
 
\[\frac{7!}{2!\:5!}=\frac{7!}{2!\,(7-2)!}={}_7\mathrm{C}_2=21\]
と計算することができます。これを一般化すると、$n$ 種類のものから重複を許して $r$ 個とることは、$r$ 個の 〇 と $n-1$ 個の | を 1 列に並べる順列に等しく、その選び方の総数は
 
\[\frac{(r+n+1)!}{r!\,(n-1)!}=\:{}_{n+r-1}\mathrm{C}_r\]
と計算することができます。これを 重複組合せ (combination with repetition) とよび、$_n\mathrm{H}_r$ という記号で表します。

 $n$ 種類のものから $r$ 個選ぶ組合せの個数は
\[_n\mathrm{H}_r=\:{}_{n+r-1}\mathrm{C}_r\]

 ≫ 数学事典

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください