Simple Counting Problem Solution!

in #mathematics7 years ago

Yesterday I posed the following question:

How many ways can you place 20 identical balls into 4 unique bins?


The answer is actually pretty cool and easy if you think about it in a certain light.
Let '0' represent a ball and '1' represent a barrier between 4 bins. (Therefore there are 3 barriers):

00100010000000001000000

This is just one possible way to place 20 balls in 4 bins, but it turns out that the exact number of ways is just the number of bitstrings of length 23 which contain 3 ones!
We "choose" three of the 23 bits to be barriers and the rest to be balls.

This is C(23,3) = 23!/(20!3!) = 23*22*21/6 = 1171


In my opinion, this is the most interesting of the basic counting arguments in combinatorics!