Pascal's Triangle long before Pascal.

Blaise Pascal did not call the array of numbers he studied "Pascal's Triangle". In math, it's considered poor form to name something after yourself.

Pascal's Treatise on the Arithmetic Triangle was published posthumously. In it, he gathered together all the facts he knew about the patterns he discovered himself or had read about in other books.  It became the "go to" text for information about the array and other mathematicians started calling it "the triangle of M. Pascal" so much so that it is now the way nearly everyone in the world refers to it.

Nearly everyone. About 100 years before Pascal, the great Italian algebraist Niccolo Fontana, known by his nickname Tartaglia - which means "the stammerer" - did a lot of work with the number pattern and in Italian the array is known as Tartaglia's Triangle.

Several centuries earlier, the Chinese were discovering things about the array, and in Chinese it is known as Yang Hui's Triangle.

But the Chinese from 700 years ago are not the first people to study the numbers and leave a paper trail behind that future generations could find. There are two completely different problems from before the birth of Christ that originate in India whose answers come from the numbers in the array we call Pascal's Triangle.

Let's say we have a spice rack with six flavors: salt, pepper, garlic, nutmeg, curry and basil.  How many different combination of three spices are there? (Note: in this problem, we are not saying how much of any one spice we are using, only if it is used. Two parts salt and one part garlic would taste different from one part salt and two parts garlic, but in this problem we would say that both are salt/garlic combinations.)

If we abbreviate the spices to S, P, G, N, C and B, here are the 20 different groups of three

Salt included

SPG  SPN SPC  SPB
SGN SGC SGB
SNC SNB
SCB

Salt excluded, pepper included
PGN PGC PGB
PNC PNB
PCB

Salt and pepper excluded, ginger included
GNC GNB
GCB

No salt, pepper or ginger
NCB

The other ancient problem from India that uses the binomial coefficients deals with music and rhythm. In the musical notation developed in Europe that is used almost everywhere today, if we say a song is in a rhythm of six beats, all those beats have the same duration. In India, beats can either be short or long. For instance, let's say we had a song that has double hand claps on the second and fourth beat of every measure, so the pattern might the counted out

bump clap-clap bump clap-clap...

In Western music, we would say this is a four beat pattern. In Indian music, they would say it is a six beat pattern.

long short short long short short.

Okay so how many different six beat patterns have three long beats and three short beats? Again the answer is 20.

First beat long
LLLSSS LLSLSS LLSSLS LLSSSL
LSLLSS LSLSLS LSLSSL LSSLLS
LSSLSL LSSSLL
First beat short, second beat long
SLLLSS SLLSLS SLLSSL SLSLLS
SLSLSL SLSSLL
First two beats short, third beat long
SSLLLS SSLLSL
SSLSLL
First three beats short
SSSLLL

At first glance, these problems don't seem to be connected, but in fact they are. If we line up the spices alphabetically in English, we would get.

Basil Curry Garlic Nutmeg Pepper Salt

Take any six beat pattern.

LLSSLS

Think of L as being yes and S as being no

YesYesNoNoYesNo.

Make a spice combination where we only use the spices that correspond to the Yes positions.

Basil Yes, Curry Yes, Garlic No, Nutmeg No, Pepper Yes, Salt No.

In this way, the beat pattern LLSSLS corresponds to the recipe that uses basil, curry and pepper. If two beat patterns are different, they will correspond to different recipes. In math, this kind of matching is called a one to one correspondence, and it is one way to prove that one set of objects has the same number of things as another set.

Tomorrow, we will look at actual geometric triangles, notably triangles with one right angle, known simply enough as right triangles.

The Hockey Stick Theorem

Earlier, we discussed the pattern from Pascal's Triangle known as the Christmas Stocking Theorem, named for a shape that has a toe and a leg, the leg being a column inside the triangle. Here is an example in bold and blue.

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10 5  1
1  6 15 20 15  6  1

What this shows is that 20 = 10+6+3+1, the toe of the stocking equal to the sum of the numbers in the leg.

A Hockey Stick will lie flat across a row like this

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1

Obviously, the 6 in the toe is not the sum of the numbers in the row below. It is the alternating sum, which is to say we start at the 21 just below the 6, then subtract the 35 to the left, then add the next 35, subtract the next 21, add the 7 then subtract the 1. Let me write it this way, with the subtractions written in red.

6 = 21 - 35 + 35 - 21 + 7 - 1

Here is the summation notation of the pattern.

If I were in front of a class, I would say

"n choose r equals the alternating sum of negative one to the r-k power times n+1 choose k as k goes from 0 to r."

Alternating sums always have -1 raised to integer powers, since (-1)(-1) = 1 but (-1)(-1)(-1) = -1, etc. -1 raised to an even power is 1, while raised to an odd power is -1.

Tomorrow, we will learn the closed form of the binomial coefficients, a useful thing to know if we want to find out the different number of five card hands in poker without having to write out rows 0 to 52 of the triangle.

