🚀 go-pugleaf

Peter Pui Tak Chiu <ppc1@cec2.wustl.edu> writes:
>Assume there are m kinds of balls in an infinitely large pool (i.e.
>there are infinitely many balls) and the distributions of different
>kinds of balls are equal.  Find the probability of getting all kinds of
>balls if n balls are picked.

>Therefore, the probability is:    (n-1)C(m-1)
>				---------------
>                                 (n+m-1)C(m-1)

Nope.  Suppose N = M.  Obviously the chance of getting one ball of each
color is M!/(M^M).  Your formula reduces to M!(M-1)!/(2M-1)!, which is
obviously not the same thing.

Your result is wrong because the arrangements are not equally likely.
The chance of getting M red balls is 1/(M^M), but the chance of getting
one ball of each color is M!/(M^M).  You have given each of these the
same weight.

Here is a correct approach based on inclusion-exclusion.  Let P(K) be
the probability that all of the balls are selected from a particular set
of K colors, with every color occurring at least once.  Thus P(M) is the
quantity we want.  Let Q(L) be the probability that all of the balls are
selected from a particular set of L colors, but not necessarily with
every color occurring.  Clearly Q(L) = (L/M)^N.

Now, of course,

   Q(L) = \sum_{K=0}^L B(L,K) P(K),

where B(L,K) is the binomial coefficient L-choose-K.  This just says
that if all of the balls are from a set of L colors, then the set of
colors which actually occur must be some K-set contained within the
L-set.  The number of such K-sets is B(L,K), for each K.

The inclusion-exclusion formula expresses P in terms of Q:

   P(K) = \sum_{L=0}^K (-1)^(K-L) B(K,L) Q(L).

It is a direct consequence of the previous formula.  If it's not
familiar to you, you can look it up in any standard combinatorics text,
or just derive it for yourself.  

Thus,

   P(M) = \sum_{L=0}^M (-1)^(M-L) B(M,L) (L/M)^N.

                                        David desJardins