# A Combinatorial Solution

In the last post, we computed the number of times the “Hello World” was printed when executing the code snippet below:


for(int i=0;i<10;i++){
for(int j=0;j<i;j++){
for(int k=0;k<j;k++){
System.out.println("Hello World");
}
}
}


The computation that we did last time was too cumbersome. It turns out that there is a much better way to do it.

Imagine dividing a sheet of paper into ten regions by match sticks as shown below.

How many match sticks do you need to have ten regions? Nine. Suppose you have 3 blue chips. Distribute these chips into any region. They can be lumped together as shown in the figure above or you can put one chip in region 1 and two chips in region 2.

Or you can put a chip in each region.

Now, how does this relate to our original problem? By interpreting the regions as corresponding to the values 1 to 10 and the chips as the variables, whenever a chips is in a region, it assumes that value. So for example, in the first figure, all the chips are in region 1, so we say that the variables $i,j,k$ all have values equal to 1. The second figure is more tricky, we have one chip in the first region, and 2 chips in the second region. So what are the values of $i,j,k$ ? We get a hint from the code snippet itself. Since $k \le j \le i$, we interpret the leftmost chip as the k variable, the middle chip as the j variable and the rightmost chip as the i variable. So, in the second figure, the values of $i,j,k$ are i=2, j=2, and k=1. In the third figure, the values of $i,j,k$ are i=3,j=2, k=1.

The problem is now reduced to counting the number of ways of finding the positions of 3 chips out of 12 positions ( 9 matchings and 3 chips):

$\displaystyle {{9+3}\choose{3}}$

which is equal to 220, the number of times the “Hello World” is printed as we have seen in the previous post.

In general, if N is the range of values of $i,j,k$,

$\displaystyle C = {{N+r -1}\choose{r}}$

is the number of times the “Hello World” is printed.

From the previous post, we know that

$\displaystyle C = \sum_{i=1}^N\sum_{j=1}^i j$

Therefore,

$\displaystyle C = \sum_{i=1}^N\sum_{j=1}^i j = \frac{1}{2}\Big(\sum_{i=1}^N i^2 + \sum_{i=1}^N i \Big)= {{N+r -1}\choose{r}}$

As an aside, we can compute for the sum of squares of the first n numbers from the expression above:

$\displaystyle \frac{1}{2}\Big(\sum_{i=1}^N i^2 + \sum_{i=1}^N i \Big)= {{N+r -1}\choose{r}}$
$\displaystyle \frac{1}{2}\Big(\sum_{i=1}^N i^2 + \sum_{i=1}^N i \Big)= \frac{(N+2)(N+1)(N)(N-1)!}{3! (N-1)!}$
$\displaystyle \sum_{i=1}^N i^2 = \frac{(N+2)(N+1)(N)}{3} - \frac{N(N+1)}{2}$
$\displaystyle = \frac{n(2n+1)(n+1)}{6}$

In summary, the combinatorial solution given above is much more elegant as it gives us the answer without too much computation.