Permutations and Euler's Triangle

Let us assume the object we are arranging in our permutation have some natural order. For example, if we are using the first five letters of the alphabet, the natural order would be the permutation abcde, while the opposite direction edcba would be as far out of order as we could imagine.

What we will look at is consecutive pairs in a permutation and we will count them as being in order or not being in order. For example, let's take ecabd.

ec not in alphabetical order
ca not in alphabetical order
ab in  alphabetical order
bd in alphabetical order

So this is a sequence that has two consecutive pairs in order and two that are not.  It is not the only permutation of five letters with this property. For example, adecb also has two consecutive letter pairs in order (ad and de) and two that are not (ec and cb).

If we want to count such things, the easiest tool to use is Euler's Triangle. Here are the first few rows.

1
1  1
1  4  1
1 11 11 1
1 26 66 26 1
...

It bears some resemblance to Pascal's Triangle, since the first and last numbers in each row are always 1 and each row reads the same forwards and backwards.  The first few rows of Pascal's Triangle are

1
1  1
1  2  1
1  3  3  1
1  4  6  4  1
1  5 10 10 5 1
...

The next row of Pascal's Triangle can be created by adding together the consecutive elements of the previous row. The rule is similar for Euler's Triangle, except we have multipliers for each number. Let's use the row 1 26 66 26 1 to make the next row

1 × 1 ...  2 × 26 ...  3 × 66 ...  4 × 26 ... 5 × 1
+ 0   ... +5 × 1 ... +4 × 26 ... +3 × 66 ... +2×26 ... +1×1

1 ... 57 ... 302 ... 302 ... 57 ... 1

The sum across any row of Pascal's  Triangle is always a power of 2.

1   sum = 1
1  1   sum = 2
1  2  1   sum = 4
1  3  3  1   sum = 8
1  4  6  4  1   sum = 16
1  5 10 10 5 1   sum = 32


The sum across any row of Euler's Triangle is always a factorial.

1   sum = 1! = 1
1  1   sum = 2! = 2
1  4  1 sum = 3! =6
1 11 11 1   sum = 4! = 24
1 26 66 26 1 sum = 5! = 120
1 57 302 302 57 1   sum = 6! = 720

Like Pascal's Triangle, Euler's Triangle shows up in places that don't seem to have much to do with factorials on first blush, just as Pascal's Triangle might show up in a formula that doesn't seem to have much to do with powers of 2.

As a reminder the first 1 in the fifth row means there is just one way to order the first five letters in perfect alphabetical order abcde. The first 26 means that if there is just one thing out of place, like dabcem there are 26 patterns that fit that description.

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 closed factorial form for the binomial coefficients

So far we have learned how to create Pascal's Triangle by using one row to generate the next.

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
...

What if we wanted to know how many different five card hands of poker there are. If we care about the suits of the cards, then "four aces and the king of spades" is different from "four aces and the king of clubs".  Counting that way the number of cards is "52 choose 5", the number of way to select five cards from a deck of fifty two.

Here is the closed form for the binomial coefficients. If this is the first time you have seen an exclamation point used in math, it means factorial.

n! = n(n-1)(n-2)(n-3)...(3)(2)(1), all the whole numbers from n to 1 multiplied together.  Let's do an example from part of the triangle we've already seen.

7 choose 2 is 7!/[2!5!]. notice that the 5×4×3×2×1 shows up in both the numerator and denominator, so it therefore can be cancelled out. We are left with 7×6/(2×1), which is 21.

 52 choose 5 will also have a lot of simple cancellations, and we end up with five consecutive numbers in the numerator divided by 5×4×3×2×1. When all the denominator is cancelled out, we are left with 2,598,960.

Tomorrow: Two problems from ancient India solved by numbers from the Triangle.

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 sum of the n-th row of Pascal's Triangle is 2 to the n-th power

Yesterday, we proved the statement that is the title of this post. Why prove it again?

Proof in mathematics is vitally important and multiple proofs of the same fact (or theorem) can show different ways things are connected to each other.

The style of proof we see today is called induction. Here is the basic idea.

1. Make a statement about an infinite number of things that you can put in order.
2. Prove it for the first thing.
3. Prove that if it is true for any given thing on the list, it must also be true for the next thing on the list.

The infinite things we are putting in order are the sums of the rows of Pascal's Triangle.

1=1
2=1+1
4=1+2+1
8=1+3+3+1
...

The first thing on the list is the sum of 1 in row 0. 1 = 2º, so that means we have done steps 1 and 2 of induction.

Now I'm going to cheat a little to make things clear. I am going to use the third row of Pascal's Triangle for my next step. I shouldn't use a specific row because induction has to be about any given row. I'm going to cheat here to convince the reader that what happens to go from the third row to the fourth row happens going from any row to the next.  I'm going to use four different colors on the four different numbers.

1 3 3 1 

next row created by adding numbers from the current row. (0 are in black.)

