Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
Why isn't my expression correct? –  Andrew Tomazos Sep 8 '12 at 6:48
    
@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. –  Brian M. Scott Sep 8 '12 at 6:57
    
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? –  Andrew Tomazos Sep 8 '12 at 7:05
    
I’ll add an explanation to my answer. Just give me a few minutes. –  Brian M. Scott Sep 8 '12 at 7:09
    
@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. –  André Nicolas Sep 8 '12 at 7:10
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.