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.
$\endgroup$2 Answers
$\begingroup$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.
$\endgroup$ 5 $\begingroup$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.
$\endgroup$
