Star and Bars – Combinatorics for CP

Hello guys, welcome back to “code with asharam”. I am back with another mathematics for competitive programming post. In this post, I will discuss star and bars technique to solve a specific set of combinatorics problems. This technique is called ball and urn approach. Problems based on this topic appears quite frequently in competitive programming contests. With that said, let’s now gear up to take a ride into deep oceans of mathematics.

Star and Bars Theorem

The number of ways to put $n$ identical objects in $k$ distinct boxes is given by:
$$^{n+k-1}C_{k-1}$$
Using $^nC_r = ^nC_{n-r}$, we can say that $^{n+k-1}C_{k-1}$ is same as $^{n+k-1}C_{n}$
Above formula can be applied to wide range of problems as we will see later in this post. But before that let’s try to understand the proof of star and bars theorem with.

Proof using star and bars technique

Suppose that there are $n$ identical stars (S) in a row and now, we would like to place bars (B) between these stars to divide them into $k$ parts. It is not difficult to see that we will require total of $(k-1)$ bars to complete our task. Now, consider the following division for $n=5$ and $k=3$.

S S B S B S S 

So, we have divided $5$ stars into $3$ parts using $2$ bars. Clearly, first part contain $2$ stars, second part contains $1$ star and third part have $2$ bars. Now, if you carefully observe, then, you will see that we can consider a region as a box and number of stars in that region as number of objects. Hence, the problem of dividing $n$ stars to $k$ parts is similar to putting $n$ identical objects in $k$ distinct boxes. So, our task now is to find the number of ways to place $k-1$ stars between $n$ stars to divide them into $k$ parts. We can easily solve this problems as follows:
Since there are total of $n+k-1$ positions – $n$ for stars and $k-1$ for bars, the number of ways of choosing $k-1$ positions for bars will be equal to:
$$^{n+k-1}C_{k-1}$$
This can be easily derived from the basic definition of $^nC_r$ which I am assuming you already know.

What if empty boxes are not allowed?

So, in the above problem, it was allowed to have distributions with empty boxes. But what if we are asked to put $n$ objects in $k$ boxes such that each box have at least one object. Let’s consider the division for $n=7$ and $k=3$ but with a different variation:

S _ S _ S _ S _ S _ S _ S

Now, if we want to place $k-1 = 3-1 = 2$ bars such that each part have at least one star, then, we have to place the bars only at one of the ‘_’ positions. Hence, number of ways to place $2$ bars on $6$ positions will be $^6C_2$. In a general case, we have to find the number of ways to place $k-1$ bars in $n-1$ positions which we equal to $^{n-1}C_{k-1}$. In this way, we can tackle the case when empty boxes are not allowed.
So, we have discussed the star and bars theorem in detail. Now, let’s see some applications of star and bars theorem.

Number of non-negative integer sums

The problem is to find the non-negative integer solutions of following equation:
$$x_1 + x_2 + \dots + x_k = n$$
Clearly, above equation is telling us to divide $n$ into $k$ divisions such that divisions of zero size is allowed. This is the direct application of star and bars theorem and can be directly solved by using the first formula.
If instead of non-negative integer solutions, we are asked positive integer solutions, then, the problem will be direct application of 2nd variation of stars and bars theorem.
Above problem can also be solved using dynamic programming. Now, let’s discuss one more interesting variation of this problem.

Number of lower-bound integer sums

In the last problem, $x_i$ was greater than or equal to zero. We also discussed the case when $x_i$ was greater than zero. Now, we will discuss the case when $x_i \ge a_i$.
\[
\begin{array}{c}
x_i \ge a_i \\
x_i – a_i \ge 0 \\
y_i \ge 0
\end{array}
\]
Since $y_i \ge 0$, if we somehow replace $x_i$ with $y_i$, then, we can directly apply the star and bars theorem. And with the beautiful support of mathematics, we can easily replace $x_i$ with $y_i+a_i$. Let’s see how our new equation looks like
\[
\begin{array}{c}
(x_1′ + a_i) + (x_2′ + a_i) + \dots + (x_k’ + a_k) = n \\
y_1′ + y_2′ + \dots + y_k’ = n – a_1 – a_2 – \dots – a_k
\end{array}
\]
Now, apply ball and urn technique on our final equation and celebrate. The final application I am going to discuss is the one I find most beautiful. So, let’s get started!

Coefficient of $x^n$ in expansion of $(1-x)^{-k}$

First important result I would like to tell you is,
$$1 + x + x^2 + \dots = (1-x)^{-1}$$
You can easily verify above relation using sum of a infinite geometric series. The series in above equation is also called famous power series. Clearly,
$$(1-x)^{-k} = (1+x+x^2+\dots)*(1+x+x^2+\dots)*\dots*\text{ k times}$$
Before find coefficient of $x^n$, let’s see how $x^n$ is being generated. To generate $x^n$, we choose a term $x^{a_1}$ from first term, $x^{a_2}$ from second term and so on from the $k$ terms in above product. Now, these $k$ chosen terms when multiplied together should be equal to $x^n$.
\[
\begin{array}{c}
x^{a_1}*x^{a_2}*\dots*x^{a_k} = x^{n} \\
x^{a_1 + a_2 + \dots + a_k} = x^{n} \\
a_1 + a_2 + \dots + a_k = n
\end{array}
\]
Clearly, coefficient of $x^n$ is equal to the number of ways to choose $a_i$ which in turn is equal to the number of solutions of the final equation we obtained. I might not be able to explain the reason for why I found this application beautiful but I will definitely explain the reason when I explain more complex stuff in the future.
So, that’s all for prime numbers algorithms from my side. Now, it is your turn to go to codechef or codeforces and search for problems with combinatorics tag.
Thank you guys for reading so far.
Read more of my mathematics for CP guides here.
Subscribe to my YouTube channel for video tutorials on competitive programming.
Connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: