Invisible wrote:

> N is trivially the lower bound.
> 
> Each ball appears with probability 1/N, so the probability for all balls 
> to appear (given that these events are clearly independent) in N trials 
> would be (1/N)^N, which is 1/(N^N).
> 
> Hmm, but wait! This does not count for ordering. There are N! 
> permutations of N events, so taking *that* into account, we now actually 
> have N! / N^N.
> 
> Now, if we perform K trails...

Let's try that again...

If we select one ball, the probability of it being ball #1 is 1/N.

If we select K balls, the probability of ball #1 appearing becomes 1/N + 
1/N + 1/N + 1/N + ... K times over, minus the probability of ball #1 
appearing more than once.

In other words, we have K/N - E, and I can't figure out how to compute E.

(Presumably combinatorics provides a trivial way to solve this. Too bad 
I don't know combinatorics, eh?)

Post a reply to this message