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.