- ベストアンサー
重複組合わせとは？なぜ重複組合わせを使うのか？
- 重複組合わせは、数値やオブジェクトから一定数の要素を重複を許して取り出し、組を作る方法です。
- 一つの箱に入っている番号付きの球から順に取り出し、一定数の組を作る際に、重複組合わせを使うことで、組合せの数を効率的に求めることができます。
- 重複組合わせは、順序を区別しないため、取り出した要素の順番は考慮せず、要素の種類と数だけを考えます。取り出す要素の数をrとした場合、n個の要素から重複組合わせを求める際には、n＋r－１個からr個取り出す組合せに変換することができます。
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
少し端折ってないですか？ 1番からn番までの番号が書いてある球がそれぞれ十分にたくさんある中からr個取り出すってことですよね？つまり、1番ばっかりr個というような場合もあると。 そしてこれは、1番からn+r-1番までの番号が書いてある球がそれぞれ1個ずつある中からr個取り出すときの場合の数と同じであると。 組み合わせなので、例えば3個取り出す場合、「1番1番3番」と取り出した場合も「1番3番1番」と取り出した場合も同じとみなすことになります。ですので、どの組み合わせも小さい順に並べて考えてもかまいません。 この、小さい順に並べたものに、例えば「1番1番3番」だったら、最初の1番には0を加え1番とし、次の1番には1を加えて2番とし、次の3番には2を加えて5番とし、「1番1番3番」を「1番2番5番」という組み合わせに変換します。こうすると変換された組み合わせには同じ番号は出てきません。そして、1番からn+r-1番までが使われることになります。そして、変換前の組み合わせが違えば変換後の組み合わせも違います。また、1番からn+r-1番までの番号が書いてある球がそれぞれ1個ずつある中からr個取り出す場合に現れる組み合わせはすべて変換後の組み合わせとして出てきます（逆の操作をすればその組み合わせが変換前に存在するのは明らか）。つまり、1番からn番までから重複を許してr個選ぶ選び方と、1番からn+r-1番までからr個選ぶ選び方は1対1対応させることが出来るので、場合の数は同じになります。
その他の回答 (2)
- kamiyasiro
- ベストアンサー率54% (222/411)
#2です． 円順列と混同するような書き方になっていました． みかんとかきの仕切りは時計の１２時の位置に動かず固定されているとして下さい． というか，別の説明なんで，無視して下さっても結構です．
お礼
２度の回答ありがとうございました。 参考になりました！
- kamiyasiro
- ベストアンサー率54% (222/411)
重複組み合わせの解説ですが， ご質問にあった解説とは別に，次のような解説もできますので，ご参考まで． みかん，りんご，かき がそれぞれ多数ある．（n＝3） １０個の果物の詰め合わせを作りたい．（r＝10） 何通りの組み合わせ方があるか． これは重複組み合わせの問題ですが， 単純に，円状に並んだ１０個の果物置き場に， 厚紙で種類を分ける仕切りを作る問題と置き換えても等価です． ・仕切りを置ける箇所は１０箇所． ・仕切りは２枚（n－1）． ・２枚を同じ箇所に置いても良い． （この条件は非常に難しいのだが，何も置かない箇所を１つづつ選択する組み合わせと等価！） ・果物を取り除いてしまえば，仕切りを置く候補は１０＋（３－１）となる． ・つまり，r＋（n－1）箇所から仕切りを置かないr箇所を選ぶ組み合わせとなる．
お礼
回答ありがとうございました。
お礼
回答ありがとうございました。 とってもわかりやすい説明でした！