# combinations, how many ways are there?

how many ways are there to put 36 non-distinguishable balls in 15 distinguishable buckets? This is what I thought: suppose the balls are distinguishable. every time you want to put a ball in a bucket, you have 15 possibilities. so if you have to do this 36 times, you have 15^36 ways to do this. Suppose then that the balls are non-distinguishable, then you have 15^36/15!.

-
$15^{36}/15!$ does not look like integer ... – Santosh Linkha Jan 9 '13 at 19:29
@ThomasAndrews sorry I edited my comment, could you add it as an answer? – Santosh Linkha Jan 9 '13 at 19:36

This is a version of the stars-and-bars problem in combinatorics.

For any pair of natural numbers $n$ and $k$, the number of distinct $n$-tuples ($15$ buckets for balls) of non-negative integers whose sum is $k$ ($36$ total balls) is given by the binomial coefficient:

$$\binom{n + k - 1}{k} = \binom{n+k-1}{n-1}.$$
So the number of ways to put $36$ balls in $15$ distinct buckets is given by:

$$\displaystyle \binom{15+36 - 1}{36} =\binom{15 + 36 - 1}{15-1} = \frac{50\,!}{14\,!\;36\,!}$$

-

As commenter ExperimentX notes above, your number is not an integer. You can see this because $15^{36}$ is odd while $15!$ is even.

This is a stars-and-bars problem.

Let $x_i$ be the number of balls that end up in bucket $i$, $i=1,...,15$. Then you have $0\leq x_i$ for all $i$ and $x_1+x_2+...x_{15}=36$.

Using the formula from the Wikipedia article, we get:

$$\binom{36+15-1}{15-1}$$

Note that the process does not make all of these results equally likely, if you were counting probabilities, but this count gives you the number of distinct results.

-