この問題は東工大２年、川喜田さんが投稿してくださった問題です。
本当は全て揃うまでの個数の期待値の問題なのですが、
難問なのでここでは確率のみにしぼって扱います。
最後の「種類数が未定である」のが曲者ですね（笑）
これは部屋分け問題で行った、
「９人を２つ（３つ）のグループに分ける方法」と同じ考え方がベストだと思いました。
まず、２種類だとどうなるでしょうか。
おまけがＡ、Ｂだとします。
最後にＢが出るとして、最後に２倍しても矛盾は生じません。
ｎ−１回Ａが出つづけ、最後にＢが出る確率は、
（１／２）n-1×１／２
よって、最後に当たるのがＡである場合も同様に確からしいので、
（１／２）n-1×（１／２）×２
＝（１／２）n-1となります。
次に、３種類の場合はどうなるでしょうか？
おまけがＡＢＣであるとします。
これも最後に当たるのがＣであるとします。
直前のｎ−１回まではＡＢのみが出つづける場合の数は、
１回１回について２通りずつ有り得るので２n-1とおりですが、
Ａ（またはＢ）のみが出つづける場合も含んでいるので、（これではｎ回目でそろえることが不可能ですから）
２n-1−２通りとなり、その確率は、
（２n-1−２）／３n-1
最後にＣが当たる確率１／３をかければ良いのですが、２種類のときと同様、この後３をかけるので、
相殺されて上の確率がそのまま答となります。
４種類にも挑戦してみましょう。
おまけがＡＢＣＤであるとし、最後にＤが出るとして後に４倍して構いません。
ｎ−１回目（ｎ≧４）までに、ＡＢＣの全種類が揃う確率を考えます。
３種類を無作為に取った場合の数は３n-1通りあり、
部屋分け問題の時のように、引いていきます。すると、
３n-1−3Ｃ2（２n-1−２）−3Ｃ1
＝３n-1−３×２n-1＋３通りですね。
５種類とした場合
同様に考え、さらに一般性も意識します。部屋は「空き部屋の選び方」に直しておきます。
4Ｃ0４n-1−4Ｃ1（３n-1−３×２n-1＋３）−4Ｃ2（２n-1−２）−4Ｃ3
＝１×４n-1−４×３n-1＋６×２n-1−４
一般に，ｍ＋１種類のおまけがｎ回目で揃う確率は，
最後に０×m-1Ｃm-1が隠れていると考えれば、
となるようではありませんか？
それではこれを数学的帰納法で証明してみます。
ｍ＝２のときは、１／２n-1となり、正しいですね。
ｍのときまで正しいとして、ｍ＋１のときが正しいことを証明します。
