数学の力

京大生が数学の定理・公式の証明や入試問題の解説をするブログ.

重複組合せについて


スポンサードリンク

重複組合せ

簡単に組合せ(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と書くこともあります.


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