Log in

No account? Create an account

Binomial Coefficients and Dynamic Programming

Today in my algorithms class I introduced the concept of dynamic programming. An example I always give is the computation of binomial coefficients. It's a fairly simple problem, and dynamic programming is the most natural choice for an algorithm.

My lectures on the binomial coefficient are always enhanced by a conversation I had with Elle a few years ago. She had called me and asked if she knew of a way to derive the recurrence equation  for binomial coefficients without using the closed formula that involves factorials. (Some women just want  you to come over and kill a spider.)

I'd never seen such a proof. But that didn't mean there was not one, and I was not going to fail a fair damsel asking me for assistance. I pulled out my extra brain cell and got to thinking. Pretty soon I came up with a proof.

For those unfamiliar the binomial coefficient Cm,n is the number of ways you can choose n items from a collection of m items. It is defined by the recurrence equation

Cm,n =Cm-1,n+ Cm-1,n-1

Thanks to my extra brain cell (sure am glad I quit drinking!) I determined that the first item in the sum is the number of combinations you have if you don't include the first element, and the second is the number of combinations you have if you do. Since every combination either has the first item (let's call it A) or it doesn't, this sum is equal to the number of all combinations.

Let's say that you have five items (let's call them A,B,C,D,E) and you want to choose 3.
The number of ways this can be done is C5,3
The combinations that don't include A are


This is all the items from the ones remaining if you exclude A. SInce you are choosing 3 out of 4, this is clearly C4,3

The ones that do include A are


We already have A, and need to pick 2 out of the remaining 4. The number of combinations is C4,2

That's the example I showed my class. I pointed out to them that the logic used here is similar to the logic used in other DP algorithms, such as Floyd's Algorithm for the shortest path problem. Hopefully they were able to see the connection when I went over Floyd's algorithm later in the lecture.

I am grateful to Elle for that phone call a couple of years ago. Just asking me that question helped me to teach dynamic programming more effectively. And it shows that she is a very good teacher...she knows how to ask a very productive leading question. Socrates would be proud of her.