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.

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!.

Is this the correct way to think about this problem?

share|improve this question
1  
$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
add comment

2 Answers

up vote 3 down vote accepted

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\,!}$$

share|improve this answer
add comment

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.

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.