Main Applications Identities History FAQ Algorithms

The nth powers hidden in the nth column

                                                

Math needed here:  a little knowledge of linear algebra is useful but not required.

    One of the simplest of the identities is Cat. # 1200002,  ; this states that any two consecutive numbers in the 2nd column, the set of numbers known as the triangular numbers (1, 3, 6, 10, 15, 21, etc.), add up to a square; 1+3 = 4, 3+6 = 9, 6+10 = 16, is the kind of pattern in Pascal’s Triangle that looks like it can’t possibly “go bad” somewhere down the line, and with a little algebraic manipulation, we can convince ourselves that it is true forever.  Let’s take a look at the first few rows 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

    Clearly, the first powers of the positive integers are found in the    column taken one at a time, and the squares of the integers are found in the    column taken two at a time.  It would be great if the cubes of the integers were to be found in the third column by adding three consecutive entries together, but 1+4+10 = 15, which isn’t a cube.  Maybe the cubes are there but we need to work a little harder; can we find three numbers a, b and c such that  ?  Let’s set up three simultaneous equations to solve for a, b and c where n=1, n=2 and n=3.  Putting the equations in reverse order, we get this:

   which becomes the matrix:     

    This matrix is already in upper triangular form, which promises there must be a unique solution; the bottom row tells us c = 1, then substituting we get b = 4 and a = 1.  So now we have a, b and c which work for the first three cases, but why should they work in the fourth case or beyond in this column?  We know that    can be thought of as a cubic polynomial in n, and we know that at the three values 1, 2 and 3, p(1)=1³, p(2)=2³ and p(3)=3³.  The rule for n^th degree polynomials is that if two n^th degree polynomials agree at n+1 points, they must be the same; in the simplest case, two first degree polynomials (lines) are the same if they share two points.  Though we didn’t write it down when we were solving our equations above, p(n) and n³ do share one more point, since p(0)= .

    Using the same method, we can find four numbers a, b, c, and d such that  , and likewise for the all the columns afterwards.  Here are the first few rows of these numbers presented in triangular form.

            1
          1   1
        1   4   1
      1  11  11   1
    1  26  66  26   1
  1  57 302 302  57   1

    This is known as Euler’s Triangle, named for the great 18th Century mathematician, Leonhard Euler of Switzerland. On this website, we designate the Euler numbers with pointed brackets  , following the convention used in one of our major source books, “Concrete Mathematics” by Knuth, Graham and Patashnik; following their convention further, we will call the number at the top of the triangle , though in some of the literature it is called ; in another of our major sources, Stanley’s “Enumerative Combinatorics”, he presents the numbers on page 22 as coefficients of polynomials and  calls the first number A(1,1).

    Returning to the triangle itself, we have a few things we can notice.  

1. The sum of the k^th row is k!, which makes sense in our construction; if we think of  as monic polynomials in n divided by k!, we need to multiply our entries by numbers so that the n^k term is multiplied by k! to cancel out the k! in the denominator, while all lower powers in the polynomial disappear.

2. There is a Pascal-like additive recurrence formula, where we can add two consecutive entries in a row to get the entry that sits between them in the row below.  The difference is we need to multiply the entry on the left by the number of the left-to-right diagonal it belongs to, and the entry on the right by the number of the right-to-left diagonal it belongs to; for example, look at the 26 and 1 in row 5; the 26 is in the 2^nd left-to-right diagonal and the 1 is 5^th right-to-left diagonal, so we get 2×26 + 5×1 = 57, the entry below them in the next row.

3. Since these numbers show up in these two source books, it is only natural to expect that the Euler numbers have a combinatorial meaning, and they do.  Consider all permutations of integers from 1 to n.  Given any permutation p, count the number of times two consecutive entries satisfy p_j>p_j+1; the number of permutations of the first n numbers where p_j>p_j+1 happens k times is the Euler number .  Here is the list of all the permutations of {1,2,3} and the consecutive decreases found in them and the count of increasing sequences, which is always (consecutive decreases+1)

Permutation	Consecutive entries where the value decreases	# of increasing sequences
123	0	1
132	1	2
213	1	2
231	1	2
312	1	2
321	2	3

This shows us that  .  Using the other convention where the numbers on this list would be called  , we would instead be counting the number of permutations of n that have k increasing sequences in them.

Questions left to the reader

1. Since we have both a combinatorial representation of the numbers and a recurrence relationship, can we construct a combinatorial proof for why ?

2.  Give a combinatorial proof of why Euler's Triangle, like Pascal's, is symmetric as we read across the rows.

3. Use the recurrence formula to find the values in the 7^th row of Euler’s Triangle.

Main Applications Identities History FAQ Algorithms