0+1 1+3 3+3 3+1 1+0

Notice that every color of number shows up exactly twice, two purple 1s, two red 3s, two green 3s and two blue 1s. This means that the sum of this row must be exactly twice the sum of the row we were looking at.

Proving this is true between rows three and four is not enough. You need to convince yourself the pattern of doubling is true between any two consecutive rows. The reason that it's true is that every number in a row is used exactly twice in two different sums to create the entries of the next row.

Tomorrow, we continue to look at patterns in Pascal's Triangle.  We have seen the Christmas Stocking, now we will discover the hockey stick.
 
 

The sum of the n-th row of Pascal's Triangle is always 2 to the power of n.

Yesterday, we discussed the Binomial Theorem, the standard way to expand a binomial, here expressed as (x + y), raised to any positive integer power n.


We also have a simple pattern easily visible in the first few rows of Pascal's Triangle.

1 = 1
2 = 1+1
4 = 1+2+1
8 = 1+3+3+1
16= 1+4+6+4+1
...

From what we can see, the sum of the n-th row is 2 raised to the power of n. In math, we can't just say we see a pattern for a few rows and assume it is always true, we need to prove it is true. Here is the proof.
  

Step 1 is no more difficult than 2 = 1+1.  Pretty easy.

Step 2 is to take the Binomial Theorem and replace the general binomial (x + y) with the specific binomial (1+1). So we get all the entries of row n multiplied by powers of 1 then added up.

Any integer power of 1 is 1, so we can erase those powers because they are superfluous.

Now we just have the sum across the row. Since the equations are of the form

a = b, then b = c, then c = d, we can also say a = d.

This is not the only way to prove this. Another proof of this basic property of Pascal's Triangle tomorrow.

The binomial coefficients

The translation of the word binomial means "two names". In algebra, a polynomial is an expression with several terms, a term being a set of numbers and variables multiplied together. The number in the term is called the coefficient.  Here are some examples

7xyz² is a single term with three variables. 7 is the coefficient, Since the z is raised to the second power, if we wrote this out in letters it would be 7xyzz, and since we have to used four letters to write this out completely, we say this is a fourth degree term.

7xy - 2z² is two terms, so it is called a binomial. The coefficient of the first term is 7 and the coefficient of the second term is -2.

What happens when we raise a binomial to different powers? Here are the first few examples.

(x + y)º = 1
(x + y)¹ = x + y
(x + y)² = x² + 2xy + y²
(x + y)³ = x³ + 3x²y + 3xy² + y³

If we strip away the variables and just look at the coefficients, we get

1
1 1
1 2 1
1 3 3 1

If you have been reading the blog this week, you know those are the first few rows of Pascal's triangle.

Here is the standard summation form of this fact, usually called The Binomial Theorem.

  
Notice that the powers for x and y always add up to n when we raise (x + y) to the n-th power.

You might also notice that the sums of the rows of Pascal's Triangle has an easily recognizable pattern.

1 = 1
2 = 1+1
4 = 1+2+1
8 = 1+3+3+1

In these first few cases, it looks like the sum of the n-th row is 2 raised to the power of n. There are many ways to prove this pattern continues forever. 

Tomorrow, we will use The Binomial Theorem to prove this pattern.

An informal proof of the Christmas Stocking Theorem

Let's put a few rows of Pascal's triangle up yet again and choose one of the entries "at random", providing it isn't in the leftmost column.

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 first rule we have learned about entries in that any entry is the sum of the entry just above it and the entry above it and to the left, in this case, 35+21 = 56.


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

I'm going to use the same rule on the 21, changing it to 15+6, the entries above it.

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

Now the 6,  changing it to 5+1, the entries above it.

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

Now the 1 in row 5 is exchanged for the 1 in row 4, actually 1 = 1+0, but the zero is invisible.

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

Now I un-bold the 1 in row 5 and we have our standard Christmas Stocking, the sum of the leg in bold red being equal to the toe in bold black.


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

Here is how I could say the theorem in everyday language.

Pick any column in Pascal's Triangle.  Starting at the top of the column, select as many entries as you want and add them up. The sum will be equal to the entry that is one row down and one column to the right of the position where you list of entries ended.

Here is how I would write this in summation notation.  The letter k stands for the column, the letter n stands for where we stop counting and the letter j is the summation variable, which goes from k to n.

Here is how I would say this summation out loud if I were explaining it in class.

The sum as j goes from k to n of "j choose k" is "n+1 choose k+1".

The parentheses with two numbers on top of each other is the standard way to write the numbers of Pascal's Triangle, known collectively as the binomial coefficients. The editor that Blogger uses doesn't have an elegant way to put up a summation symbol or stacking numbers inside a parentheses, so I will write "8 choose 5" = 56 when I mention an entry or "j choose k" when discussing a general entry.

Tomorrow: Why the entries are called binomial coefficients.

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.