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, rescaled 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 wellknown recurrence 

_{} 

In addition, they have the interesting generating function 

_{} 

The coefficient of x^{m1} y^{n1} (t)^{m+n1} / (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 closedform 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 x^{k}, we can proceed as before, alternately differentiating and multiplying x to give 

_{} 

where the coefficients E_{k}{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 E_{k}{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 closedform expression for the infinite sum 

_{} 

This is given by (3) with the values of E_{k}{N,j} taken from the following table for E_{5}{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 closedform expression for the infinite sum 

_{} 

so again we can subtract this from the simple closedform 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 wellknown 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 sumofdivisor function and the sum of the inverse squares. 
