Probability of Collection

1. Let P(k) be the probability of collecting all N types of items after drawing k times.
Then, P(k < N) = 0.

When k = N,
P(N) = (N/N)*[(N - 1)/N]*[(N - 2)/N]*...*(1/N)
____= N!/(N^N)

When k > N, consider k = N + 1,
(the extra draw can happen after every new draw except for the last one)
So, P(N + 1) = (N/N)*(1/N)*[(N - 1)/N]*[(N - 2)/N]*...*(1/N) +
___________ (N/N)*[(N - 1)/N]*(2/N)*[(N - 2)/N]*...*(1/N) +
___________ (N/N)*[(N - 1)/N]*[(N - 2)/N]*(3/N)*...*(1/N) +
___________ ... + (N/N)*[(N - 1)/N]*...*(2/N)*[(N - 1)/N]*(1/N)
__________= [N!/(N^(N + 1)]*[1 + 2 + ... + (N - 1)]
__________= [N!/(N^(N + 1)]*[N(N - 1)/2] (By sum of finite series)

By the concept used in case k = N + 1, I can get :

P(N + 2) = [N!/(N^(N + 2)]*sum(x = 1 -> N - 1)[x(N - 1 + x)(N - x)/2]

P(N + 3) = [N!/(N^(N + 3)]*{[sum(x2 = 1 -> N - 1) x2]
_______________________sum(x1 = x2 -> N - 1)[x1(N - 1 + x1)(N - x1)/2]}
(Double summation)

Then, by similar guessing,

P(N + i) = [N!/(N^(N + i)]*{[sum(x(i-1) = 1 -> N - 1) x(i-1)]
________[sum(x(i-2) = x(i-1) -> N - 1) x(i-2)] ...
________ sum(x1 = x2 -> N - 1)[x1(N - 1 + x1)(N - x1)/2]}
(Multiple summation)


2. The expected times needed to draw to collect all N types of items

= N*N!/(N^N) + sum(i = 1 -> oo) (N + i) P(N + i) for i = 1, 2, ...


Hope you can understand my denotation.

2009-03-21 13:14:54 補充：
It seems to me that you are right.
However, its meaning seems so strange that
we have to add in the case of an extra draw after obtaining the N th item!

2009-03-21 13:24:08 補充：
Correction :
P(N+1) = [N!/(N^(N + 1)]*[N(N + 1)/2]
P(N + 2) = [N!/(N^(N + 2)]*sum(x = 1 -> N)[x(N + x)(N + 1 - x)/2]
P(N + 3) = [N!/(N^(N + 3)]*{[sum(x2 = 1 -> N) x2]
_______________________sum(x1 = x2 -> N)[x1(N + x1)(N + 1 - x1)/2]}
(Double summation)

2009-03-21 13:26:54 補充：
P(N + i) = [N!/(N^(N + i)]*{[sum(x(i-1) = 1 -> N) x(i-1)]
________[sum(x(i-2) = x(i-1) -> N) x(i-2)] ...
________ sum(x1 = x2 -> N)[x1(N + x1)(N + 1 - x1)/2]}
(Multiple summation)

The answer for Q#2 remains the same. Thank you.

我終於想到第1題的答案是甚麼。

答案就是N!S(k,N)/N^k，S(k,N)就是Stirling numbers of the second kind（http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind）。