# Thread: Ball and Urn Model

1. ## Ball and Urn Model

I need to find the probability of calculating placing of r balls into n urns, such that there can be no empty urns.

I find the number of ways to do it is $\displaystyle {n-1}\choose{r-1}$.
But this is pretty useless. It does not give me the actual probability.

For example, for n=2, r=3.
We can list down all the cases:
ABC|x
x|ABC
AB|C
AC|B
CB|A
A|BC
B|AC
C|AB

The probability is 6/8.
The number of ways is 6.

Using the $\displaystyle {n-1}\choose{r-1}$ formula, I get:
$\displaystyle 1\choose2$, which is pretty much meaningless.

Can I use any mathematical models to get the number 6, instead of having to list all down?

Thanks!

2. If you have read my response to an earlier question, then you know that you are using a model in which objects-distinguishable, cells-distinguishable and cells may not be empty. Putting R distinguishable balls into N distinguishable urns without any urn being empty of course requires $\displaystyle R \ge N$. The number of ways to do that is simply the number of surjections (onto functions) from a set of R elements to a set of N elements. I will give you the counting formula for that: $\displaystyle Surj(R,N) = \sum\limits_{k = 0}^N {\left( { - 1} \right)^k { N \choose k } \left( {N - k} \right)^R }$.
To understand this idea, you may want to study Stirling numbers of the second kind.

3. Thanks! That was very helpful indeed, throwing me a lead on Stirling's Number.
The amount of knowledge to master for probability is really vast.