重複組合せについて

この記事の所要時間: 236

重複組合せ

簡単に組合せ(2項係数)の復習を

\(n\) 個の中から \(k\) 個を取り出す方法は \[\binom{n}{k}={}_nC_k=\dfrac{n!}{k!(n-k)!}\] で計算できます.これは2項定理に登場する係数であることから,2項係数(binomial coefficients)と呼ばれます.

2項係数の性質については「二項係数(コンビネーション)の性質まとめ」,
2項係数の性質の組合せ論的な解釈は「二項係数と組み合わせ問題」を見てください.

重複組合せ

通常の組合せでは,\(n\) 個から \(k\) 個を取り出すときに,\(k\) この中に同じものを含みません.例えば,次の問題を考えます.

Q1. 30のクラスで,5人の委員を選ぶことになりました.委員メンバーの選び方は何通りあるか.
答えはもちろん \[{}_{30}C_5\] 通りですが,この問題で委員の5人の中に同じ人を複数回選ぶことはできません(Aさん,Cさん,Fさん,Rさん,Wさんのように5人を選ばないといけない.Aさん,Cさん,Fさん,Fさん,Rさんのように重複があってはいけません).

さて,重複組合せでは,この重複を許した場合を考えます.
例えば,次のような問題を考えます.
Q2. かごにキャンディ,クッキー,チョコが入っています.この中から5個をもらえることになりました.選び方は何通りあるか.
キャンディ,クッキー,チョコをそれぞれ2個,1個,2個のようにもらっても構わないですし,クッキーだけを5個もらっても構いません.
この問題が,通常の組合せの問題の重複を許したケースになっていることがわかるでしょうか.(今回のQ.2 の場合は,選択肢がキャンディ,クッキー,チョコの3通りしかないため,鳩ノ巣原理によって必ず重複がでることになります).

重複組合せの考え方

重複組合せは,丸と仕切りを使って考えます.上の例Q.2の場合を例に説明します.

まず,丸を5つと,仕切り2つを1列に並べ,仕切りの間にある丸の数を順にキャンディ,クッキー,チョコの個数とみなします.このとき,2つの仕切りが隣り合ったり,端にあっても構いません.

このように考えると,キャンディ,クッキー,チョコを合計5個選ぶ方法と,5個の丸と2個の仕切りを1列に並べる方法は同じであることが分かります.

従って,キャンディ,クッキー,チョコの選び方は,7箇所から仕切りを置く2箇所を選ぶ方法と同じで,\[{}_7C_2=\frac{7!}{2!5!}=21\]より21通りとなります.


一般に,\(n\) 種類の中から重複を許して \(k\) 個を選ぶ方法は,\[{}_{n+k-1}C_{k}\] で計算できます.これを,\({}_nH_k\)と書くこともあります.


「重複」は「じゅうふく」ではなく「ちょうふく」と読むそうですね.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加