Combinatorial Coincidence

By Susam Pal on 14 Sep 2008

Combinatorics for Fun

I joined RSA a few weeks ago. It is a small and delightful place with a great work culture. It was founded by Ron Rivest, Adi Shamir, and Leonard Adleman (the inventors of the RSA algorithm) in 1982. The company develops and sells the RSA BSAFE cryptography libraries, SecurID two-factor authentication tokens, and several network security software products these days.

Perhaps due to the nature of work in this domain, some of the engineers in this organization also happen to be math geeks. There is a certain fondness for combinatorics among the engineers which I believe is due to being involved with the analysis of security tokens, authentication schemes, password complexity, information entropy, etc. on a daily basis. Probability theory is another popular topic of discussion. Of course, often combinatorics and probability theory go hand in hand. There is a culture of challenging each other with combinatorics problems for fun.

Recurrence Relation

One of these math geeks is a good friend of mine. Recently, I shared the the following problem with him at lunch:

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 started 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.