We have $n$ bins and $m$ balls. I want to compute the probability that in the first $k$ bins, $q$ of them will be non-empty.

I can throw $m$ balls into $n$ bins in $n^m$ ways.

Using Stirling numbers of second type I know, that I can divide $m$ balls into $x$ non empty subsets in ${m \brace x}$.

Now I want to have during first $k$ bins exactly $q$ non empty, and the rest balls should be in the next $n-k$ bins.

So I made the evaluation that this is:

  1. from $m$ balls I pick $p$, which will 'hit' into first $k$ bins: ${m \choose p}$
  2. from first $k$ bins I select $q$ bins which should be non-empty: ${k \choose q}$
  3. balls from 1. point I have to divide into $q$ non-empty subsets using Stirling numbers of second type: ${{m \choose p}\brace q}$
  4. I have to permute the subsets from 3. point

So the final result which I have is $$Pr = \sum_{p=q}^m\frac{{k \choose q}\cdot {{m \choose p}\brace q}\cdot q!}{n^m}$$

Is reasoning this correct? If anyone will notice any mistake, I will be grateful for any suggestion how can I correct it.

  • $\begingroup$ An obvious problem is that the final formula depends on parameter $p$, which is not given (fixed). $\endgroup$ – leonbloy Dec 18 '13 at 2:36

First: you need to sum over all the possible values of $p$. Second: In the Stirling number, you must use the number of available balls, which is $p$, not ${m \choose p} $ (the later is the number of ways of choosing them). Third: You must also count what you do with the remaining balls $m-p$ balls, that go into the remaining $n-k$ urns.

Then the total count is given by

$$ \sum_{p=q}^m {k \choose q} {m \choose p} q! {p \brace q} (n-k)^{m-p} $$

Quite ugly, I don't know if it can be simplified.

A quick Poissonization gives the asymptotic approximation, with $\lambda=m/n$:

$$P\approx {k \choose q} \left(1- e^{-\lambda}\right)^q e^{-\lambda(k-q)}$$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.