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.

permutations and factorials

A permutation is an arrangement of n distinct objects where order matters. For example, if you have a deck with n cards, all the permutations would mean every possible arrangement you could create by shuffling the cards.  For this demonstration, let's use the lowercase letters of the alphabet for our objects.

If we have only one object, there is only one permuation: a

If we have two objects, there are two permuations: ab and ba

Three objects increases the number of permuations to six: abc acb cab bac bca cba

Four objects can be arranged into 24 different permutations.

This number sequence 1, 2, 6, 24, ... is the start of the factorials, which are denoted with an exclamation point.

1! = 1
2! = 2 × 1 = 2
3! = 3 × 2 × 1 = 6
4! = 4 × 3 × 2 × 1 =24
5! = 5 × 4 × 3 × 2 × 1 = 120
...

Here's why the sequence increases this way. We have the list above of the six permutations of the letters a, b and c. If we add the letter d to the list, let's take a look at any of the three letter permutations, for example cab. It's possible to add in the d to this pattern in four places.

dcab cdab cadb cabd

The d can be put in the first, second, third or fourth position. Since there are six different permutations, we multiply six by four to get twenty four different permutations of four distinct objects.

 The factorials increase very quickly, even faster than exponential growth. 10! = 3,628,800 and if we consider the number of ways to shuffle a standard 52 card deck, 52! is a number with sixty eight digits, 8.0658 × 10^67. A deck with 60 cards would have more different permutations than the current estimate of atoms in the observable universe.

Tomorrow, we'll look at a way to categorize permutations and introduce the numbers in Euler's Triangle.

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.