I joined RSA a few weeks ago. Here, I met Anoop who loves playing with combinatorics problems. We challenge each other with combinatorics problems.
I asked him the following question at lunch.
For integers n ≥ 1 and k ≥ 1,
f0(n) = 1.
fk(n) = Σni=1 fk−1(i).
Find a closed formula for fk(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.
Consider the following pseudocode with k nested loops.
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 = count + 1
What is the final value in
count after the outermost loop
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. This is also the value of f1(n). If k = 2, the inner loop with the counter as c2 will run once when c1 = 1, twice when c1 = 2, and so on. So, the final value of count will be f1(1) + f1(2) + … + f1(n) = n(n + 1)/2. This is the value of f2(n) as well.
Extending this argument, one may realize that for any k, count = fk−1(1) + fk−1(2) + … + fk−1(n) = fk(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 fk(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: fk+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:
n ≥ c1 ≥ c2 ≥ … ≥ ck ≥ 1.
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 descending 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
right of the ith stick and add one to it, we get a valid value for
ci as the number of balls to the left of a stick can not
increase 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 decrease as we move left and consider
(i − 1)th, (i − 2)th, etc. sticks.
Also, any set of valid values for c1, c2,
…, ck 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.