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 =
*Please keep in mind – it is very important that the balls & bins are distinct. If not, this would be a whole different problem.