Monday, January 26, 2009

Triangular Numbers and Euler’s Number Triangle

As mentioned in a few places (such as here, and here), there is a nice identity stating that a square number can be written as the sum of two subsequent triangular numbers.

Here we are writing \(t^d_n\) for the nth triangular of dimension d (d=2 are the flat polygonals, d=3 for they pyramidal polygonals, etc.)

There is also a nice relationship that connects cubes to polygonal numbers. It turns out that a cube of spheres can be unfolded into a packed-hexagonal pyramid. The “packed hexagonals” or “centered hexagonals” are not quite the usual hexagonal numbers – instead these are hexagons of dots with the gaps filled in. The picuture below shows how square numbers fill the gaps of the hexagonals perfectly to form the “packed hexagonals,” and how these in turn can be stacked to form a cube. Here we are using \({ph}^d_n \) for “packed hexagonals” \(h^d_n\) for hexagonals, \(s^d_n\) for squares, and \(t^d_n\) for triangular numbers.

Combining this result with the "triangulation" identities we have:
This gives us three nice identities for powers of n:

It turns out that these identities generalize for other positive integer powers of n. Every \(n^d \) can be written as a sum of \(t^d_i\) where i ranges from \(n\) to \(n+1-d\). (for any i less than 1, these terms are zero)
1.Write out the sequence of \(n^d\) for at least \(2d-2\) terms. Take the finite difference of this sequence \(d-2\) times (this reduces the sequence down to “2-dimensional” numbers, allowing us to use the 2-dimensional triangular numbers in our calculations).

2.The first term of the new sequence should be 1. Eliminate the first term by subtracting \(t^2_n\) from this sequence. This means that our sum begins with \(t^d_n\), with a coefficient of 1. Ensure that the \(t^2_n\) values are subtracted from the corresponding terms of the sequence.

3. Now, the sequence has a new first term which is A. Eliminate this term by subtracting A \(t^2_n\) from the sequence. A is the coefficient of \(t^d_{n-1}\).

4. Repeat step 3, eliminating the first term of the sequence each time with a multiple of \(t^2_n\), which provides the coefficient for the next value of \(t^d_i\).

5.The process ends when all terms in the \(n^d\) sequence is eliminated, which happens at the dth step.
Carrying out this process for a few more powers of n, we end up with:

In general, we seem to have:
where the coefficients A(i,k) have the nice properties:
The coefficients are naturally analogous to the binomial coefficients, and can be arranged in a triangle like Pascal’s.
These coefficients are known as Eulerian numbers, and the construction above is known as Euler’s Number Triangle (not to be confused with the geometric construction called the Euler Triangle).

See also: