**Q: We have k distinct balls and n distinct bins. We want to distribute the balls among the bins. How many distributions are possible if there is no bound on the number of balls in each bin? Assume that all balls are distributed among the bins.**

A: Let’s first start with a “smaller” problem. Say we have 2 distinct balls and 3 distinct bins. How many ways can we distribute 2 balls into 3 bins? Here is how I think: How many choices doesball #1 have? 3 bins to choose from. How many choices does ball #2 have? 3 bins to choose from

So, there are 3 * 3 = 3² = 9 ways to place 2 balls into 3 bins

Now, what if we have 5 balls and 8 bins? Choices for ball #1? 8. Choices for ball #2? 8. Choices for ball #3? 8….. Etc!

So, 8 choices 8 * 8 choices * 8 choices ….. 5 times:

8*8*8*8*8 = 8^{5} ways! You can compute this out if you really want.

So, how many ways to place k balls in n bins?

n choices * n choices * n choices * …. * k times =

n^{k}

*Please keep in mind – it is very important that the balls & bins are distinct. If not, this would be a whole different problem.

### Like this:

Like Loading...

Thank you, now i understand it! 🙂

LikeLike

“distinct’ what does that mean exactly? can a get a brief understanding please thanks

LikeLike

“Distinct” means that ALL the balls are different: we can tell the balls apart, for instance they are colored or numbered. Same goes for the bins: they are labeled so we can tell them apart.

Now, why is it important for them to be distinct?

Let me explain this in a smaller example. Imagine we had 2 balls and 3 bins. Imagine if both the balls were black and not numbered. Consider:

Placing 1st ball in bin #2 and 2nd ball in bin #3

OR

Placing 1st ball in bin #3 and 2nd ball in bin #2.

If you cannot tell the balls apart, these two situations would really just be the same situation. As opposed to:

Placing a red ball in bin #2 and a yellow ball in bin #3

OR

Placing a red ball in bin #3 and a yellow ball in bin #2

This is clearly two different situations.

See what I mean now?

LikeLike

yes i do, thanks for the clarification 🙂

LikeLike