# Bins and balls model - filling first bins

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.

• An obvious problem is that the final formula depends on parameter $p$, which is not given (fixed). – 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.
$$\sum_{p=q}^m {k \choose q} {m \choose p} q! {p \brace q} (n-k)^{m-p}$$
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)}$$