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.

Triangular numbers

We learn the perfect squares in school.  Here are the first few starting with 1² = 1.

1² = 1
*

2² =4
* *
* *

3² = 9
* * *
* * *
* * *

4² = 16
* * * *
* * * *
* * * *
* * * *

5² = 25
* * * * *
* * * * *
* * * * *
* * * * *
* * * * *

Another series of numbers base on shape are the triangular numbers. Here are the first five examples starting with 1.

*
1 = 1, the 1st triangular number

*
*  *
1+2 = 3, the 2nd triangular number

*
*  *
*  *  *
1+2+3 = 6, the 3rd triangular number

*
*  *
*  *  *
*  *  *  *
1+2+3+4 = 10, the 4th triangular number


*
*  *
*  *  *
*  *  *  *
*  *  *  *  *
1+2+3+4+5 = 15, the 5th triangular number

So the n-th triangular number is the sum of the numbers from 1 to n. There are games where these numbers show up, notably the ten pins in bowling and the fifteen balls other than the cue in pool. There are many places where these number show up in math, including the total number of handshakes necessary in a room with n+1 people so that every possible pair of people shakes hands.  Let's look at the example with 5 people.

Person #1: Shakes hands with 4 people
Person #2: Already counted the handshake with #1, 3 people left.
Person #3: Already counted the handshakes with #1 and #2, 2 people left.
Person #4: Already counted the handshakes with #1, #2 and #3, 1 person.
Person #5: Already counted all the handshakes.

There is a formula for the n-th triangular number, which is ½[n(n + 1)].

Consider our idea called relatively prime, which we discussed yesterday.

Two consecutive square numbers are always relatively prime, like 4² and 5². This follows from the fact that any two consecutive numbers are relatively prime.

After the first pair of triangular numbers, namely 1 and 3, any two consecutive triangular numbers cannot be relatively prime.

Ignoring 1 and 3, the next pair are 3 and 6, which have 3 in common as a factor.

Next are 6 and 10, which have 2 in common.

Next, 10 and 15 have 5 in common as a factor.

The formula shows us the numbers are  ½[n(n + 1)] and ½[(n + 1)(n + 2)]. If n is even, the common factor will be n + 1. If n is odd, the common factor will be ½(n + 1).

The square and triangular numbers have a connection. The sum of two consecutive triangular numbers is always a square.

1 + 3 = 4
3 + 6= 9
6 + 10 = 16
10 + 15 = 25
etc. ...

Here is a picture of 10 + 15 = 25 to give an idea why this always works.

* * * * *
* * * * *
* * * * *
* * * * *
* * * * *

Tomorrow: the Fibonacci numbers.