login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A340556 E2(n, k), the second-order Eulerian numbers with E2(0, k) = δ_{0, k}. Triangle read by rows, E2(n, k) for 0 <= k <= n. 14
1, 0, 1, 0, 1, 2, 0, 1, 8, 6, 0, 1, 22, 58, 24, 0, 1, 52, 328, 444, 120, 0, 1, 114, 1452, 4400, 3708, 720, 0, 1, 240, 5610, 32120, 58140, 33984, 5040, 0, 1, 494, 19950, 195800, 644020, 785304, 341136, 40320, 0, 1, 1004, 67260, 1062500, 5765500, 12440064, 11026296, 3733920, 362880 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

The second-order Eulerian number E2(n, k) is the number of Stirling permutations of order n with exactly k descents; here the last index is defined to be a descent. More formally, let Q_n denote the set of permutations of the multiset {1,1,2,2, ..., n,n} in which, for all j, all entries between two occurrences of j are larger than j, then E2(n, k) = card({s in Q_n with des(s) = k}), where des(s) = card({j: s(j) > s(j+1)}) is the number of descents of s.

Also the number of Riordan trapezoidal words of length n with k distinct letters (see Riordan 1976, p. 9).

Also the number of rooted plane trees on n + 1 vertices with k leaves (see Janson 2008, p. 543).

Let b(n) = (1/2)*Sum_{k=0..n-1} (-1)^k*E2(n-1, k+1) / C(2*n-1, k+1). Apparently b(n) = Bernoulli(n, 1) = -n*Zeta(1 - n) = Integral_{x=0..1}F_n(x) for n >= 1. Here F_n(x) are the signed Fubini polynomials (A278075). (See Rzadkowski and Urlinska, example 4.)

REFERENCES

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed. Addison-Wesley, Reading, MA, 1994, p. 270.

LINKS

Table of n, a(n) for n=0..54.

J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers, Electronic Journal of Combinatorics 22(3), 2015.

Brian Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.10.1), Thesis, Brandeis Univ., Aug. 2008, p. 58.

Sergi Elizalde, Descents on quasi-Stirling permutations, arXiv:2002.00985 [math.CO], 2020.

I. Gessel and R. P. Stanley, Stirling polynomials, J. Combin. Theory, A 24, 24-33, 1978.

Svante Janson, Plane recursive trees, Stirling permutations and an urn model, Fifth Colloquium on Mathematics and Computer Science, 541-547, Discrete Math. Theor. Comput. Sci. Proc., AI, 2008.

Peter Luschny, A companion to A340556, A SageMath-Jupyter notebook, Feb. 2021.

Peter Luschny, How are the Eulerian numbers of the first-order related to the Eulerian numbers of the second-order?, MathOverflow, Feb. 2021.

Andrew Elvey Price and Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.

John Riordan, The blossoming of Schröder's fourth problem, Acta Math., 137 (1976), 1-16.

G. Rzadkowski, M. Urlinska, A Generalization of the Eulerian Numbers, arXiv:1612.06635 [math.CO], 2016

FORMULA

E2(n, k) = E2(n-1, k)*k + E2(n-1, k-1)*(2*n - k) for n > 0 and 0 <= k <= n, and E2(0, 0) = 1; in all other cases E(n, k) = 0.

E2(n, k) = Sum_{j=0..n-k}(-1)^(n-j)*binomial(2*n+1, j)*Stirling1(2*n-k-j+1, n-k-j+1).

E2(n, k) = Sum_{j=0..k}(-1)^(k-j)*binomial(2*n + 1, k - j)*Stirling2(n + j, j).

Stirling1(x, x - n) = (-1)^n*Sum_{k=0..n} E2(n, k)*binomial(x + k - 1, 2*n).

Stirling2(x, x - n) = Sum_{k=0..n} E2(n, k)*binomial(x + n - k, 2*n).

E2poly(n, x) = Sum_{k=0..n} E2(n, k)*x^k, as row polynomials.

E2poly(n, x) = x*(x-1)^(2*n)*d_{x}((1-x)^(1-2*n)*E2poly(n-1)) for n>=1 and E2poly(0)=1.

