Dynamic Programming — Binomial Sequence
Today is the day, when I finally understood the real use of Pascal Triangle. The pascal sequence is something I coded in my freshmen year in university. It was a fun exercise. It was one of the problems in the series of finding patterns and coding them in C or Java.
Dynamic programming questions can be tricky. Binomial Sequence and its variants have always been my nemesis. The solutions never come to me easily, and even when it does, it does not always lead to working code. That’s why I decided to try a new source for Dynamic Programming this time, and read the chapter 8 of Skiena. While reading, this problem was discussed, and boom it all came back to me. The connection between binomial sequnce, pascal triangle and dynamic programming was reinstated. Ironically, the solution to question which I have always struggled with, variants of binomial sequence, is one of the first programs I wrote, Pascal Triangle.
Pascal’s triangle is as shown above. In it, every element in the series is the sum of the two numbers “RIGHT ABOVE IT”. The question then comes is, what does “right above” mean? How can something that can be seen easily, expressed in code?
If we take the example of 6 in the diagram, the numbers right above it are 3 and 3. 6 is in 4th row, and 3rd column within it. The two threes are a row above — row number 3, and 2nd and 3rd column respectively. A similar pattern can be seen for the 10s in the 5th row. Now, the relation which we can derive from this is — Every [n,k]th element is the sum of [n-1,k] and [n-1,k-1] elements.
Now, how does this connect with the binomial theorem. Recall, the binomial number is as follows -
The physical meaning of this is, if we have to choose k elements from n elements. We can either choose the nth element and choose the remainder k-1 elements from the remaining n-1 elements or drop the nth element and choose all the k elements from the remaining n-1 elements. A certain symmetry of what we saw in pascal triangle should be apparent here.
Now, coming to coding this. If we represent the results of each nCk in a matrix, then we can effectively calculate the higher orders of the sequence. It will also be clear that once an element is calculated, it can be put to use in other subsequence calculations as well . This means that there is good memoization potential!
Let’s begin with the recursive solution for binomial sequence. There is a clear recurrence observed here. For any recurring function, base cases are needed. For binomial sequence, the base case would be when we have select 0 elements out of n. Such a selection can be made in only one way — NULL SET. Another base case would be, when we have to select ALL n elements from a set of n. Which again can be done in 1 way. Next is selecting 0 elements from n, can be done in 1 way. Finally, selecting 1 element from n, can be done in n ways. All these are the bases cases which we should care about.
The recurrence solution can be written as below.
Note that the above solution has many overlapping subproblems which are recalculated. In order to avoid the recalculation, we can store it in a matrix. Let’s discuss this with an iterative solution. We begin by initializing the matrix with appropriate value for the base cases we discussed above. (Note: In the code, I took the easy way out and initialized ALL elements to 1. This is wasteful.) The only case which is not represented here is choosing 1 element from n. This case we shall calculate. The iterative solution in python is as below —
The result on running the iterative solution is as below
In this post we discussed the binomial sequence and its relationship with pascal triangle. We went through my journey of figuring this relationship, and realized how sometimes connecting the dots can take 10 years. We also discussed the solution for the same, both iterative and recursive. I highly recommend reading Skiena and CLRS for algorithms if you not already have.