|
%I #70 Mar 02 2021 09:56:19
%S 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,
%T 4400,3708,720,0,1,240,5610,32120,58140,33984,5040,0,1,494,19950,
%U 195800,644020,785304,341136,40320,0,1,1004,67260,1062500,5765500,12440064,11026296,3733920,362880
%N 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.
%C 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.
%C Also the number of Riordan trapezoidal words of length n with k distinct letters (see Riordan 1976, p. 9).
%C Also the number of rooted plane trees on n + 1 vertices with k leaves (see Janson 2008, p. 543).
%C 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.)
%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed. Addison-Wesley, Reading, MA, 1994, p. 270.
%H J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, <a href="https://doi.org/10.37236/4814">Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers</a>, Electronic Journal of Combinatorics 22(3), 2015.
%H Brian Drake, <a href="http://people.brandeis.edu/~gessel/homepage/students/drakethesis.pdf">An inversion theorem for labeled trees and some limits of areas under lattice paths (Example 1.10.1)</a>, Thesis, Brandeis Univ., Aug. 2008, p. 58.
%H Sergi Elizalde, <a href="https://arxiv.org/abs/2002.00985">Descents on quasi-Stirling permutations</a>, arXiv:2002.00985 [math.CO], 2020.
%H I. Gessel and R. P. Stanley, <a href="https://doi.org/10.1016/0097-3165(78)90042-0">Stirling polynomials</a>, J. Combin. Theory, A 24, 24-33, 1978.
%H Svante Janson, <a href="https://hal.inria.fr/hal-01194667">Plane recursive trees, Stirling permutations and an urn model</a>, Fifth Colloquium on Mathematics and Computer Science, 541-547, Discrete Math. Theor. Comput. Sci. Proc., AI, 2008.
%H Peter Luschny, <a href="http://luschny.de/math/oeis/A340556.html">A companion to A340556</a>, A SageMath-Jupyter notebook, Feb. 2021.
%H Peter Luschny, <a href="https://mathoverflow.net/q/384146">How are the Eulerian numbers of the first-order related to the Eulerian numbers of the second-order?</a>, MathOverflow, Feb. 2021.
%H Andrew Elvey Price and Alan D. Sokal, <a href="https://arxiv.org/abs/2001.01468">Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials</a>, arXiv:2001.01468 [math.CO], 2020.
%H John Riordan, <a href="https://doi.org/10.1007/BF02392410">The blossoming of Schröder's fourth problem</a>, Acta Math., 137 (1976), 1-16.
%H G. Rzadkowski, M. Urlinska, <a href="http://arxiv.org/abs/1612.06635">A Generalization of the Eulerian Numbers</a>, arXiv:1612.06635 [math.CO], 2016
%F 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.
%F 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).
%F E2(n, k) = Sum_{j=0..k}(-1)^(k-j)*binomial(2*n + 1, k - j)*Stirling2(n + j, j).
%F Stirling1(x, x - n) = (-1)^n*Sum_{k=0..n} E2(n, k)*binomial(x + k - 1, 2*n).
%F Stirling2(x, x - n) = Sum_{k=0..n} E2(n, k)*binomial(x + n - k, 2*n).
%F E2poly(n, x) = Sum_{k=0..n} E2(n, k)*x^k, as row polynomials.
%F 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.
%F E2poly(n, x) = (1 - x)^(2*n + 1)*Sum_{k=0..n}(k^(n + k)/k!*(x*exp(-x))^k.
%F W(n, k) = [x^k] (1+x)^n*E2poly(n, x/(1 + x)) are the Ward numbers A269939.
%F 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.
%F W(n, k) = Sum_{j=0..k} E2(n, j)*binomial(n - j, n - k).
%F E2(n, k) = Sum_{j=0..k} (-1)^(k-j)*W(n, j)*binomial(n - j, k - j).
%F The compositional inverse with respect to x of x - t*(exp(x) - 1) (see B. Drake):
%F T(n, k) = [t^k](n+1)!*(1-t)^(2*n+1)*[x^(n+1)] InverseSeries(x - t*(exp(x)-1), x).
%F 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).
%F 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.
%F 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).
%F E2(n, k) = Sum_{j=0..k} (-1)^(k-j)*AS2(n + j, j)*binomial(n - j, k - j).
%e Triangle starts:
%e [0] 1;
%e [1] 0, 1;
%e [2] 0, 1, 2;
%e [3] 0, 1, 8, 6;
%e [4] 0, 1, 22, 58, 24;
%e [5] 0, 1, 52, 328, 444, 120;
%e [6] 0, 1, 114, 1452, 4400, 3708, 720;
%e [7] 0, 1, 240, 5610, 32120, 58140, 33984, 5040;
%e [8] 0, 1, 494, 19950, 195800, 644020, 785304, 341136, 40320;
%e [9] 0, 1, 1004, 67260, 1062500, 5765500, 12440064, 11026296, 3733920, 362880.
%e .
%e 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.
%e .
%e Stirling permutations of order 3 with exactly k descents: (When counting the descents one may assume an invisible '0' appended to the permutations.)
%e T[3, k=0]:
%e T[3, k=1]: 112233;
%e T[3, k=2]: 331122; 223311; 221133; 133122; 122331; 122133; 113322; 112332;
%e T[3, k=3]: 332211; 331221; 233211; 221331; 133221; 123321.
%p # Using the recurrence:
%p E2 := proc(n, k) option remember;
%p if k = 0 and n = 0 then return 1 fi; if n < 0 then return 0 fi;
%p 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);
%p # Using the row generating function:
%p E2egf := n -> (1-x)^(2*n+1)*add(k^(n+k)/k!*(x*exp(-x))^k, k=0..n);
%p T := (n, k) -> coeftayl(E2egf(n), x=0, k): seq(print(seq(T(n, j),j=0..n)), n=0..7);
%p # Using the built-in function:
%p E2 := (n, k) -> `if`(k=0, k^n, combinat:-eulerian2(n, k-1)):
%p # Using the compositional inverse (series reversion):
%p E2triangle := proc(N) local r, s, C; Order := N + 2;
%p s := solve(y = series(x - t*(exp(x) - 1), x), x):
%p r := n -> -n!*(t - 1)^(2*n - 1)*coeff(s, y, n); C := [seq(expand(r(n)), n = 1..N)];
%p seq(print(seq(coeff(C[n+1], t, k), k = 0..n)), n = 0..N-1) end: E2triangle(10);
%t 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
%t (* Via row polynomials: *)
%t E2poly[n_] := If[n == 0, 1,
%t Expand[Simplify[x (x - 1)^(2 n) D[((1 - x)^(1 - 2 n) E2poly[n - 1]), x]]]];
%t Table[CoefficientList[E2poly[n], x], {n, 0, 9}] // Flatten
%t (* Series reversion *)
%t Revert[gf_, len_] := Module[{S = InverseSeries[Series[gf, {x, 0, len + 1}], x]},
%t Table[CoefficientList[(n + 1)! (1 - t)^(2 n + 1) Coefficient[S, x, n + 1], t],
%t {n, 0, len}] // Flatten]; Revert[x + t - t Exp[x], 6]
%o (PARI)
%o E2poly(n) = if(n == 0, 1, x*(x-1)^(2*n)*deriv((1-x)^(1-2*n)*E2poly(n-1)));
%o { for(n = 0, 9, print(Vecrev(E2poly(n)))) }
%o (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
%o (SageMath) # See link to notebook.
%Y 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.
%Y Row reversed: A163936 (with offset = 0).
%Y 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).
%Y Diagonals: A000142, A002538, A002539, A112008, A112485.
%Y Columns: A000007, A000012, A005803, A004301, A006260.
%Y Cf. A008299, A137375, A008306, A106828, A269939, A278075, A331998.
%K nonn,tabl
%O 0,6
%A _Peter Luschny_, Feb 05 2021
|
