すべてのキャラクターを揃える

友人が、クイズを持ちこんできた。
k種類のおまけがあって、それは、すべての割合であたるが、どれがあたるか分からないという。
いったい、何回おまけをもらうと、k種類の全制覇ができるか、全制覇する確率が５０％を越えるのはいつごろか、というものだった。

今、k種類のおまけがある。
それぞれのおまけを選ぶ確率p=1/k

今、n回の応募を終えた時点で、手元にあるおまけの種類数を　a 種類　(1<=a<=min(n,k))とします。

今、このときの確率を　Pn(a)とすると

Pn(1)+Pn(2)+...+Pn(min(n,k))=1
なる関係にあります。

Pn+1(a)=Pn(a) x a/k + Pn(a-1) x (k-a+1)/k

という漸化式が正しいです。

１世代前にa種類もっていたら、そのa種類のどれかをもらうしかない。
１世代前にa-1種類もっていたら、そのa-1以外の種類(k-a+1)のどれかをもらうしかない。

この漸化式の初期値は
P1(1)=1,P1(0)=0 (P1(0)が定義されていないと計算ができないので。Pk(0)=0も同様に、与えるものとします)によって定義されます。

エクセルで、作ってみたら、ある程度のところで、計算誤差が出てしまった。

java でソースを書いて、計算させてみた。

４６種類のときは、それほど大変じゃなく、１９３回で可能だった。
１０種類なら２７回も応募すればよいらしいです。