Probability: r balls in n urns

Question

I am trying to solve this complicated problem:

r balls are randomly assigned into n urns. The assignment is random and the balls are cannot be distinguished. What is the probability that exactly m urns will contain exactly k balls each ?

I don't even know how to start, apart from saying that each ball has a probability of 1/n to be in each urn. It sounds like a very complicated problem. Can anyone assist please ? Thank you.

Following the hints below, this is what I came up with, it looks too simple and incorrect, where is my mistake?

$\frac{\binom{n}{m}\binom{r-km+n-m-1}{r-km}}{\binom{r+n-1}{r}}$

Answer 1

The problem statement is somewhat unclear. “$r$ balls are randomly assigned into $n$ urns” sounds as if each ball is independently uniformly randomly assigned to an urn – but then it’s not clear why you’d write “the balls cannot be distinguished”. So I’ll assume that you intended for each distinguishable assignment of indistinguishable balls to be equiprobable. If in fact you intended for the balls to be independently uniformly randomly assigned to the urns, you can readily apply the same principle.

According to a Generalised inclusion-exclusion principle, if $\ell$ particular conditions out of $n$ can be fulfilled in $b_\ell$ ways, there are

$$ \sum_{\ell=m}^n(-1)^{\ell-m}\binom \ell m\binom n\ell b_\ell $$

ways to fulfill exactly $m$ of the conditions. In the present case, there are

$$ b_\ell=\binom{r-\ell k+n-\ell-1}{n-\ell-1} $$

ways to have exactly $k$ balls in $\ell$ particular urns, so there are

$$ \sum_{\ell=m}^n(-1)^{\ell-m}\binom \ell m\binom n\ell\binom{r-\ell k+n-\ell-1}{n-\ell-1} $$

ways to have exactly $k$ balls in exactly $m$ urns.

Answer 2

We need to state clearly the terms of the problem to avoid misunderstandings.
So, it looks that the interpretation of the problem should be:
- we have $r$ undistinguishable balls and $n$ distinguishable (i.e. labeled) bins;
- the bins have unlimited capacity , so each can be filled with $0$ to $n$ balls;
- the balls are laid (not launched) into the bins; that means that we are parting the balls into the bins in a Stars&Bars or better weak Compositions of $r$ into $n$ parts; the total number of ways of doing that is $$T(r,n)=\binom{r+n-1}{r}$$
- it is asked to find the number of compositions in which there are exactly $m$ boxes filled with exactly $k$ balls, while the remaining boxes might be empty or filled with a number of balls which is lower or greater than $k$.

If this is the correct understanding, then consider the following scheme

which is much of help to "keep under sight" what is the path to follow.

We take one of the possible occupancy histogram and re-arrange it into the three blocks as shown,
just translating each bar to the pertinent block without altering the sequence within the block.
It is important to note that each histogram on the right will correspond to a number of histograms on the left which equals the combinations of a collection of three different items, i.e. $$ H = \left( \matrix{ n \cr b,\;m,\;n - m - b \cr} \right) = \left( \matrix{ n \cr m \cr} \right)\left( \matrix{ n - m \cr b \cr} \right) $$ The shuffling within each block will be accounted in the computation of the relevant number of ways. These are

a) for the block with exactly $k$ balls in each bin there is of course only $1$ way

b) for the block with max $k-1$ balls the number of different ways to compose it is given by $$ N_b (j,k - 1,b) = \sum\limits_{\left( {0\, \le } \right)\,\,l\,\,\left( { \le \,{j \over k}\, \le \,b} \right)} {\left( { - 1} \right)^l \binom{ b }{l} \binom{ j + b - 1 - l\,k }{ j - l\,k } } $$ as explained in this related post

c) for the block with more than $k$ balls, only $r - j - mk -(n-m-b)(k+1)= r-j+m-(n-b)(k+1)$ are free to be differently allocated, so that corresponds to the weak compositions $$ N_c = \binom{ r - j - 1 - \left( {n - b} \right)k }{ r - j + m - \left( {n - b} \right)\left( {k + 1} \right) } $$

