Assume that we have $n$ balls and $k$ bins. The $n$ balls are are divided into $M$ sets, $\left\{ {{m_i}} \right\}_{i = 1}^M$, where $\sum\limits_{i = 1}^M {\left| {{m_i}} \right|} = n$, $|m_i| \le k$.

For the balls in a given set $m_i$, the first ball can be placed in $|m_i|$ (randomly chosen from $k$) bins, the second one in $(|m_i|-1)$ bins and so on. In addition, each ball in the set $m_i$ must be placed in a different bin, that is, for each $m_i$, $|m_i|$ balls are placed in $|m_i|$ distinct bins.

My question is, what is the probability that $j$ ($j=1,2,...,k$) bins are non-empty?

Another version (maybe a simpler one):

Assume that there are $n$ balls, and they are thrown into $k$ bins, $s$ balls in a time ($s|n$), where each ball from the $s$ balls is known to fall into a different bin.

What is the probability that $j$ ($j=1,2,...,k$) bins are non-empty after all balls have been thrown?

  • $\begingroup$ I thought that for each set $m_i$ the problem can be divided into $|m_i|$ sub-problems, with each having one ball and $k,k-1,...,k-|m_i|+1$ bins. However, I don't see how to combine the probabilities of these sub-problems. $\endgroup$ – MJK Jul 31 '13 at 13:37

Your Answer

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

Browse other questions tagged or ask your own question.