Eulerian Numbers


Beginning with the geometric series



which converges for all |x| < 1, we can repeatedly differentiate and multiply by x to give the sequence of identities



and so on. The coefficients of the numerator polynomials on the right side are as shown below.


The sum of the mth row equals the factorial of m. Also, the mth row interpreted as a histogram approaches a normal distribution (just as do the binomial coefficients). The figure below shows a plot of the Eulerian numbers for m = 1 to 85, re-scaled as indicated.



Letting E(m,n) denote the value from the mth row and nth column, we have the general identity



Not surprisingly, the Eulerian numbers have many combinatorial applications. The most famous is the fact that the nth number in the mth row represents the number of permutations of m objects that have exactly n "rises". For example, the six possible permutations of three objects, along with the number of "rises" (i.e., the number of times it goes from a lower to a higher number, reading left to right) are shown below



Thus the numbers of permutations having exactly 0, 1, and 2 rises are 1, 4, and 1 respectively, and these numbers comprise the 3rd row of Eulerian numbers.


If we arrange the Eulerian Numbers with symmetrical indices as shown below



then they can be generated by the well-known recurrence



In addition, they have the interesting generating function



The coefficient of  xm-1 yn-1 (-t)m+n-1 / (m+n)!  is the Eulerian number E[m,n]. Thus we have



I found this by a very indirect approach. Is there a simple procedure for deducing the generating function - if one exists - for a given array of numbers?


There's also a nice relation between Eulerian numbers and the generalized Bernoulli numbers. Let W(m,n) be a weighted average of the nth powers of the first m natural numbers, using the Eulerians as the weights. For example



For m>n it turns out that W(m,n) equals B(-m,n), the generalized Bernoulli number, which can be defined as the coefficients in the expansion



Beginning at the "diagonal" where m=n, the values of W and B begin to differ, although they differ only half the time on the diagonal. Specifically, the differences B(-m,m) - W(m,m) for m = 0,1,2,3... along the diagonal are



which of course are just the ordinary Bernoulli numbers.


The Eulerian numbers can also be used to give a closed-form expression for the sums of powers (and sums of sums of powers, etc.) of the first n positive integers, as discussed in the note on Sums and Differences of Discrete Functions. In that note we derive the closed form expression for the Eulerian numbers



There is also an interesting relation between the Eulerian Numbers and the binomial coefficients. The most obvious recurrence relation satisfied by the binomial coefficients is



but they also satisfy the recurrence



Interestingly, this formula also generates the Eulerian numbers, so both sets of numbers can be regarded as simply different regions of a single array. Here's a brief table of the combined binomial and Eulerian numbers.



On the other hand, it is sometimes convenient to write the array of Eulerian numbers in "rectangular form" as follows:



With these indicies the Eulerians satisfy the recurrence relation



The fact that I've negated the "m" index may seem strange, but it leads to a natural generalization. Suppose that instead of dealing with infinite series, we want an expression for the finite sum



Obviously if N = 0 this sum is given by the simple Euclidean expression



but what about higher values of N? Clearly if we had an expression for the infinite sum



we could subtract it from our original infinite sum (1) to give the desired finite sum. So, our objective is to find a closed form expression for (2). Notice that if we multiply the basic geometric series by xk, we can proceed as before, alternately differentiating and multiplying x to give



where the coefficients Ek{N,j} are taken from an array of number somewhat similar to the Eulerian numbers. Of course, if k = 0 these coefficients are the Eulerian numbers. For other values of k we can generate the coefficients Ek{m,n} (using "rectangular indicies") with the same recurrence as for the standard Eulerians, except that we "slide the indicies around the corner". This is best illustrated with an example. For the case k = 5 we are seeking a closed-form expression for the infinite sum



This is given by (3) with the values of Ek{N,j} taken from the following table for E5{m,n} (and appropriately converting their indicies from the rectangular to the triangular array format):



So, with k = 5 and N = 3, equation (3) gives the identity



Subtracting this from (1) with N=3 gives, as expected



For a less trivial example, suppose we want an abbreviated expression for the finite sum



The procedure is just the same, except that we have k = 101 instead of k = 3, so we need to slide the indicies further around the corner. In other words, the coefficient array with k = 101 is



By the way, a convenient check on the accuracy of these coefficients is to notice that, just as in the case of the basic Eulerian numbers, the sum of the jth diagonal is j!. This table gives us the closed-form expression for the infinite sum



so again we can subtract this from the simple closed-form expression for the infinite sum given by (1) with N=3 to represent the polynomial f(x) of degree 100.


Incidentally, the process of differentiating and multiplying by x can be reversed to give expressions for infinite sums whose coefficients are the inverses of powers of integers. To reverse the process we integrate both sides of the basic geometric series, which gives the well-known expansion for the natural log



Diving by x and integrating then gives the relation



This is the same formula that appears in the note Average of s(n)/n describing the relation between the sum-of-divisor function and the sum of the inverse squares.


Return to MathPages Main Menu