重複組合わせ

重複組合わせ

ある本に次のような説明がありました。

一つの箱のなかに１からnまでの番号のついた球が入っているとする。この中から球を順にr個取り出すという場合。
取り出した番号は無視してそれらの番号の組を作る。
この場合、n＋r－１個からr個取り出す組合せに直す事ができる。
まず、取り出したr個のものa1,a2,…,arに対して、順序を区別しないのであるから、考えやすくするために、n個のものに対応する番号をつけ、取り出したa1,a2,…,arの番号は、a1≦a2≦…≦arであると仮定しても問題無い。そうすると、ここに、順に０，１，２、…、r－１を加え、
a1+0=b1
a2+1=b2
…
ar+(r-1)=br
を考えれば、b1<b2<…<brであって、しかも、b1,b2,…,brは１，２，３、…、n＋r－１のうちのいずれかである。このb1,b2,…,brの取り方は、取り出した順番に関係なく番号が大きい順に並べ直したものだから、n＋r－１個からr個取り出す組合せになる。
つまり、nこからr個重複して取り出す組み合わせを、n＋r－１こからr個取り出す組合せになおすことができた。


・・・という説明があるのですが、イマイチよくわかりません゜(゜´Д｀゜)゜
どなたかもう少し噛み砕いてわかりやすく説明してくださいませんか？？

回答よろしくお願いします。

No.1 ベストアンサー 回答者： Quattro99 回答日時： 2010/10/31 00:46

少し端折ってないですか？

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対応させることが出来るので、場合の数は同じになります。

この回答へのお礼

回答ありがとうございました。

とってもわかりやすい説明でした！

お礼日時：2010/11/03 11:12

No.3 回答者： kamiyasiro 回答日時： 2010/10/31 16:54

#2です．

円順列と混同するような書き方になっていました．

みかんとかきの仕切りは時計の１２時の位置に動かず固定されているとして下さい．

というか，別の説明なんで，無視して下さっても結構です．

この回答へのお礼

２度の回答ありがとうございました。

参考になりました！

お礼日時：2010/11/03 11:13

No.2 回答者： kamiyasiro 回答日時： 2010/10/31 16:13

重複組み合わせの解説ですが，

ご質問にあった解説とは別に，次のような解説もできますので，ご参考まで．

みかん，りんご，かき　がそれぞれ多数ある．（n＝3）
１０個の果物の詰め合わせを作りたい．（r＝10）
何通りの組み合わせ方があるか．

これは重複組み合わせの問題ですが，
単純に，円状に並んだ１０個の果物置き場に，
厚紙で種類を分ける仕切りを作る問題と置き換えても等価です．
・仕切りを置ける箇所は１０箇所．
・仕切りは２枚（n－1）．
・２枚を同じ箇所に置いても良い．
（この条件は非常に難しいのだが，何も置かない箇所を１つづつ選択する組み合わせと等価！）

・果物を取り除いてしまえば，仕切りを置く候補は１０＋（３－１）となる．
・つまり，r＋（n－1）箇所から仕切りを置かないr箇所を選ぶ組み合わせとなる．

この回答へのお礼

回答ありがとうございました。

お礼日時：2010/11/03 11:12