Eulerian Number

Author

Eric W. Weisstein
July 29, 2022

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/EulerianNumber.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/EulerianNumber.html.

©2022 Wolfram Research, Inc. except for portions noted otherwise

Usage

WFR

https://resources.wolframcloud.com/FunctionRepository/resources/EulerianNumber

ResourceFunction["EulerianNumber"][10,5]

Table[ResourceFunction["EulerianNumber"][n,k],{n,0,10},{k,0,n}]//Column

Combinatorica

<<Combinatorica`

?Eulerian

Notation

Eulerian[n,k]//TraditionalForm

Table[Eulerian[n,k],{n,0,10},{k,0,n}]//Column

Enumeration

Reverse/@Table[CoefficientList[Numerator[PolyLog[-n,r]],r],{n,5}]//Column

Definition

Graham et al., number of permutations of {1,…,n} having k ascents

Table[Count[Ascents/@Permutations[n],#]&/@Range[0,n],{n,0,7}]//Column

Ascents[p_]:=Count[Partition[p,2,1],_?(Greater@@#&)]

n==2

Ascents/@Permutations[2]

Count[%,#]&/@Range[0,1]

Table[Eulerian[2,k],{k,0,1}]

n==3

Greater@@@Partition[{1,2,4,3},2,1]

Ascents/@Permutations[3]

Count[%,#]&/@Range[0,3]

Table[Eulerian[3,k],{k,0,3}]

Sums

(∑_(j=0)^(k+1))(((-1))^j) (Binomial[n+1, j]) (((-j+k+1))^n)==⟨({{n}, {k}})⟩

v4.2

Sum[(-1)^j Binomial[n+1,j](k+1-j)^n,{j,0,k+1}]

v5.0

Sum[(-1)^j Binomial[n+1,j](k+1-j)^n,{j,0,k+1}]

v5.2

Sum[(-1)^j Binomial[n+1,j](k+1-j)^n,{j,0,k+1}]

v6

Sum[(-1)^j Binomial[n+1,j](k+1-j)^n,{j,0,k+1}]

V7

Sum[(-1)^j Binomial[n+1,j](k+1-j)^n,{j,0,k+1}]

Table

Table[%,{n,10},{k,10}]

Table[Eulerian[n,k],{n,10},{k,10}]

(∑_(k=0)^n)⟨({{n}, {k}})⟩==n!

Table[n!,{n,10}]

v4.2

Sum[Eulerian[n,k],{k,0,n}]

Table[%,{n,10}]

v5.2

Sum[Eulerian[n,k],{k,0,n}]

v7

Sum[Eulerian[n,k],{k,0,n}]

(∑_k^n)(Binomial[k+x-1, n]) ⟨({{n}, {k}})⟩==(x^n)

Worpitzky's Identity

Expand[Table[Sum[Eulerian[n,k]Binomial[x+k-1,n],{k,n}],{n,5}]]

V7

Sum[Eulerian[n,k]Binomial[x+k-1,n],{k,n}]

(∑_(n=0)^∞)(∑_(k=0)^∞)(((z^k) (x^n))/(k! n!)) ⟨({{n}, {k}})⟩==(((z-1) exp(x))/(z exp(x)-exp(x z)))

Sum[((z^k)/(k!))((x^n)/(n!))Eulerian[n,k],{k,0,∞},{n,0,∞}]

(1/(((1-r))^(n+1)))(∑_(i=0)^(n-1))(r^(n-i)) ⟨({{n}, {i}})⟩==(PolyLog[-n, r])

Table[{
PolyLog[-n,r],
Sum[Eulerian[n,i]r^(n-i),{i,0,n-1}]/(1-r)^(n+1)
},{n,6}]

Subtract@@@%

Sum[Eulerian[n,i]r^(n-i),{i,0,n-1}]/(1-r)^(n+1)

Special Cases

k==1

FullSimplify[With[{k=1},Sum[(-1)^j Binomial[n+1,j](k+1-j)^n,{j,0,k+1}]],n>0]

Table[Eulerian[n,1],{n,10}]

k==2

FullSimplify[With[{k=2},Sum[(-1)^j Binomial[n+1,j](k+1-j)^n,{j,0,k+1}]],n>0]

Table[Eulerian[n,2],{n,10}]

k==3

Factor/@FullSimplify[With[{k=3},Sum[(-1)^j Binomial[n+1,j](k+1-j)^n,{j,0,k+1}]],n>0]

Table[Eulerian[n,3],{n,10}]

Recurrence

A[n_,1]:=1
A[n_,n_]:=1
A[n_,k_]:=(n-k+1)A[n-1,k-1]+k A[n-1,k]

TableForm[Table[A[n,k],{n,6},{k,n}],TableAlignments->Right]

v5.0

RSolve[{A[n,k]==(n-k+1)A[n-1,k-1]+k A[n-1,k],A[n,n]==1,A[n,1]==1},A[n,k],{n,k}]

v5.2

RSolve[{A[n,k]==(n-k+1)A[n-1,k-1]+k A[n-1,k],A[n,n]==1,A[n,1]==1},A[n,k],{n,k}]

Generating Function

GF

FunctionExpand[(((((1-x))^(n+1))PolyLog[-n,x])/x),n∈Integers&&n>0]

TimeConstrained[SeriesCoefficient[(((((1-x))^(n+1))PolyLog[-n,x])/x),{x,0,k}],300]//Timing

Table[(((1-x))^(1+n)) PolyLog[-n,x],{n,4}]//Column

EulerianNumber[n_,k_]:=Module[{x},SeriesCoefficient[(((1-x))^(n+1))PolyLog[-n,x],{x,0,k+1}]]

Table[EulerianNumber[n,k],{n,0,10},{k,0,n}]//Column

CoefficientList[#,x]&/@Table[(1-x)^(n+1)*PolyLog[-n,x]/x,{n,6}]//Column

GF2

Series[(1/(1+(1-Exp[x t])/t)),{t,0,2},{x,0,2}]

SeriesCoefficient[(1/(1+(1-Exp[x t])/t)),{t,0,n},{x,0,k}]

EGF

s1=Sum[(((z^k)(x^n))/(k!n!))Eulerian[n,k],{k,0,6},{n,0,6}]

s2=Series[((Exp[x](z-1))/(z Exp[x]-Exp[z x])),{x,0,7},{z,0,7}]//Normal//Expand

s1-s2

SeriesCoefficient[((Exp[x](z-1))/(z Exp[x]-Exp[z x])),{x,0,n},{z,0,k}]

SeriesCoefficient[((Exp[x](z-1))/(z Exp[x]-Exp[z x])),{z,0,k}]

SeriesCoefficient[((Exp[x](z-1))/(z Exp[x]-Exp[z x])),{x,0,n}]

EulerianNumber[n_,k_]:=n!k!Coefficient[Series[((Exp[z x]-Exp[x])/(z Exp[x]-Exp[z x])),{x,0,n},{z,0,k}],(x^n)(z^k)]

Table[EulerianNumber[n,k],{n,10},{k,0,n}]//Column