Combinatorics Coincidence

By Susam Pal on 14 Sep 2008

Combinatorics for Fun

At my current workplace, there are several 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 \geq 1$ and $k \geq 1,$ $f_{k} (n) = {\begin{cases} n & if k = 1, \\ \sum_{i = 1}^{n} f_{k - 1} (i) & if k \geq 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₁ in 0 to (n - 1):
    for c₂ in 0 to (c₁ - 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 realised 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 \geq 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 \geq c_{1} \geq c_{2} \geq \dots \geq c_{k} \geq 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 \leq i \leq 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.

Comments | #mathematics | #combinatorics | #puzzle