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.