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.

Advertisements

Published by

Bobby Corpus

Is an IT Architect.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s