# Combinatorics Coincidence

By Susam Pal on 14 Sep 2008

In this blog post, I will tell you a story about a remarkable coincidence that occurred last week when a friend of mine and I were sharing puzzles with each other.

## Recurrence Relation

While having lunch with my friend, I shared the following problem involving a recurrence relation:

For integers $$n \ge 1$$ and $$k \ge 1,$$ $f_k(n) = \begin{cases} n & \text{if } k = 1, \\ \sum_{i=1}^n f_{k-1}(i) & \text{if } k > 0. \end{cases}$ Find a closed-form expression for $$f_k(n).$$

## Nested Loops

Soon after I shared the above problem, he gave me a problem of his own. Here is the problem shared by him:

Consider the following pseudocode with k nested loops.

x = 0
for c1 in 1 to n:
for c2 in 1 to c1:
...
for ck in 1 to ck-1:
x = x + 1


What is the final value of x after the outermost loop terminates?

## Coincidence

With one problem each, we went back to our desks. As I began solving the nested loops problem shared by him, I realized that the solution to his problem led me to the recurrence relation in the problem I shared with him.

In the nested loops problem, if $$k = 1,$$ the final value of $$x$$ after the loop terminates is $$x = n.$$ This is also the value of $$f_1(n).$$

If $$k = 2,$$ the inner loop with counter $$c_2$$ runs once when $$c_1 = 1,$$ twice when $$c_1 = 2,$$ and so on. Therefore after the loop terminates, $$x = 1 + 2 + \dots + n = \frac{n(n + 1)}{2}.$$ Note that this series is same as $$f_2(n) = f_1(1) + f_1(2) + \dots + f_1(n).$$

Extending this argument, we now see that for any $$k > 0,$$ the final value of $$x$$ is $f_k(n) = f_{k-1}(1) + f_{k-1}(2) + \dots + f_{k-1}(n).$ In other words, the solution to his nested loops problem is the solution to my recurrence relation problem. It was an interesting coincidence that the problems we shared with each other had the same solution.

## Closed-Form Expression

The closed form expression for the recurrence relation is $f_k(n) = \binom{n + k - 1}{k}.$

It is quite easy to prove this using the principle of mathematical induction. Since we know that this is also the result of the nested loops problem, we can also arrive at this result by another way.

In the nested loops problem, the following condition is always met due to the loop conditions: $n \ge c_1 \ge c_2 \ge \dots \ge c_k \ge 1.$

The variables $$c_1, c_2, \dots, c_k$$ take every possible choice of integer values that satisfy the above condition. If we find out how many such choices are there, we would know how many times the variable $$x$$ is incremented.

Therefore the final value of $$x$$ is the number of possible ways of arranging $$k$$ numbers from the first $$n$$ natural numbers in descending order. To find this number, let us consider $$n$$ similar balls and $$k$$ similar sticks. For every possible permutation of these balls and sticks such that there is at least one ball to the right of the rightmost stick, if we count the number of balls to the right of the $$i$$th stick, we get a number that the variable $$c_i$$ (the counter variable in the $$i$$th loop statement) holds in some iteration of its loop. Therefore the variable $$c_i$$ is represented as the number of balls lying on the right side of the $$i$$th stick where $$1 \le i \le k.$$

The above argument holds good because the first stick has more balls to its right than the second one, the second stick has more balls to its right than the third one, and so on, so $$n \ge c_1 \ge c_2 \ge \dots \ge c_k$$ is always satisfied. Further, we have added the constraint that at least one ball must lie on the right side of the $$k$$th stick, so $$c_k \ge 1.$$ Also, any set of valid values for $$c_1, c_2, \dots, c_k$$ can be represented as an arrangement of these sticks and balls.

To compute the number of permutations of $$n$$ similar balls and $$k$$ similar sticks such that there is at least one ball to the right side of the rightmost stick, we need to consider the rightmost ball to be fixed in its position in all permutations. Thus we are left with only $$n - 1$$ similar balls and $$k$$ similar sticks that we can rearrange in different ways. The number of permutations of $$n - 1$$ similar balls and $$k$$ similar sticks is $\frac{(n + k - 1)!}{(n - 1)! k!} = \binom{n + k - 1}{k}.$

This closed-form expression is the solution to both the recurrence relation problem and the nested loops problem.

If you found this blog post interesting, you might also like A Kid Who Could Read My Mind.

Also, follow me on Twitter where I often post about math, Python, Lisp, TeX, Vim, Linux, etc.