by Jonathan Kujawa
Everyone learns about Pascal's Triangle when they are young. But I, at least, didn't learn all the wonders contained in the Triangle. Indeed, we're still discovering new things!
To construct the Triangle is easy enough: you start with 1's down the outside edges and each interior number is gotten by adding together the two numbers just above it. So the third number on the sixth line is a 10 because that's the sum of 4 and 6.
Warning! Actually we will say that 10 is the second number in the fifth line. For reasons which will soon become clear, we will choose to start with zero when we count rows and columns of the Triangle. For example, the second number of the fourth line is a 6.
With the addition rule in hand it's off to the races: the Triangle goes on forever and you can calculate as many rows as your patience allows.
Pascal introduced the Triangle in 1653 in Traité du triangle arithmétique as part of his investigation into probability and counting problems. Questions like “If I want to choose two people out of a group of four, how many possible pairs are there?” or “What's the probability of drawing a full house when dealt five cards from a well mixed deck of cards?”. Indeed, Pascal and Fermat essentially invented probability in a series of letters they exchanged around this time. You can see the Pascal's original triangle here.
What does the Triangle have to do with probability? Well, if you want to choose k objects out of a group of n possibilities, then the number of possible choices is precisely the kith number on the nth row of the triangle. Remember, for positions in the Triangle we always count starting from zero! Using this rule we see that there are exactly 6 ways to choose two people out of a group of four. And since 84 is the third number in the ninth row of the triangle, it must be that there are 84 ways to choose three people out of a group of nine. Once you can compute these numbers it's a short step to computing all sorts of probabilities.
At first glance it seems quite mysterious why the Triangle gives the right answer to this question. It also may seem strange that we have to always start with zero to get it to work. To see that both of these things are exactly right, we make two observations.
First, if you have a group of objects, how many ways can you choose to take zero of them? You have exactly 1 way to choose zero objects — namely just by declaring that you choose to take none of them. Similarly, you have only 1 way of choosing to take all of the objects. And this exactly corresponds to the 1's at the two end of each row.
Second, if we want to choose k objects from a group of n, we notice that there are two mutually exclusive scenarios: either our favorite object is one of the chosen or it's not. If we choose it, then we must also choose k-1 objects from the remaining n-1 objects in the group to round out our choice of k objects. If we don't choose it, then we must choose all k objects from the n-1 objects in the group left after we've excluded our favorite. Since these were mutually exclusive, to get the total we should sum the number of choices in each scenario.
In short, to get the number of ways to choose k objects from a group of n, we should add together the number of ways to choose k-1 objects from a group of n-1 and the number of ways to choose k objects from a group of n-1. But this is exactly the addition rule for the Triangle!
We already know the Triangle is completely determined by having 1's down the sides and the addition rule. Since these properties also apply to the answer of the question of choosing objects, the Triangle must also give the right answer.
Being able to make such calculations is invaluable in all sorts of situations. It's little wonder, then, that Pascal was late to the party. These numbers were already considered by Indian, Chinese, and Iranian mathematicians at various times going back more than a thousand years. And certainly everyone will recognize Yang Hui's Triangle from 1303:
Amusingly, even without being able to read the numbers you can find a typo in this 700+ year old Triangle! Hint: The addition rule makes Pascal's Triangle left/right symmetric. If you look carefully, Yang Hui's Triangle fails this symmetry in one place.
I promised that the Triangle is filled with wondrous things. Where's the wonder? Some are easy. If you sum the numbers in the nth row of the Triangle, you will always get 2 raised to the power n (e.g., 1+3+3+1 = 28). For us this is rather boring [2].
Somewhat more interesting is the fact that if you sum the numbers of the Triangle along diagonals you get the Fibonacci Sequence. As we've already seen at 3QD, the Fibonacci Sequence itself already contains all sorts of surprises [3].
Recently something surprising and new was discovered in the Triangle. As we saw, if you sum the numbers in a row of the Triangle something interesting happens. This fact about the sums is as old as the triangle itself. It wasn't until 2012 that Harlan Brothers thought to ask what happens if you multiply the numbers in each row.
Let's write P(n) for the product of the numbers in the nth row of the Triangle. So P(3) is 1*3*3*1=9, P(4) is 96, and so on. The numbers you get don't seem to have any obviously wonderful properties. Mr. Brothers had the idea to look at what happens if you divide these numbers for successive rows. More precisely, for n being 1,2,3, etc., he looked at the numbers r(1), r(2), r(3), … you get from the following formula:
That is, for each row he looked at the fraction where the top is the product of all numbers in the row before and the row after and the bottom is the product of all the numbers in the row in question, each used twice.
Here's the wondrous thing: As n gets larger and larger, this ratio gets closer to the number e! Remember, e is the decimal number which goes on and on forever, but is approximately 2.71828. It appears in compounding interest, models of population growth, and other exponential growth situations. I was astonished that it can be found in such a fairly straightforward way in the Triangle. Once you know to look for e in this way, it's not so hard to see that it this ratio truly does go to e as n gets larger. As you can see here, the calculation itself is just a bit of algebra.
A very nice animation by Richard Green shows Harlan Brothers's result in action [4]:
There is one other wonder in the Triangle everyone should know. Let's color each number in the Triangle according to whether the number is even or odd. For example, we could color the even numbers white and the odd numbers blue. If we do this for the first 500 rows of the Triangle, a striking pattern emerges:
This is the famous fractal known as Sierpinski's Gasket! This leads to all sorts of questions. A number is even or odd if it has remainder 0 or 1, respectively, when you divide by two. What happens when you divide by 8? You then have remainder 0, 1, 2, 3, 4, 5, 6, or 7. What happens if you use eight colors and color each number according to its remainder when you divide by eight? Coloring the first 500 rows of the Triangle in this way gives us this beautiful picture:
There is a fun app on Wolfram Demonstrations which lets you see what happens as you vary the number you divide by (also called the modulus). Helpful hint: when you use the app, click on the little “plus” symbols to reveal the more detailed version of the controls.
There are loads of other wondrous things to be found in the Triangle. A good place to start if you're interested in more is the mathforum.org website. For a more, let's say eccentric, view of what can be found in the Triangle, be sure to take a look here.
[1] Image borrowed from Christopher Olah's blog.
[2] Why? Because we know that the kth number in the nth row is just how many ways of choosing k objects from a group of n. Adding the numbers in the nth row just means you're counting the number of ways of drawing 0 or 1 or 2 or 3 or some other number of objects from a group of n. That is, you're counting how many different ways you can choose some arbitrary number of objects from a group of n objects. But we can count this in another way. You could instead go along to each candidate and declare it as one to keep or one to reject. Each of the n objects has two possible states (kept or rejected). A little thought leads us to realize that to count all the possible choices, we should multiply two with itself as many times as there are objects. That is, there are 2*2*2*…*2 = 2n possibilities.
[3] So much so that even today there are new things to be discovered and unanswered questions. One of these days I'll get around to putting it together some of these discoveries into a post for 3QD.
[4] I first learned of Brothers's result from Dr. Green's always excellent Google+ posts.