Stars and Bars Theorem
Problem
Given K variables, $a_1, a_2, a_3 \dots a_K$ and a value $N$, how many ways can we write $a_1 + a_2 + a_3 \dots a_K = N$, where $a_1, a_2, a_3 \dots a_K$ are non-negative integers?
For example, if $K = 3$ and $N=2$, there are 6 solutions.
a b c ----- 2 0 0 0 2 0 0 0 2 1 1 0 1 0 1 0 1 1
Solution
The solution is very simple. In order to understand it, let us visualize the problem from a different angle.
Another way to represent the solutions visually is to use “Stars and Bars”. In the visualization below, we imagine we have $K$ partitions and we need to distribute $N$ stars in them. Like before, if we have $K = 3$ and $N=2$, then:
a b c -------- **| | |**| | |** * |* | * | |* |* |*
This visualization gives us the foundation of the solution. If we have $K$ partitions and $N$ stars to distribute in them, we can imagine that we have $N+K-1$ blanks. For example, when $K=3$ and $N=2$, we have $N+K-1=2+3-1=4$ blanks.
- - - - 4 Blanks
So, if we have $N+K-1$ blanks, how many of them will be stars? $N$ of the blanks need to be stars. And how many of the blanks need to be bars? Remember, if we have $K$ partition, then we just need $K-1$ bars to create $K$ partitions. So there will be $K-1$ bars.
So, the problem boils down to which blanks get to become stars and which blanks become bars. If we have $N+K-1$ blanks, how many ways are there to select $N$ of them to become stars? $\binom{N+K-1}{N}$ or $\binom{N+K-1}{K-1}$
For our example this equals to $\binom{4}{2} = 6$.
Stars and Bars Theorem
Theorem: For any pair of positive integers $N$ and $K$, the number of $K$-tuples of non-negative integers whose sum is $N$ is equal to the binomial coefficient $\binom{N+K-1}{N}$ or $\binom{N+K-1}{K-1}$.
Or we can rephrase “Stars and Bars Theorem” as “Ball and Urn Theorem”:
Theorem: If we have K distinguishable containers and N indistinguishable balls, then we can distribute them in $\binom{N+K-1}{N}$ ways.
The “Stars and Bars” theorem is also known as “Ball and Urn” theorem. Don’t get confused. They are the same thing.
Extensions
Positive Number of Stars in Each Partition
What if every partition needs to have at least one star? Simple. Place a star in each partition and subtract those placed stars from total stars. Then apply the Stars and Bars theorem normally.
For example, find the number of solution to $a + b + c = 10$, where $a,b,c > 0$.
Let $a = 1 + a’$, $b = 1 + b’$ and $c = 1 + c’$, where $a’,b’,c’ \geq 0$
$a+b+c = 10$
$(1+a’)+(1+b’)+(1+c’) = 10$
$a’+b’+c’ = 10 – 3$
$a’+b’+c’ = 7$, where $a’,b’,c’ \geq 0$
This can now be solved using normal “Stars and Barsh” theorem, which equals to $\binom{9}{2}$.
Theorem: For any pair of positive integers $N$ and $K$, the number of $K$-tuples of positive integers whose sum is $N$ is equal to the binomial coefficient $\binom{N-1}{K-1}$.
Lower Bound with Each Partition
The extension above can be further generalized. For each partition, if we are given a lower bound $x$, then we simply place $x$ stars in that partition and subtract with from total stars $K$. Finally, we apply “Stars and Bars” theorem normally.
So, for $a_1 + a_2 + a_3 \dots a_K = N$, where $a_1 \geq L_1, a_2 \geq L_2, a_3 \geq L_3 \dots a_K \geq L_n$ is same as $a’_1 + a’_2 + a’_3 \dots a’_K = N – L_1 – L_2 – L_3 \dots L_K$, where $a’_1, a’_2, a’_3 \dots a’_K \geq 0$.
Equation with Inequality
What if we are asked to find:
This is a very interesting extension. There are two ways to think about the solution to this problem.
Garbage Partition
Imagine that you have an extra partition which acts like a garbage bin. Then if you try to apply normal “Stars and Bars Theorem”, what happens?
So the equation now becomes: $a_1 + a_2 + a_3 \dots a_K + a_{K+1} = N$. What is the solution to this problem? Ans: $\binom{N+K}{K}$.
Now, simply imagine, anything that gets assigned to the extra garbage partition gets thrown out. So the sum of remaining partitions will be: $a_1 + a_2 + a_3 \dots a_K \leq N$
Theorem: For any pair of positive integers $N$ and $K$, the number of $K$-tuples of non-negative integers whose sum is less than or equal to $N$ is $\binom{N+K}{K}$.
Vertical Sum of Pascal Triangle
Another way to solve the problem is to simply loop over the solution from 0 to $N$.
$$a_1 + a_2 + a_3 \dots a_K = 0 \\
a_1 + a_2 + a_3 \dots a_K = 1 \\
a_1 + a_2 + a_3 \dots a_K = 2 \\
a_1 + a_2 + a_3 \dots a_K = 3 \\
\dots \\
a_1 + a_2 + a_3 \dots a_K = N \\
$$
If we find the sum of all the results above, then we will get result for $a_1 + a_2 + a_3 \dots a_K \leq N$. So what is the sum?
$$\binom{N+K-1}{K-1} + \binom{N+K-2}{K-1} + \binom{N+K-3}{K-1} \dots + \binom{K-1}{K-1}$$
Do you know what this is? This is the vertical sum of a column in pascal triangle. I will discuss the properties of Pascal Triangle someday else. For today, understanding the “Garbage Partition” logic will be enough.
So vertical sum of pascal triangle, or $\sum_{i=k}^{n}\binom{i}{k}$, is equal to $\binom{n+1}{k+1}$.
Upper Bound with Each Partition
Now, this is tricky. This time we are given the upper limit for each partition. So the number of stars we place must be smaller or equal to the upper limit for that partition.
One possible solution is Dynamic Programming. We iterate over each partition and keep track of remaining stars in our hand. When at each partition, we run a loop from 0 to upper limit and try placing the different amount of stars in each container.
It will be something similar to this ( not exactly this ):
int dp ( int partition, int stars ) {
int res = 0;
for ( int i = 0; i < upperLimit[pos]; i++ ) {
res += dp ( partition + 1, stars - i );
}
}
Now, the above DP solution will work only if we are lucky to get constraints that fit the complexity of the DP. When we are unlucky, we will need to be more creative.
Related Problems
- UVa 10541 – Stripe
- SPOJ MARBELS – Marbles
- UVa 11480 – Jimmy’s Balls
- UVa 13035 – Another Combination Problem
- UVa 10532 – Combination! Once Again