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

Read More

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

Read More

Application of Prufer Code: Random Tree Generation, Cayley’s Formula and Building Tree from Degree Count

On the last post (Prufer Code: Linear Representation of a Labeled Tree), we discussed how to convert a labeled tree into Prufer Code and vice versa. On this post, we will look into some of its applications in problem-solving.

Generating Random Tree

This one is the simplest. Though problem-solving may not require generating random trees, problem setting might. In order to generate a random tree with $N$ nodes, all we need to do is generate a Prufer Code of length $N-2$ with each element being in the range of $1$ to $N$. Next, we just convert the Prufer Code into a tree.

The randomness of the tree depends on the randomness of the sequence generated. Using rand() function is not good since it’s not truly random. How we can generate a random sequence requires a blog post of its own. Maybe I will write a post on it in near future.

Read More