Putting all together we get $$ \eqalign{ & N = \sum\limits_{j,b} {H \cdot 1 \cdot N_b \cdot N_c } = \cr & = \left( \matrix{ n \cr m \cr} \right)\sum\limits_{j,b} {\left( \matrix{ n - m \cr b \cr} \right)\left( \matrix{ r - j - 1 - \left( {n - b} \right)k \cr r - j + m - \left( {n - b} \right)\left( {k + 1} \right) \cr} \right) \sum\limits_l {\left( { - 1} \right)^l \left( \matrix{ b \hfill \cr l \hfill \cr} \right) \left( \matrix{ j + b - 1 - l\,k \cr j - l\,k \cr} \right)} } = \cr & = \left( \matrix{ n \cr m \cr} \right)\sum\limits_{l,b} {\left( \matrix{ n - m \cr b \cr} \right)\left( { - 1} \right)^l \left( \matrix{ b \cr l \cr} \right) \sum\limits_j {\left( \matrix{ r - j - 1 - \left( {n - b} \right)k \cr r - j + m - \left( {n - b} \right)\left( {k + 1} \right) \cr} \right)} \left( \matrix{ j + b - 1 - l\,k \cr j - l\,k \cr} \right)} = \cr & = \left( \matrix{ n \cr m \cr} \right)\sum\limits_{l,b} {\left( { - 1} \right)^l \left( \matrix{ n - m \cr b \cr} \right) \left( \matrix{ b \cr l \cr} \right)\left( \matrix{ r\; + b - 1 - \left( {n - b + l} \right)k \cr r + b + m - n - \left( {n - b + l} \right)k \cr} \right)} \cr} $$ where to the inner sum we have applied the "double convolution" identity.

Continuing in the simplification, putting $$ j = n - b + l\quad \Rightarrow \quad b = n - j + l $$ we can rewrite the sums as $$ \eqalign{ & \sum\limits_{l,\,j} {\left( { - 1} \right)^l \left( \matrix{ n - m \cr n - j + l \cr} \right) \left( \matrix{ n - j + l \cr l \cr} \right)\left( \matrix{ r\; + n - j + l - 1 - jk \cr r + n - j + l + m - n - jk \cr} \right)} = \cr & = \sum\limits_{l,\,j} {\left( { - 1} \right)^l \left( \matrix{ n - m \cr l \cr} \right) \left( \matrix{ n - m - l \cr n - j \cr} \right)\left( \matrix{ r\; + n - j + l - 1 - jk \cr r + n - j + l + m - n - jk \cr} \right)} = \cr & = \sum\limits_{l,\,j} {\left( { - 1} \right)^l \left( \matrix{ n - m \cr n - m - l \cr} \right) \left( \matrix{ n - m - l \cr n - j \cr} \right)\left( \matrix{ r\; + n - j + l - 1 - jk \cr r + m - j + l - jk \cr} \right)} = \cr & = \sum\limits_{l,\,j} {\left( { - 1} \right)^l \left( \matrix{ n - m \cr n - j \cr} \right) \left( \matrix{ - m + j \cr - m - l + j \cr} \right)\left( \matrix{ r\; + n - j + l - 1 - jk \cr r + m - j + l - jk \cr} \right)} = \cr & = \sum\limits_{l,\,j} {\left( { - 1} \right)^{m - j} \left( \matrix{ n - m \cr n - j \cr} \right) \left( \matrix{ - l - 1 \cr - m - l + j \cr} \right)\left( \matrix{ r\; + n - j + l - 1 - jk \cr r + m - j + l - jk \cr} \right)} = \cr & = \sum\limits_j {\left( { - 1} \right)^{m - j} \left( \matrix{ n - m \cr n - j \cr} \right)\left( \matrix{ r\; + n - j - 1 - jk \cr r - jk \cr} \right)} \cr} $$ by applying the "trinomial revision" and "double convolution" identities.

Finally we can conclude that $$ \bbox[lightyellow] { N = \left( \matrix{ n \cr m \cr} \right)\sum\limits_j {\left( { - 1} \right)^{m - j} \binom{ n - m }{ n - j } \binom{ r\; + n - j - 1 - jk }{ r - jk } } }$$ which is the same formula as the one already given by Joriky.