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:
- from $m$ balls I pick $p$, which will 'hit' into first $k$ bins: ${m \choose p}$
- from first $k$ bins I select $q$ bins which should be non-empty: ${k \choose q}$
- balls from 1. point I have to divide into $q$ non-empty subsets using Stirling numbers of second type: ${{m \choose p}\brace q}$
- 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.
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)}$$