Eulerian number

In combinatorics, the Eulerian number

A

(

n

,

k

)

{\textstyle A(n,k)}

is the number of permutations of the numbers 1 to

n

{\textstyle n}

in which exactly

k

{\textstyle k}

elements are greater than the previous element (permutations with

k

{\textstyle k}

"ascents").

Leonhard Euler investigated them and associated polynomials in his 1755 book Institutiones calculi differentialis.

Other notations for

A

(

n

,

k

)

{\textstyle A(n,k)}

are

E

(

n

,

k

)

{\textstyle E(n,k)}

and

⟨

n

k

⟩

{\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }

.

Definition

The Eulerian polynomials

A

n

(

t

)

{\displaystyle A_{n}(t)}

are defined by the exponential generating function

∑

n

=

0

∞

A

n

(

t

)

x

n

n

!

=

t

−

1

t

−

e

(

t

−

1

)

x

=

(

1

−

e

(

t

−

1

)

x

−

1

t

−

1

)

−

1

.

{\displaystyle \sum _{n=0}^{\infty }A_{n}(t)\,{\frac {x^{n}}{n!}}={\frac {t-1}{t-e^{(t-1)\,x}}}=\left(1-{\frac {e^{(t-1)x}-1}{t-1}}\right)^{-1}.}

The Eulerian numbers

A

(

n

,

k

)

{\displaystyle A(n,k)}

may also be defined as the coefficients of the Eulerian polynomials:

A

n

(

t

)

=

∑

k

=

0

n

A

(

n

,

k

)

t

k

.

{\displaystyle A_{n}(t)=\sum _{k=0}^{n}A(n,k)\,t^{k}.}

An explicit formula for

A

(

n

,

k

)

{\textstyle A(n,k)}

is

A

(

n

,

k

)

=

∑

i

=

0

k

(

−

1

)

i

(

n

+

1

i

)

(

k

+

1

−

i

)

n

.

{\displaystyle A(n,k)=\sum _{i=0}^{k}(-1)^{i}{\binom {n+1}{i}}(k+1-i)^{n}.}

Basic properties

For fixed

n

{\textstyle n}

there is a single permutation which has 0 ascents:

(

n

,

n

−

1

,

n

−

2

,

…

,

1

)

{\textstyle (n,n-1,n-2,\ldots ,1)}

. Indeed, as

(

n

0

)

=

1

{\displaystyle {\tbinom {n}{0}}=1}

for all

n

{\displaystyle n}

,

A

(

n

,

0

)

=

1

{\textstyle A(n,0)=1}

. This formally includes the empty collection of numbers,

n

=

0

{\textstyle n=0}

.