Stars and columns
Stars and Bars is a classic combinatorial method that allows you to count the number of ways to distribute identical objects among distinct containers.
The idea is very simple:
* represent objects,| separate containers.Given:
In how many ways can these objects be distributed among containers?
We can represent a distribution as a sequence of:
*,|For example, distribute objects among containers:
The number of ways to do this is .
In the more general case:
Given the equation
where , count the number of its solutions.
Note that a solution can be depicted using stars and bars. For example, the solution
for , can be represented using
It is easy to see that this is exactly the stars and bars theorem. Therefore, the solution is .
Given the equation
where , count the number of its solutions.
Note that this version of the problem is more restrictive: the numbers are strictly positive, meaning that this time we cannot place two bars in a row, because that would mean (an empty box).
There are gaps between the stars to place bars, so the solution is
(the second part of the theorem).
****||
***|*|
*|**|*
.
.
.