Ball & Bins

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 = 85 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 =

nk

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

4 thoughts on “Ball & Bins

  1. “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?

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s