重複組合せ
簡単に組合せ(2項係数)の復習を
個の中から 個を取り出す方法は で計算できます.これは2項定理に登場する係数であることから,2項係数(binomial coefficients)と呼ばれます.2項係数の性質については「二項係数(コンビネーション)の性質まとめ」,
2項係数の性質の組合せ論的な解釈は「二項係数と組み合わせ問題」を見てください.
重複組合せ
通常の組合せでは, 個から 個を取り出すときに, この中に同じものを含みません.例えば,次の問題を考えます.Q1. 30のクラスで,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箇所を選ぶ方法と同じで,より21通りとなります.
一般に, 種類の中から重複を許して 個を選ぶ方法は, で計算できます.これを,と書くこともあります.
「重複」は「じゅうふく」ではなく「ちょうふく」と読むそうですね.