重複組合せ
簡単に組合せ(2項係数)の復習を
\(n\) 個の中から \(k\) 個を取り出す方法は \[\binom{n}{k}={}_nC_k=\dfrac{n!}{k!(n-k)!}\] で計算できます.これは2項定理に登場する係数であることから,2項係数(binomial coefficients)と呼ばれます.
2項係数の性質については「二項係数(コンビネーション)の性質まとめ」,
2項係数の性質の組合せ論的な解釈は「二項係数と組み合わせ問題」を見てください.
重複組合せ
通常の組合せでは,\(n\) 個から \(k\) 個を取り出すときに,\(k\) この中に同じものを含みません.例えば,次の問題を考えます.
重複組合せの考え方
重複組合せは,丸と仕切りを使って考えます.上の例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\)と書くこともあります.
「重複」は「じゅうふく」ではなく「ちょうふく」と読むそうですね.