おまけが揃う確率 - イガブロギュ

ひょんなことから、次のような問題を考えました。
「n種類あるおまけのうち1つだけが等確率で入っているお菓子がある。お菓子をr個買って初めてn種類のおまけが全て揃う確率はいくつか。」
r=n、つまりn回目だったら簡単です。
$\frac{n!}{n^n}$
です。
また、rが大きくなればなるほど、確率が上がっていくことは明らかです。
さて、問題を解くために漸化式を立てることもできるのですが、自分でやってみたらとても扱いにくい式になってしまったので、路線を変更しました。
r回目で初めて全てが揃う確率は、r-1回目までにn-1種類が揃っていて、r回目に残りの1種類が当たる確率です。
また、r-1回目までにn-1種類が揃っている場合の数は、n-1種類のおまけを重複を許してr-1個並べたときにn-1種類全てが含まれている場合の数と同じです。
これは、n-1種類のおまけのそれぞれが少なくとも一つのiについてi回目の購入に対応している状況ですので、r-1個の異なるボールをn-1個の異なる箱にそれぞれ最低1個はボールが入るように分けた状況と同じです。
ということは、「n個のボールをr個の箱に分ける場合の数」に書いた結果が使えるではありませんか！
やったね。
というわけで、r-1回目までにn-1個が揃う場合の数は
$\sum_{i=1}^{n-1}(-1)^{n-1-i}{}_{n-1}C_ii^{r-1}$
となるので、求める確率は、r回目に当たるおまけの選び方がn通りあって、r回目にそれらを当てる確率が1/nであることから
$n \times \frac{1}{n} \times \frac{1}{n^{r-1}}\sum_{i=1}^{n-1}(-1)^{n-1-i}{}_{n-1}C_ii^{r-1}$
$=\frac{1}{n^{r-1}}\sum_{i=1}^{n-1}(-1)^{n-1-i}{}_{n-1}C_ii^{r-1}$
となります。
いやはや、問題自体は単純なのに、まさか第二種スターリング数まで絡んでくるとは思いませんでした。
ちなみに、確率ではなくn種類が集まるまでの購入回数の期待値を求める問題は「クーポンコレクターの問題」と呼ばれ、割と有名な話のようです。