# General Eulerian Numbers and Eulerian Polynomials

Authors: Tingyao Xiong; Hung-Ping Tsao; Jonathan I. Hall
Journal: Journal of Mathematics
 (2013)

---

## Abstract

We will generalize the definitions of Eulerian numbers and Eulerian polynomials to general arithmetic progressions. Under the new definitions, we have been successful in extending several well-known properties of traditional Eulerian numbers and polynomials to the general Eulerian polynomials and numbers.


---

## Body

## 1. Introduction

Bernoulli [1, pages 95–97] had introduced his famous Bernoulli numbers, denoted by B2r (B2r+1=0 for r≥1) to evaluate the sum of the nth power of the first m integers. He then proved the following summation formula:
(1)∑i=1min=mn+1n+1+mn2+1n+1∑r=1⌊r/2⌋‍(n+12r)mn-2r+1(-1)r+1B2r,
when n,m≥1.Two decades later, Euler [2] studied the alternating sum∑i=1m‍(-1)iin. He ended up with giving the following general result [3, (2.8), page 259]:
(2)∑i=1m‍inti=∑l=1n‍(-1)n+l(nl)tm+1ml(t-1)n-l+1An-l(t)+(-1)nt(tm-1)(t-1)n+1An(t).
Another simplified form of ∑i=1m‍inti is the following [3, (3.3), page 263]:
(3)∑i=1m‍inti=-tm+1∑k=0n‍(nk)mn-k(1-t)k+1Ak(t)+t(1-t)n+1An(t),
where An(t), (n=0,1,2,…) are called Eulerian polynomials and are recursively defined by [3, (2.7), page 264]:
(4)A0(t):=1,An(t)=∑k=0n-1‍(nk)Ak(t)(t-1)n-1-k.Note that for∑i=1m‍inti, if we put t=-1, then ∑i=1m‍inti becomes the alternating sum of the nth power of the first m positive integers. Furthermore, as m→∞, we have [3, (3.2), page 263]:
(5)An(t)(1-t)n+1=∑j=0∞‍tj(j+1)n(n≥0).Each Eulerian polynomial can be presented as a generating function ofEulerian numbersAn,k [4], also introduced by Euler, as
(6)An(t)=∑k=0n-1‍An,ktk.Furthermore, the corresponding exponential generating function [3, (3.1), page 262] is
(7)A(t,u)=∑n≥0‍An(t)unn!=t-1t-exp(u(t-1)).The following combinatorial definition of Eulerian numbers was discovered by Riordan in the 1950s.Definition 1.
A Eulerian numberAn,k is the number of permutations p1p2p3…pn of the first n numbers {1,2,…,n} that have k ascents (or descents), that is, k places where pj<pj+1 (or pj>pj+1), 1≤j≤n-1.Example 2.
Whenn=3,k=1, and A3,1=4, because there are four permutations with only one ascent:
(8)132,213,231,312,
then An,k satisfies the recurrence: An,0=1,   (n≥0),An,k=0(k≥n) and
(9)An,k=(k+1)An-1,k+(n-k)An-1,k-1(1≤k≤n-1).It is well known that Eulerian numbers have the following symmetric property:Proposition 3.
Given a positive integern, and 0≤k≤n-1, An,k=An,n-1-k.Proof.
It is obvious because if a permutation hask ascents then its reverse has n-1-k ascents.Furthermore, the values ofAn,k can be expressed in a form of a triangular array as shown in Table 1.Table 1
First few values of Eulerian numbersAn,k.
k =
0
1
2
3
4
5
n = 1
1
2
1
1
3
1
4
1
4
1
11
11
1
5
1
26
66
26
1
6
1
57
302
302
57
1Besides the recursive formula (9), An,k can be calculated directly by the following analytic formula [3, (3.5), page 264]:
(10)An,k=∑i=0k‍(-1)i(k-i+1)n(n+1i)(0≤k≤n-1).Since the 1950s, Carlitz ([5, 6]) and his successors have generalized Euler’s results to q-sequences {1,q,q2,q3,…}. Under Carlitz’s definition, the q-Eulerian numbers An,k(q) are given by
(11)[x]n=∑k=0n-1‍An,k(q)[x+k-1n](n≥1),
where
(12)[x]=1-qx1-q,[xn]=(1-qx)(1-qx-1)⋯(1-qx-n+1)(1-q)(1-q2)⋯(1-qn).
Then the q-Eulerian polynomials An(t,q) are defined as
(13)An(t,q)=∑k=0n-1‍An,ktk(n≥1).
Like the traditional Eulerian numbers, the q-Eulerian numbers An,k(q) have the following recursive formula:
(14)A1,0(q)=1,An,k(q)=0if(k≤0ork≥n),An,k(q)=qn-1-k[k+1]An-1,k(q)+[n-k]An-1,k-1(q)(n≥1).Similarly to the traditional Eulerian numbers, we can also construct a triangular array forq-Eulerian numbers as in Table 2.Table 2
First values ofq-  Eulerian numbers An,k(q).
k =
0
1
2
3
n = 1
1
2
q
1
3
q
3
2
q
2
+
2
q
1
4
q
6
3
q
5
+
5
q
4
+
3
q
3
3
q
3
+
5
q
2
+
3
q
1Definition 4.
Given a permutationπ=p1p2p3…pn of the first n numbers {1,2,3,,…,n}, define functions
(15)majπ=∑pj>pj+1‍j,a(n,k,i)=#{π∣majπ=iandπhaskascents}.In 1974, Carlitz [6] completed his study of his q-Eulerian numbers by giving a combinatorial meaning to his q-Eulerian numbers:
(16)An,k(q)=q((m-k+1)(m-k))/2∑i=0k(n-k-1)‍a(n,n-k,i)qi,
where functions a(n,k,i) are as defined in Definition 4. Interested readers can find more details about the history of Eulerian numbers, Eulerian polynomials, and the corresponding concepts in q-environment from [3].In this paper, instead of studyingq-sequences, we will generalize Euler’s work on Eulerian numbers and Eulerian polynomials to any general arithmetic progression:
(17){a,a+d,a+2d,a+3d,…}.In Section2, we will give a new definition of general Eulerian numbers based on a given arithmetic progression as defined in (17). Under the new definition, some well-known combinatorial properties of traditional Eulerian numbers become special cases of our more general results. In Section 3, we will define general Eulerian polynomials. Then, (2), (3), (4), (5), (6), (7), (9), and (10) become special cases of our more general results.


## 2. General Eulerian Numbers

The traditional Eulerian numbersAn,k, play an important role in the well-known Worpitzky’s identity [7]:
(18)xn=∑k=0n-1‍(x+kn)An,k,n≥1.Before we give a general definition of Eulerian numbers based on a given arithmetic progression (17), we shall mention a property associated with the traditional Eulerian numbers An,k.Proposition 5.
LetAn,k be the traditional Eulerian numbers as defined in Definition 1, then
(19)∑i=1m‍in=∑k=0n-1‍An,k(m+k+1n+1).Proof.
See [8, (4), page 348].Given an arithmetic progression (17), we want to define general Eulerian numbers An,k(a,d) so that the important properties of traditional Eulerian numbers such as the recursive formula (9), the triangular array (Table 1), Worpitzky’s Identity (18), and Proposition 5, and so forth, become special cases of more general results under the new definition.Definition 6.
General Eulerian numbersAn,k(a,d) associated with an arithmetic progression as in (17) are defined as A0,-1=1,An,k=0(k≥nork≤-2) and
(20)An,k(a,d)=(-a+(k+2)d)An-1,k(a,d)+(a+(n-k-1)d)An-1,k-1(a,d)(0≤k≤n-1).Like the traditional Eulerian numbers andq-Eulerian numbers, the first general Eulerian numbers can be presented in the form of a triangular array as in Table 3.Table 3
First values of general Eulerian numbersAn,k(a,d).
k =
−1
0
1
2
3
n = 0
1
1
d
-
a
a
2
(
d
-
a
)
2
-
2
a
2
+
2
a
d
+
d
2
a
2
3
(
d
-
a
)
3
3
a
3
-
6
a
2
d
+
4
d
3
-
3
a
3
+
3
a
2
d
+
3
a
d
2
+
d
3
a
3
4
(
d
-
a
)
4
-
4
a
4
+
12
a
3
d
-
6
a
2
d
2
-
12
a
d
3
+
11
d
4
6
a
4
-
12
a
3
d
-
6
a
2
d
2
+
12
a
d
3
+
11
d
4
-
4
a
4+4a3d+6a2d2+4ad3+d4
a
4We intentionally choosek values to start with -1, because by doing so Table 1 becomes the special case of Table 3 when a=d=1 in the arithmetic progression:
(21){a,a+d,a+2d,a+3d,…}.
In other words, Table 1 corresponds to the sequence of natural numbers:
(22){1,2,3,4,…}.
Therefore when a=d=1, the entries in the first column of Table 3 become zeroes except initially defined A0,-1(a,d)=1.With the new Definition6, we are able to prove the following two properties. Again note that if a=d=1, then the following identity is just the conventional Worpitzky’s identity.Lemma 7 (General Worpitzky’s Identity).
Given an arithmetic progression as in (17),
(23)(a+(i-1)d)n=∑j=-1n-1‍An,j(a,d)(i+jn),i≥1.Proof.
We will prove Lemma7 by induction on n.
(i) Whenn=1, using the values in Table 3,
(24)a+(i-1)d=A1,-1(a,d)(i-11)+A1,0(a,d)(i1).
(ii) Now suppose(25)(a+(i-1)d)n=∑j=-1n-1‍An,j(a,d)(i+jn)then,(a+(i-1)d)n+1=[∑j=-1n-1‍An,j(a,d)(i+jn)](a+(i-1)d)=∑j=-1n-1‍An,j(a,d)[a(i+jn)-(j+2)d(i+jn)+(i+j+1)d(i+jn)]=∑j=-1n-1‍An,j(a,d)[a(i+j+1n+1)-a(i+jn+1)+(n-j-1)d(i+j+1n+1)]+∑j=-1n-1‍An,j(a,d)[(j+2)d(i+jn+1)]=∑j=-1n-1‍An,j(a,d)(a+(n-j-1)d)(i+j+1n+1)+∑j=-1n-1‍An,j(a,d)(-a+(j+2)d)(i+jn+1)=∑j=-1n‍[An,j-1(a,d)(a+(n-j)d)+An,j(a,d)×(-a+(j+2)d)An,j](i+jn+1)=∑j=-1n‍An+1,j(a,d)(i+jn+1).By (20) With Lemma 7, we can prove the following Lemma which is a generalization of Proposition 5.Lemma 8.
Given an arithmetic progression as in (17),
(26)∑i=1m‍(a+(i-1)d)n=∑j=-1n-1‍An,j(a,d)(m+j+1n+1).Proof.
We will prove Lemma8 by induction on m.(i)
Whenm=1, by Lemma 7,
(27)(a+(1-1)d)n=∑j=-1n-1‍An,j(a,d)(1+jn)=∑j=-1n-1‍An,j(a,d)(1+jn)+∑j=-1n-1‍An,j(a,d)(1+jn+1),since(1+jn+1)=0, for j=-1,0,1,…,n-1. Therefore,
(28)[a+(1-1)d]n=∑j=-1n-1‍An,j(a,d)(1+j+1n+1),which finishes the base casem=1.(ii)
Now suppose(29)∑i=1m‍(a+(i-1)d)n=∑j=-1n-1‍An,j(a,d)(m+j+1n+1).(iii)
Then from Table3, Definition 6, and Lemma 7,
(30)∑i=1m+1‍(a+(i-1)d)n=∑j=-1n-1‍An,j(a,d)(m+j+1n+1)+(a+md)n=∑j=-1n-1‍An,j(a,d)[(m+j+1n+1)+(m+j+1n)]=∑j=-1n-1‍An,j(a,d)(m+1+j+1n+1).The general Eulerian numbersAn,k(a,d) can be calculated directly from the following formula, which is a generalization of (10).Lemma 9.
For a given arithmetic progression{a,a+d,a+2d,a+3d,…}, the general Eulerian numbers satisfy
(31)An,k(a,d)=∑i=0k+1‍(-1)i[(k+2-i)d-a]n(n+1i).Proof.
The following proof is given by inductions on bothn and k.
Forn=0,k=-1, A0,-1(a,d)=(-1)0(d-a)0(10)=1.
Forn=1,k=-1, A1,-1(a,d)=(-1)0(d-a)1(20)=d-a.
Forn=1,k=0, A1,0(a,d)=(-1)0(2d-a)1(20)+(-1)1(d-a)1(21)=a.
Now supposeAn-1,k(a,d)=∑i=0k+1‍(-1)i[(k+2-i)d-a]n-1(ni). Then from the recursive formula (20),
(32)An,k(a,d)=[-a+(k+2)d]An-1,k(a,d)+[a+(n-k-1)d]An-1,k-1(a,d)=[-a+(k+2)d]×∑i=0k+1‍(-1)i[(k+2-i)d-a]n-1(ni)+[a+(n-k-1)d]∑i=1k+1‍(-1)i-1×[(k+2-i)d-a]n-1(ni-1)byinduction=[(k+2)d-a]n(n0)+∑i=1k+1‍(-1)i[(k+2-i)d-a]n-1×[(k+2)d(ni)-(n-k-1)d(ni-1)-a(ni)-a(ni-1)];
Note that
(33)(k+2)d(ni)-(n-k-1)d(ni-1)-a(ni)-a(ni-1)=(k+2)d(ni)-(n-k-1)d(ni-1)-a(n+1i)=(k+2)d(ni)+(k+2)d(ni-1)-(n+1)d(ni-1)-a(n+1i)=(k+2)d(n+1i)-id(n+1i)-a(n+1i)=[(k+2-i)d-a](n+1i).
Combine the results above, we have
(34)An,k(a,d)=∑i=0k+1‍(-1)i[(k+2-i)d-a]n(n+1i).


## 3. General Eulerian Polynomials

Definition 10.
We define the general Eulerian polynomials associated to an arithmetic progression as in (17) as
(35)Tn(t,a,d)=∑k=-1n-1‍An,k(a,d)tk+1.Definition10 is a generalization of the traditional Eulerian polynomials as in (6). The following lemma gives the relation between the general Eulerian polynomials and the traditional Eulerian polynomials.Lemma 11.
LetTn(t,a,d) be the general Eulerian polynomials as in Definition 10, T0(t,a,d)=1. Then
(36)Tn(t,a,d)=∑k=-1n-1‍An,k(a,d)tk+1=∑j=0n‍(nj)djAj(t)(at-a)n-j,
where Aj(t),j=0,1,2,…,n are traditional Eulerian polynomials as defined in (4) and (6).Proof.
(i) Whenn=0, T0(t,a,d)=(00)d0A0(t)(at-a)0=1.
(ii) Now suppose(37)Tn(t,a,d)=∑j=0n‍(nj)djAj(t)(at-a)n-j.Then,Tn+1(t,a,d)=∑k=-1n‍An+1,k(a,d)tk+1bydefinition=∑k=-1n‍(a+(n-k)d)An,k-1(a,d)tk+1+∑k=-1n‍(-a+(k+2)d)An,k(a,d)tk+1=∑k=-1n-1‍(a+(n-k-1)d)An,k(a,d)tk+2+∑k=-1n-1‍(-a+(k+2)d)An,k(a,d)tk+1=∑k=-1n-1‍(at-a)An,k(a,d)tk+1+∑k=-1n-1‍d(nt-t+2)An,k(a,d)tk+1+∑k=-1n-1‍d(1-t)kAn,k(a,d)tk+1(38)=(at-a)Tn(t,a,d)+(dnt-dt+2d)Tn(t,a,d)+∑k=-1n-1‍d(1-t)kAn,k(a,d)tk+1.
Note that by definition,Tn(t,a,d)=∑k=-1n-1‍An,k(a,d)tk+1. So Tn′(t,a,d)=∑k=-1n-1‍(k+1)An,k(a,d)tk, which implies
(39)tTn′(t,a,d)=Tn(t,a,d)+∑k=-1n-1‍kAn,k(a,d)tk+1.
On the other hand, from [3, (3.4), page 263], we have
(40)An(t)=[1+(n-1)t]An-1(t)+t(1-t)An-1′(t).
With results as in (39) and (40), we have
(41)(dnt-dt+2d)Tn(t,a,d)+∑k=-1n-1‍d(1-t)kAn,k(a,d)tk+1=(dnt+d)Tn(t,a,d)+d(1-t)tTn′(t,a,d)=(dnt+d)Tn(t,a,d)+d(1-t)t∑j=0n‍dj(nj)×[Aj′(t)(at-a)n-j+a(n-j)Aj(t)(at-a)n-j-1]byinduction=(dnt+d)Tn(t,a,d)-dt(n-j)Tn(t,a,d)+d(1-t)t∑j=0n‍(nj)djAj′n-j=∑j=0n‍(nj)dj+1(at-a)n-j×[(1+jt)Aj(t)+t(1-t)Aj′(t)]=∑j=0n‍(nj)dj+1(at-a)n-jAj+1(t).
Therefore, expression (37) becomes
(42)Tn+1(t,a,d)=∑j=0n‍(nj)dj+1(at-a)n-jAj+1(t)+∑j=0n‍(nj)dj(at-a)n-j+1Aj(t)=∑j=1n+1‍(nj-1)dj(at-a)n+1-jAj(t)+∑j=0n‍(nj)dj(at-a)n-j+1Aj(t)=∑j=0n+1‍(n+1j)djAj(t)(at-a)n+1-j.The following result is a generalization of (7).Lemma 12.
LetTn(t,a,d) be as defined in Lemma 11. Then
(43)Tn(t,u,a,d)=∑n≥0‍Tn(t,a,d)unn!=(t-1)exp(au(t-1))t-exp(du(t-1)).Proof.
From Lemma11(44)Tn(t,u,a,d)=∑n≥0‍Tn(t,a,d)unn!=∑n≥0‍[∑j=0n‍(nj)djAj(t)(at-a)n-j]unn!=∑n≥0‍[∑0≤k≤nk+l=n‍n!k!l!dkAk(t)(at-a)luk·uln!]=(∑k≥0‍Ak(t)(du)kk!)(∑l≥0‍(ua(t-1))ll!)=(t-1)exp(au(t-1))t-exp(du(t-1)).Using the results from Lemma12, we can derive the following lemma, which is a general version of (5).Proposition 13.
Given an arithmetic progression as in (17), let Tn(t,a-d,-d) be the general Eulerian Polynomials associated to the arithmetic progression {a-d,a-2d,a-3d,…}. Then
(45)-Tn(t,a-d,-d)(t-1)n+1=∑j=0∞tj(a+jd)n(n≥0).Proof.
(46)
e
a
u
1
-
t
e
d
u
=
e
a
u
∑
j
=
0
∞
‍
(
t
e
d
u
)
j
=
∑
j
=
0
∞
t
j
e
u
(
a
+
j
d
)
=
∑
j
=
0
∞
t
j
∑
n
=
0
∞
‍
u
n
(
a
+
j
d
)
n
n
!
=
∑
n
=
0
∞
u
n
n
!
(
∑
j
=
0
∞
‍
t
j
(
a
+
j
d
)
n
)
.
On the other hand, by Lemma12,
(47)∑n=0∞‍-Tn(t,a-d,-d)(t-1)n+1unn!=1t-1∑n=0∞‍-Tn(t,a-d,-d)(t-1)nunn!=-1t-1∑n=0∞‍Tn(t,a-d,-d)n!(ut-1)n=-1t-1·(t-1)e(a-d)ut-e-du=-e(a-d)ut-e-du=eau1-tedu.
By comparing the coefficients of un/n!, we have
(48)-Tn(t,a-d,-d)(t-1)n+1=∑j=0∞‍tj(a+jd)n(n≥0).For the finite summation∑i=1m‍ti[a+(i-1)d]n, we have the following property which is a generalization of (2) and (3).Lemma 14.
LetTn be the general Eulerian polynomials as defined in Definition 10:
(49)∑i=1mti[a+(i-1)d]n=∑l=0n‍(nl)tm+1(dm-d)l(t-1)n-l+1Tn-l(t,a,-d)-t2(t-1)n+1Tn(t,a,-d),(50)∑i=1mti[a+(i-1)d]n=tm+1(t-1)n+1Tn(t,a+d(m-1),-d)-t2(t-1)n+1Tn(t,a,-d).Proof.
We will use (2) and (3) to prove expressions (49) and (50), respectively. 							(51)∑i=1mti[a+(i-1)d]n=∑i=1m‍ti[∑j=0n‍(nj)an-j(i-1)jdj]=∑j=0n‍(nj)djan-j[∑i=1m‍ti(i-1)j]=∑j=0n‍(nj)djan-jt[∑i=1m-1‍ijti].
For (49), if we use (2) to evaluate ∑i=1m-1‍ijti, we have
(52)∑i=1m‍ti[a+(i-1)d]n=∑j=0n‍(nj)djan-jt×[∑l=1j‍(-1)j+l(jl)tm(m-1)l(t-1)j-l+1Aj-l(t)+(-1)jtm-t(t-1)j+1Aj(t)∑l=1j‍]=∑j=0n‍(nj)djan-jt×[∑l=0j‍(-1)j+l(jl)tm(m-1)l(t-1)j-l+1Aj-l(t)]+∑j=0n‍(nj)djan-jt(-1)j-t(t-1)j+1Aj(t)=I+II;II=∑j=0n‍(nj)djan-jt(-1)j-t(t-1)j+1Aj(t)=-t2(t-1)n+1∑j=0n‍(nj)(-d)j(a(t-1))n-jAj(t)=-t2(t-1)n+1Tn(t,a,-d).
This gives the second term in (49). 							(53)I=∑j=0n‍(nj)djan-jt×∑l=0j‍(-1)j+l(jl)tm(m-1)l(t-1)j-l+1Aj-l(t)=∑l=0n‍∑j=ln‍(nj)djan-jt(-1)j+l(jl)×tm(m-1)l(t-1)j-l+1Aj-l(t)=∑l=0n‍∑j=ln‍n!j!(n-j)!djan-jt(-1)j+l×j!l!(j-l)!tm(m-1)l(t-1)j-l+1Aj-l(t)=∑l=0n‍∑k=0n-l‍n!(n-k-l)!dk+lan-k-lt(-1)k×1l!k!tm(m-1)l(t-1)k+1Ak(t)k=j-l=∑l=0n‍(m-1)ln!tm+1dll!(n-l)!×∑k=0n-l‍(-d)kan-k-l(n-l)!k!(n-k-l)!(t-1)k+1Ak(t)=∑l=0n‍(nl)(m-1)ltm+1dl(t-1)n-l+1×∑k=0n-l‍(n-lk)(-d)k(at-a)n-k-lAk(t)=∑l=0n‍(nl)tm+1(dm-d)l(t-1)n-l+1Tn-l(t,a,-d),
which gives the first term of (49). So we have proved (49) by using expression (2).
For (50), if we use (3) to evaluate ∑i=1m-1‍ijti, we have
(54)∑i=1m‍ti[a+(i-1)d]n=∑j=0n‍(nj)djan-jt×[-tm∑k=0j‍(jk)(m-1)j-k(1-t)k+1Ak(t)+t(1-t)j+1Aj(t)∑k=0j‍]=-tm+1∑j=0n‍(nj)djan-j∑k=0j‍(jk)(m-1)j-k(1-t)k+1Ak(t)+∑j=0n‍(nj)djan-j(1-t)-jt21-tAj(t)=III+IV;IV=∑j=0n‍(nj)djan-j(1-t)-jt21-tAj(t)=∑j=0n‍(nj)(-d)jan-j(t-1)n-jt2(1-t)(t-1)nAj(t)=-t2(t-1)n+1Tn(t,a,-d),
by Lemma 11. Thus, we have obtained the second part of (50). 							(55)III=-tm+1∑j=0n‍(nj)djan-j×∑k=0j‍(jk)(m-1)j-k(1-t)k+1Ak(t)=-tm+1∑j=0n‍∑k=0j‍n!j!(n-j)!·j!k!(j-k)!×djan-j(m-1)j-k(1-t)k+1Ak(t)=-tm+1∑k=0n‍n!k!(1-t)k+1Ak(t)×∑j=kn‍1(n-j)!(j-k)!(m-1)j-kdjan-j=-tm+1∑k=0n‍n!k!(1-t)k+1Ak(t)×∑l=0n-k‍1l!(n-k-l)!(m-1)ldl+kan-l-kl=j-k=-tm+1∑k=0n‍(nk)dk(1-t)k+1Ak(t)(a+d(m-1))n-k=tm+1(t-1)n+1∑k=0n‍(nk)(-d)k(t-1)n-k×Ak(t)(a+d(m-1))n-k=tm+1(t-1)n+1Tn(t,a+d(m-1),-d),
which gives the first term of (50).



---

*Source: 629132-2013-01-31.xml*