Generalized Eulerian Numbers
Starting with the familiar geometric series
1
----- = 1 + x + x^2 + x^3 + x^4 + ... (1)
1 - x
which converges for all |x| < 1, we can alternately differentiate and
multiply by x to give the family of identities
x N-1
----------- SUM E{N,j} x^j = (1^N) x + (2^N) x^2 + (3^N) x^3 + ...
(1-x)^(N+1) j=0
(2)
where the coefficients E{N,j} consist of a row of the Eulerian numbers.
The first few rows of these numbers are tabluated below:
1
1 1
1 4 1
1 11 11 1
1 26 66 26 1
1 57 302 302 57 1
1 120 1191 2416 1191 120 1
1 247 4293 15619 15619 4293 247 1
1 502 14608 88234 156190 88234 14608 502 1
So, for example, we have the identity
inf x
SUM (j^6)(x^j) = ------- ( 1 + 57x + 302x^2 + 302x^3 + 57^4 + x^5 )
j=1 (1-x)^7
By the way, notice that the nth row of Eulerian numbers sums to n!. Not
surprisingly, these numbers have many combinatorial applications. The
most famous is the fact that the jth number in the nth row represents
the number of permutations of n objects that have exactly j "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
permutation rises
----------- -----
123 2
132 1
213 1
231 1
312 1
321 0
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. It's also interesting to note that the rows of Eulerian
numbers approach a normal density, just as do the rows of the binomial
coefficients.
Also, there's a nice Generating Function For Eulerian Numbers.
Anyway, it's often convenient to write the array of Eulerian numbers
in "rectangular form" as follows:
n
-----------------------------------------------------------
m 1 2 3 4 5 6 7 8
--- ---- ----- ----- ----- ------ ----- ----- -----
0 1 0 0 0 0 0 0 0
-1 1 1 1 1 1 1 1 1
-2 1 4 11 26 57 120 247 502
-3 1 11 66 302 1191 4293 14608
-4 1 26 302 2416 15619 88234
-5 1 57 1191 15619 156190
-6 1 120 4293 88234
-7 1 247 14608
-8 1 502
-9 1
With these indicies it's easy to show that the Eulerians satisfy the
recurrence relation
E[m,n] = -m E[m,n-1] + n E[m+1,n]
For example, the value of E[-6,4] is given by
E[-6,4] = 6 E[-6,3] + 4 E[-5,4]
= 6(4293) + 4(15619) = 88234
The fact that I've negated the "m" index may seem strange, but
this leads to a very natural generalization. To describe this
generalization, suppose that instead of dealing with infinite
series, we want an expression for the FINITE sum
(1^N) x^1 + (2^N) x^2 + (3^N) x^3 + ... + ((k-1)^N) x^(k-1)
Obviously if N=0 this sum is given by the simple Euclidean formula
x^k - 1
-------
x - 1
but what about higher values of N? Clearly if we had an expression
for the infinite sum
(k^N) x^k + ((k+1)^N) x^(k+1) + ((k+2)^N) x^(k+2) + ... (3)
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 (3). Notice that if we multiply the basic geometric
series by x^k, we can proceed as before, alternately differentiating
and multiplying x to give
x^k N
----------- SUM E_k{N,j} x^j = k^N x^k + (k+1)^N x^(k+1) + ...
(1-x)^(N+1) j=0
(4)
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 closed-form
expression for the infinite sum
5^N x^5 + 6^N x^6 + 7^N x^7 + ...
This is given by (4) 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):
n
-------------------------------------------
m 5 6 7 8 9 10
--- ---- ----- ----- ----- ------ ------
4 1 -4 16 -64 256 1024
3 5 -39 229 -1199 5901
2 25 -284 2171 -13934
1 125 -1829 17026
0 625 -10974
-1 3125
So, with k=5 and N=3, equation (4) gives the identity
x^5
------- (125 - 284x + 229x^2 - 64x^3) = 125 x^5 + 216 x^6 + ...
(1-x)^4
Subtracting this from (2) with N=3 gives, as expected
1x + 8x^2 + 27x^3 + 64x^4
For a less trivial example, suppose we want an abbreviated expression
for the finite sum
f(x) = 1^3 x + 2^3 x^2 + 3^3 x^3 + ... 99^3 x^99 + 100^3 x^100
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
n
----------------------------------------
m 101 102 103 104
--- ------ ------ ------ --------
100 1 -100 10000 -1000000
99 101 -20199 3029701
98 10201 -3059996
97 1030301
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!. Anyway, this table gives us the closed-
form expression for the infinite sum
101^3 x^101 + 102^3 x^102 + ...
x^101
= ------- (1030301 - 3059996x + 3029701x^2 - 1000000x^3)
(1-x)^4
so again we can subtract this from the simple closed-form expression
for the infinite sum given by (2) 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 geometric series (1), which gives the well-known
expansion for the natural log
inf x^n
SUM --- = - ln(1-x)
n=1 n
Diving by x and integrating then gives the relation
inf x^n / ln(1-x)
SUM --- = - | ------- dx
n=1 n^2 / x
This is the same formula that appears in the note Average of Sigma(n)/n
describing the relation between the sum-of-divisor function and the sum
of the inverse squares.
Return to MathPages Main Menu
Сайт управляется системой
uCoz