重複組合せについて

この記事の所要時間：約 2分36秒

重複組合せ

\(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個をもらえることになりました．選び方は何通りあるか．

キャンディ，クッキー，チョコをそれぞれ２個，１個，２個のようにもらっても構わないですし，クッキーだけを５個もらっても構いません．

この問題が，通常の組合せの問題の重複を許したケースになっていることがわかるでしょうか．(今回のQ.2 の場合は，選択肢がキャンディ，クッキー，チョコの3通りしかないため，鳩ノ巣原理によって必ず重複がでることになります)．

重複組合せの考え方

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

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

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

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

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

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