Stars and Bars Theorem

Stars and Bars Theorem

Consider the equation  where  are non-negative integers. We're looking for the number of solutions this equation has.

How to solve this? 😟

Suppose we have  places, where we put  stars and  bars, one item per place. The key idea is that this configuration stands for a solution to our equation. For example,  stands for the solution . Because we have  star, then a bar (standing for a plus sign), then  stars, again a bar, and similarly  and  stars follow. Similarly,  denotes the solution  because we have no star at first, then a bar, and similar reasoning like the previous.

We see that any such configuration stands for a solution to the equation, and any solution to the equation can be converted to such a stars-bars series.

So our problem reduces to "in how many ways can we place  stars and  bars in  places?" 

This is the same as fixing  places out of  places and filling the rest with stars. We can do this in, of course,  ways. So the number of solutions to our equation is

The number of ways to place  indistinguishable balls into  labelled urns is

This is our solution of the above type of equation.😃