# Combinatorics Coincidence

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

I met several engineers here who are fond of mathematics in general and combinatorics in particular. The work often involves analysis of authentication tokens, key strengths, information entropy, etc. I think that such work naturally attracts engineers who have an affinity for combinatorics. As a result, discussions about combinatorics problems often occur at the cafeteria. Probability theory is another popular topic of discussion. Of course, often combinatorics and probability theory go hand in hand.

## Recurrence Relation

At the cafeteria one day, I joined in on a conversation about combinatorics problems. During the conversation, I happened to share the following problem:

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 \ge 2. \end{cases} \] Find a closed-form expression for \( f_k(n). \)

## Nested Loops

Soon after I shared the above problem, a colleague of mine shared this problem with me:

Consider the following pseudocode with `k`

nested loops:

```
x = 0
for c
```_{1} in 0 to (n - 1):
for c_{2} in 0 to (c_{1} - 1):
...
for c_{k} in 0 to (c_{k-1} - 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 my colleague, 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 = 0, \) twice when \( c_1 = 1, \) and so on. When the loop terminates, \( x = 1 + 2 + \dots + n. \) 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 \ge 1, \) 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 inequalities are
always met due to the loop conditions:
\[ n - 1 \ge c_1 \ge c_2 \ge \dots \ge c_k \ge 0. \]
The variables \( c_1, c_2, \dots, c_k \) take all possible
arrangements of integer values that satisfy the above inequalities.
If we find out how many such arrangements are there, we will know
how many times the variable \( x \) is incremented.

Let us consider \( n - 1 \) similar balls and \( k \) similar sticks. For every possible permutation of these balls and sticks, if we count the number of balls to the right of the \( i \)th stick where \( 1 \le i \le k, \) we get a number that the variable \( c_i \) holds in some iteration of the \( i \)th loop. Therefore the variable \( c_i \) is represented as the number of balls lying on the right side of the \( i \)th stick.

The above argument holds good because the number of balls on the right side of the first stick does not exceed \( n - 1, \) the number of balls on the right side of the second stick does not exceed the number of balls on the right side of the first stick, and so on. Thus the inequalities mentioned earlier are always satisfied. 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.

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.