Frank Morgan

Guest post by Jack Wadden ’11 from my Discrete Mathematics 251 class. For more on this topic google “paths in Pascal’s triangle,” e.g. Baez.

I was thinking today about Pascal’s triangle and how amazing it is that the binomial theorem actually works and why each number corresponds to a combination. It turns out that if you think of Pascal’s triangle as an upside down binary tree, this relationship is obvious.Think of each number on the tree as the number of possible paths from the top 1 to the number. It should be obvious then that the possible paths to one vertex is the sum of the possible paths to either of its two parents. These paths can be defined as combinations of choices of turns, left or right.

For example, in order to get to the number “2” we can go right then left, or left then right: two possible paths. Or the sum of the possible paths to each of that vertex’s parents. Therefore the vertex should be labeled “2”.

This is analogous to choosing an x or a y (left is choosing a y and right is choosing an x). The binomial expansion of then involves all the possible paths down to level two of the tree. We can go right twice, choosing x two times. We can go right then left, or left then right to get one x term and one y term. Or we can go left two times, choosing y two times. Summing we then get

Pascal’s triangle is an now an obvious representation of each choice for each (x+y) term. That is, which variable should I multiply by next?

I’m excited by this because it is a truly logical way of thinking about WHY those numbers are the numbers they are, as opposed to just “each term is the sum of the two numbers above it” trick.