The naming convention for Pascal's Triangle.

Yesterday, I wrote down the rules for creating Pascal's Triangle using addition of the row elements above the chosen row element. Here are the values of the first nine rows.

row 0 = 1
row 1 = 1  1
row 2 = 1  2  1
row 3 = 1  3  3  1
row 4 = 1  4  6  4  1
row 5 = 1  5 10 10  5  1
row 6 = 1  6 15 20 15  6  1
row 7 = 1  7 21 35 35 21  7  1
row 8 = 1  8 28 56 70 56 28  8  1

Notice that we call the top row "row 0" instead of "row 1".  We do a similar thing when labeling the columns. The left most column, which is filled with the number 1 in every row, is column 0. For example, the 6 in row 4 is "row 4, column 2".  Here is a triangle of the labels, where r2c0 is shorthand for "row 2, column 0".

r0c0
r1c0 r1c1
r2c0 r2c1 r2c2
r3c0 r3c1 r3c2 r3c3
r4c0 r4c1 r4c2 r4c3 r4c4
...

The standard way to say the name of a binomial coefficient is "5 choose 2" or "7 choose 3". "5 choose 2" is the first 10 in row 5. "7 choose 3" is the first 35 in row 7.

Here is why that name caught on.  Let's say you have five distinct things that you can tell apart. We'll call them a, b, c, d and e. How many different ways are there to choose two of them? If you think of them as cards in a deck, this would be the same as asking how many different two card hands can you make, where ae is considered to be the same as ea. (In most card games, you are allowed to rearrange your hand and the order of the cards in your hand is not essential to the rules of the games.) Here is the list of all the two card hands in alphabetical order, where each hand has the letters in alphabetical order as well.

ab ac ad ae (all the hands where a is the in the hand)
bc bd be (all the hands where b is the first card alphabetically)
cd ce (all the hands where c is the first card alphabetically)
de (all the hands where d is the first card alphabetically) 

Counting it this way, we get 4+3+2+1 = 10. As it turns out "n choose 2" is always a triangular number. If you look at column 2 in the Pascal's triangle above, you see 1, 3, 6, 10, 15, 21, 28..., the first seven triangular numbers.

Let me make the list that corresponds to "7 choose 3". Our list of things is now {a, b, c, d, e, f, g}. It wouldn't change anything vital to make the list {1, 2, 3, 4, 5, 6, 7}. Any seven things we can tell apart will do.

Here are all the three letter groups that include a in alphabetical order.

abc abd abe abf abg
acd ace acf acg
ade adf adg
aef aeg
afg

So far, 15 things on the list. Now the three letter groups where b comes first alphabetically.

bcd bce bcf bcg
bde bdf bdg
bef beg
bfg

10 more, the total is now 25. Groups with c as the first letter.

cde cdf cdg
cef ceg
cfg

6 more, total is 31. Groups with d first.

def deg
dfg

3 more, total  34. And one last group where e is the first letter in the group.

efg

The final total is 35.  Notice that this says that "7 choose 3" = 35, a number in the third column can be created as a sum of numbers in the second column. Let me mark those numbers in red and bold in this copy of the triangle.


1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1

This leads us to one of the first patterns embedded in Pascal's Triangle, often called The Christmas Stocking Theorem, since the shape looks something like a sock or a boot. In this case the 35 is the toe and the other numbers make up the part that covers the leg.  

Tomorrow, I will show a construction style proof that makes it clear the Christmas Stocking Theorem works for any number in the Triangle used as the toe, providing it isn't in column 0, because we need a non-empty column to the left to make this pattern work.

Pascal's Triangle

You may have seen Pascal's Triangle at some time in your education. It is an array of numbers where each row has one more number in it than the last row. The top row is just the number 1 and the second row is 1 and 1, so these rows look like this.

1
1  1

The rule for creating the entries of a row are based on the row just above it. Here is how to state it as a sentence.

An entry in Pascal's Triangle is the sum of the entry just above it in the previous row and the number just above it and to the left.  If one of these numbers doesn't exist, assume it is zero.

That means the next row down will be 1(+0), 1+1 and (0+)1 so the first three rows look like

1
1  1
1  2  1

Like the Fibonacci sequence, the numbers go on forever.  Here are the first nine rows, which is the last row before the biggest number is more than two digits long.

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10  5  1
1  6 15 20 15  6  1
1  7 21 35 35 21  7  1
1  8 28 56 70 56 28  8  1    

The numbers are known as the binomial coefficients and they turn out to be the answers to a remarkable number of different questions about how to count things. The field of counting things in math is called combinatorics. This because it sounds more impressive to say "I study combinatorics" instead of saying "I count things for a living."

All this week we will look at the numbers in Pascal's Triangle and discuss the history how these numbers were used.

Tomorrow: The standard way to identify numbers in the array.