E2poly(n, x) = (1 - x)^(2*n + 1)*Sum_{k=0..n}(k^(n + k)/k!*(x*exp(-x))^k.

W(n, k) = [x^k] (1+x)^n*E2poly(n, x/(1 + x)) are the Ward numbers A269939.

E2(n, k) = [x^k] (1-x)^n*Wpoly(n, x/(1 - x)); Wpoly(n, x) = Sum_{k=0..n}W(n, k)*x^k.

W(n, k) = Sum_{j=0..k} E2(n, j)*binomial(n - j, n - k).

E2(n, k) = Sum_{j=0..k} (-1)^(k-j)*W(n, j)*binomial(n - j, k - j).

The compositional inverse with respect to x of x - t*(exp(x) - 1) (see B. Drake):

T(n, k) = [t^k](n+1)!*(1-t)^(2*n+1)*[x^(n+1)] InverseSeries(x - t*(exp(x)-1), x).

AS1(n, k) = Sum_{j=0..n-k} binomial(j, n-2*k)*E2(n-k, j+1), where AS1(n, k) are the associated Stirling numbers of the first kind (A008306, A106828).

E2(n, k) = Sum_{j=0..n-k+1} (-1)^(n-k-j+1)*AS1(n+j, j)*binomial(n-j, n-k-j+1), for n >= 1.

AS2(n, k) = Sum_{j=0..n-k} binomial(j, n-2*k)*E2(n-k, n-k-j) for n >=1, where AS2(n, k) are the associated Stirling numbers of the second kind (A008299, A137375).

E2(n, k) = Sum_{j=0..k} (-1)^(k-j)*AS2(n + j, j)*binomial(n - j, k - j).

EXAMPLE

Triangle starts:

[0] 1;

[1] 0, 1;

[2] 0, 1, 2;

[3] 0, 1, 8,    6;

[4] 0, 1, 22,   58,    24;

[5] 0, 1, 52,   328,   444,     120;

[6] 0, 1, 114,  1452,  4400,    3708,    720;

[7] 0, 1, 240,  5610,  32120,   58140,   33984,    5040;

[8] 0, 1, 494,  19950, 195800,  644020,  785304,   341136,   40320;

[9] 0, 1, 1004, 67260, 1062500, 5765500, 12440064, 11026296, 3733920, 362880.

.

To illustrate the generating function for row 3: The expansion of (1 - x)^7*(x*exp(-x) + 16*x^2*exp(-x)^2 + (243*x^3*exp(-x)^3)/2) gives the polynomial x + 8*x^2 + 6*x^3. The coefficients of this polynomial give row 3.

.

Stirling permutations of order 3 with exactly k descents: (When counting the descents one may assume an invisible '0' appended to the permutations.)

T[3, k=0]:

T[3, k=1]: 112233;

T[3, k=2]: 331122; 223311; 221133; 133122; 122331; 122133; 113322; 112332;

T[3, k=3]: 332211; 331221; 233211; 221331; 133221; 123321.

MAPLE

# Using the recurrence:

E2 := proc(n, k) option remember;

if k = 0 and n = 0 then return 1 fi; if n < 0 then return 0 fi;

E2(n-1, k)*k + E2(n-1, k-1)*(2*n - k) end: seq(seq(E2(n, k), k = 0..n), n = 0..9);

# Using the row generating function:

E2egf := n -> (1-x)^(2*n+1)*add(k^(n+k)/k!*(x*exp(-x))^k, k=0..n);

T := (n, k) -> coeftayl(E2egf(n), x=0, k): seq(print(seq(T(n, j), j=0..n)), n=0..7);

# Using the built-in function:

E2 := (n, k) -> `if`(k=0, k^n, combinat:-eulerian2(n, k-1)):

# Using the compositional inverse (series reversion):

E2triangle := proc(N) local r, s, C; Order := N + 2;

s := solve(y = series(x - t*(exp(x) - 1), x), x):

r := n -> -n!*(t - 1)^(2*n - 1)*coeff(s, y, n); C := [seq(expand(r(n)), n = 1..N)];

seq(print(seq(coeff(C[n+1], t, k), k = 0..n)), n = 0..N-1) end: E2triangle(10);

MATHEMATICA

T[n_, k_] := T[n, k] = If[k == 0, Boole[n == 0], If[n < 0, 0, k T[n - 1, k] + (2 n - k) T[n - 1, k - 1]]]; Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten

(* Via row polynomials: *)

E2poly[n_] := If[n == 0, 1,

  Expand[Simplify[x (x - 1)^(2 n) D[((1 - x)^(1 - 2 n) E2poly[n - 1]), x]]]];

Table[CoefficientList[E2poly[n], x], {n, 0, 9}] // Flatten

(* Series reversion *)

Revert[gf_, len_] := Module[{S = InverseSeries[Series[gf, {x, 0, len + 1}], x]},

Table[CoefficientList[(n + 1)! (1 - t)^(2 n + 1) Coefficient[S, x, n + 1], t],

{n, 0, len}] // Flatten]; Revert[x + t - t Exp[x], 6]

PROG

(PARI)

E2poly(n) = if(n == 0, 1, x*(x-1)^(2*n)*deriv((1-x)^(1-2*n)*E2poly(n-1)));

{ for(n = 0, 9, print(Vecrev(E2poly(n)))) }

(PARI) T(n, k) = sum(j=0, n-k, (-1)^(n-j)*binomial(2*n+1, j)*stirling(2*n-k-j+1, n-k-j+1, 1)); \\ Michel Marcus, Feb 11 2021

(SageMath) # See link to notebook.

CROSSREFS

Indexing the second-order Eulerian numbers comes in three flavors: A008517 (following Riordan and Comtet), A201637 (following Graham, Knuth, and Patashnik) and this indexing, extending the definition of Gessel and Stanley. (A008517 is the main entry of the numbers.) The corresponding triangles of the first-order Eulerian numbers are A008292, A173018, and A123125.

Row reversed: A163936 (with offset = 0).

Values: E2poly(n, 1) = A001147(n), E2poly(n, -1) ~ -A001662(n+1), E2poly(n, 2) = A112487(n), 2^n*E2poly(n, 1/2) = A000311(n+1), 2^n*E2poly(n, -1/2) = A341106(n).

Diagonals: A000142, A002538, A002539, A112008, A112485.

Columns: A000007, A000012, A005803, A004301, A006260.

Cf. A008299, A137375, A008306, A106828, A269939, A278075, A331998.

Sequence in context: A278881 A335095 A337444 * A201637 A055141 A055140

Adjacent sequences:  A340553 A340554 A340555 * A340557 A340558 A340559

KEYWORD

nonn,tabl

AUTHOR

Peter Luschny, Feb 05 2021

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 10 09:20 EDT 2021. Contains 342845 sequences. (Running on oeis4.)