12
$\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

14

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
    Why isn't my expression correct?2012-09-08
  • 0
    @user1131467: Most obviously, because it isn’t always an integer. Take $3$ balls and $2$ buckets: your formula gives $\frac43$ ways to distribute the balls.2012-09-08
  • 0
    This proves it incorrect, however I still don't see what went wrong in my reasoning. The number of ways to put N labelled balls in M labelled buckets is $M^N$ correct? So why can't I just divide by the number of permutations of N balls to arrive at the unlabelled ball case?2012-09-08
  • 0
    I’ll add an explanation to my answer. Just give me a few minutes.2012-09-08
  • 0
    @user1131467: Because some 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.