Counting pairs is the oldest trick in combinatorics… Everytime we count pairs, we learn something from it. — Gil Kalai
Most of the combinatorical problems have something with number of ways. In this articles I’m going to explain a combinatorical theorem — I guess so — in the way of solving the “number of ways” problems.
Stars and Bars
Before we get into the theorem let’s see the logic that’s lead us into the theorem.
Let’s say we have 10 identical cubics that we’re going to fill in 3 buckets, in how many ways?
Okay, let’s get started. First let’s form a line with that cubics.
Now we can add 2 lines that will represents the number of cubics in bucket number 1 and so on. Let’s see.
We can see that bucket 1 fill with 3 cubics, same with buckets 3, and bucket 2 fill with 4 cubics. Now this is one of many ways, we can find other ways with this logic, which is how many ways to put the line in that form of line of cubics. Which in combinatorics we write as:
So we can see that it’s actually equal to:
Where n is the cubic in our case and k is the bucket in our case also. Now the questions how and when can we use the stars and bars? You can find out by solving this problem:
Thank you for reading! If you have any suggestion, you can write it down.
