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:

$$a_1 + a_2 + a_3 \dots a_K \leq N$$

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

  1. UVa 10541 – Stripe
  2. SPOJ MARBELS – Marbles
  3. UVa 11480 – Jimmy’s Balls
  4. UVa 13035 – Another Combination Problem
  5. UVa 10532 – Combination! Once Again

Blogger to WordPress Migration

Blogging on Blogger always has been a hassle. Here are some of the things I found annoying about writing a post on Blogger:

  1. The spacing always got messed up. I had to carefully place <br> tags here and there to keep things consistent.
  2. I had to type in HTML. Why? Cause I had codes in my posts and I wanted to highlight them using SyntaxHighlighter. For that I had to create <pre class="brush:cpp;"> tags. You can’t do that in the normal visual panel.
  3. The most annoying part is when I switched between Visual and HTML view in the editor. It always messed up my clean HTML.
  4. I had to HTML escape my code before pasting it ( < sign would need to be &lt;)

Well, that’s it actually. Writing and editing post on Blogger was a pain.

Now that I wanted to resume blogging again, the Blogger editor was making it hard to get started. It would have been amazing if Blogger had a markdown editor, but it didn’t. Nowadays, I write most of my notes in markdown, which I keep in a git repo: notes.

Then, I also read a recent blog post (TechCrunch: Blogger gets a spring cleaning) on how Google stripped down some of the (already lacking) features from Blogger. Forget about getting a markdown editor, someday the whole platform might disappear.

I had to switch before I continue. And I did. And I am glad that I did.

How did I switch? Well, basically I just followed this tutorial: How To Move Your Blog From Blogger To WordPress

Hosting

The first step was choosing a Hosting. I had a few options in this case:

  1. Get a new VPS: I usually just rent a VPS from Linode and directly deploy my projects there. Then again renting a whole server just for a blog seemed slightly overkill to me.
  2. Deploy it on my existing VPS: Better than the first option, but I will have to configure my Nginx. I kind of forgot how I configured it last time, so I was a bit reluctant about this option.
  3. Get a shared hosting: Now, all the tutorials out there suggest this option. I never actually used a shared hosting before, so this option had the charm of “new experience” with it.

So I went for the third option and bought a shared hosting from Dhrubo Host and deployed my WordPress blog from CPanel. Couldn’t believe how easy it was.

Domain Name

While getting the hosting, I noticed that forthright48.com was available again! Yay!

I previously owned forthright48.com domain but didn’t renew the lease after a year due to procrastination (I can be really lazy sometimes).

A few months after my domain expiration I tried to buy the domain again only to find that some random guy bought the domain and is using it to redirect to fb.com. I was really surprised. Why would anybody in this world apart from me be interested with a domain named forthright48.com? And then use it to redirect towards facebook!

I guess they wanted to resell the domain to me for a higher price. I think I once saw an asking price around 3000$ on GoDaddy. Too bad I was too poor to buy it back.

Migrating Posts

Migrating the posts took the biggest toll on me. Though there was a plugin to make things easier for most people, unfortunately, my blog is filled with latex equations. And they all broke down. Mainly the backslash symbol ('\') disappeared from all posts.

So I had to manually fix every single post. It took me 3 days to fix all posts. I fear that there is still some broken stuff left here and there. If you happen to notice any, please leave a comment.

Was It Worth It?

So I went through so much trouble (3 days of manual labor for fixing posts) to migrate my blog. Was it worth it?

  1. Theme: It looks so much better than before. Blogger didn’t have so much option.
  2. Markdown: Finally, I have a markdown editor! Now I can just focus on writing and not worry about the HTML.
  3. Link Checker: I realized the power of WordPress when I found this plugin. It checks all my posts and detects if there is any broken link. Then, it sends me an email! Amazing plugin indeed. I don’t think I could have gotten such a feature from Blogger.
  4. MathJax: I had MathJax on Blogger too, but in order to add MathJax to Blogger I had to manually edit the theme. On WordPress, I just had to install a plugin.
  5. More Plugins: There are so many plugins with so many cool features that I kind of feel like I was living under a rock before. What the heck was I doing on Blogger?

Conclusion

I am really enjoying my old blog on the new WP platform. Now that I can write in markdown, hopefully, I will be able to resume writing again.