13
$\begingroup$

So the question is how many ways are there to put N unlabelled balls in M labeled buckets.

One way (I think) I figured it out is $M^N$ ways to put each ball, divided by $N!$ permutations of ball ordering we don't care about:

$M^N \over N!$

First, is this correct?

Second, is there another way to approach it without using division? I need to calculate it in a non-prime modulo space so division isn't available. I really need a recurrence.

2 Answers 2

17

No, that expression isn’t correct. The correct expression is

$\binom{N+M-1}{M-1}=\binom{N+M-1}N=\frac{(N+M-1)!}{N!(M-1)!}\;;$

this formula is derived here. As André notes in the comments, this can be calculated without division, by using the identity

$\binom{n}m=\binom{n-1}m+\binom{n-1}{m-1}$

with the initial conditions $\binom{n}0=1$ for all integers $n\ge 0$ and $\binom0m=0$ for all integers $m>0$.

Added: To see why your reasoning doesn’t work, consider the case of $3$ balls and $2$ buckets, labelled $A$ and $B$. Suppose that we put the balls into the buckets one at a time; then the $2^3=8$ possibilities are $AAA,AAB,ABA,ABB,BAA,BAB,BBA$, and $BBB$. One of these puts $3$ balls in $A$ and none in $B$; $3$ of them put $2$ balls in $A$ and $1$ in $B$; $3$ of them put $1$ in $A$ and $2$ in $B$; and $1$ of them puts all $3$ balls in $B$. In other words, the number of permutations corresponding to each distribution of the unlabelled balls is not constant: it depends on the distribution. Here the count of $2^3$ sequences counts two of the possible distributions correctly, but it overcounts the other two by a factor of $3$. And this variation only gets worse as the numbers of balls and buckets go up.

  • 0
    @user1131467: Because so$m$e permutations change the distribution and some do not. **How many** change the distribution depends on the number of balls in each bucket, which is highly variable.2012-09-08
2

The Stars and Bars approach given in the answer by Brian M. Scott can be carried out without division. For example, Pascal's Identity $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ can be used as a recurrence to calculate the required binomial coefficient. For large numbers, the procedure is unfortunately quite inefficient: simple operations, but too many of them.

There is a substantial literature about methods for computing binomial coefficients. For example, Granville gives a sophisticated method or computing binomial coefficents modulo a prime power.