Combinatorial coincidence

I joined RSA a few weeks ago. Here, I met Anoop who has a passion for combinatorics. We challenge each other with combinatorics problems.

I asked him the following question at lunch.

f₀(n) = 1; f_k(n) = Σⁿ_i=1 f_k-1(i). Find a closed formula for f_k(n).

He asked me one on programming. I have used subscripted variables to represent the counters for the nested loops in the pseudocode to show the question.

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

What is the final value in count after the loop exits?

With one question each, we went back to our desks. As, I started solving his question on nested loops, I realized that his problem led me to the recurrence relation in the question I asked him. If k = 1, count = n = f₁(n). If k = 2, the inner loop with the counter as c₂ will run once when c₁ = 1, twice when c₁ = 2, and so on. So, the final value of count will be f₁(1) + f₁(2) + ... + f₁(n) = n(n+1)/2. One may note that this is the value of f₂(n).

Extending this argument, one may realize that for any k, count = f_k-1(1) + f_k-1(2) + ... + f_k-1(n) = f_k(n). In other words, the answer to his question is the answer to my question. I already knew the answer to this. So, I went back to his desk with the answer: C(n+k-1, k).

I had arrived at this closed formula earlier by solving f_k(n) for the first few k's using Faulhaber's formula. I noticed that they were all equal to C(n+k-1, k). So, I proved that this is always true by the principle of strong mathematical induction. It involved proving that: f_k+1(n) = C(k, k) + C(k+1, k) + ... + C(n+k-1, k) = C(n+k, k+1)

This was a remarkable coincidence that we asked each other questions which had the same answer. When I explained the coincidence to him, he explained how he arrived at the same result for the question on nested-loops which can be used to determine the closed formula for the recurrence relation too.

In the question on nested-loops, the following condition is always met: 1 <= c₁ <= c₂ <= ... <= c_k <= n. So, the number of times count variable would be incremented is equal to the number of possible ways we can arrange k numbers from the first n natural numbers in ascending order. The answer to this is the number of possible ways we can arrange n - 1 similar balls and k similar sticks. If we consider the number of balls to the left of ith stick and add one to it, we get a valid value for c_i as the number of balls to the left of a stick can not decrease as we move right and consider (i+1)th, (i+2)th, etc. sticks. Similarly, the number of balls to the left of a stick can not increase as we move left and consider (i-1)th, (i-2)th, etc. sticks. Also, any set of valid values for c₁, c₂, ..., c_k can be represented as an arrangement of these sticks and balls.

We can arrange n-1 similar balls and k similar sticks in (n+k-1)! / {(n-1)! × k!} = C(n+k-1, k) number of ways. This is the answer to the question on nested loops as well as that on the recurrence relation.