cp's OEIS Frontend

A112493 Triangle read by rows, T(n, k) = Sum_{j=0..n} C(n-j, n-k)*E2(n, j), where E2 are the second-order Eulerian numbers A201637, for n >= 0 and 0 <= k <= n.

%I A112493 #70 Apr 29 2025 18:57:13
%S A112493 1,1,1,1,4,3,1,11,25,15,1,26,130,210,105,1,57,546,1750,2205,945,1,120,
%T A112493 2037,11368,26775,27720,10395,1,247,7071,63805,247555,460845,405405,
%U A112493 135135,1,502,23436,325930,1939630,5735730,8828820,6756750,2027025,1
%N A112493 Triangle read by rows, T(n, k) = Sum_{j=0..n} C(n-j, n-k)*E2(n, j), where E2 are the second-order Eulerian numbers A201637, for n >= 0 and 0 <= k <= n.
%C A112493 Previous name was: Coefficient triangle of polynomials used for e.g.f.s of Stirling2 diagonals.
%C A112493 For the o.g.f. of diagonal k of the Stirling2 triangle one has a similar result. See A008517 (second-order Eulerian triangle).
%C A112493 A(m,x), the o.g.f. for column m, satisfies the recurrence A(m,x) = x*(x*(d/dx)A(m-1,x) + m*A(m-1,x))/(1-(m+1)*x), for m >= 1 and A(0,x) = 1/(1-x).
%C A112493 The e.g.f. for the sequence in column k+1, k >= 0, of A008278, i.e., for the diagonal k >= 0 of the Stirling2 triangle A048993, is exp(x)*Sum_{m=0..k} a(k,m)*(x^(m+k))/(m+k)!.
%C A112493 It appears that the triangles in this sequence and A124324 have identical columns, except for shifts. - _Jörgen Backelin_, Jun 20 2022
%C A112493 A refined version of this triangle is given in A356145, which contains a link providing the precise relationship between A124324 and this entry, confirming Jörgen Backelin's observation above. - _Tom Copeland_, Sep 24 2022
%H A112493 F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of Increasing Trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
%H A112493 D. Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions.</a> arXiv:math/0501052v2 [math.CA], 2005.
%H A112493 Wolfdieter Lang, <a href="/A112493/a112493_1.txt">First ten rows.</a>
%H A112493 MathOverflow, <a href="https://mathoverflow.net/a/490326/231922">Recursion for row polynomials of A112493</a>, (2025).
%H A112493 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.
%F A112493 a(k, m) = 0 if k < m, a(k, -1):=0, a(0, 0)=1, a(k, m)=(m+1)*a(k-1, m) + (k+m-1)*a(k-1, m-1) else.
%F A112493 From _Peter Bala_, Sep 30 2011: (Start)
%F A112493 E.g.f.: A(x,t) = -1-((1+t)/t)*LambertW(-(t/(1+t))*exp((x-t)/(1+t))) = x + (1+t)*x^2/2! + (1+4*t+3*t^2)*x^3/3! + .... A(x,t) is the inverse function of (1+t)*log(1+x)-t*x.
%F A112493 A(x,t) satisfies the partial differential equation (1-x*t)*dA/dx = 1 + A + t*(1+t)*dA/dt. It follows that the row generating polynomials R(n,t) satisfy the recurrence R(n+1,t) =(n*t+1)*R(n,t) + t*(1+t)*dR(n,t)/dt. Cf. A054589 and A075856. The polynomials t/(1+t)*R(n,t) are the row polynomials of A134991.
%F A112493 The generating function A(x,t) satisfies the autonomous differential equation dA/dx = (1+A)/(1-t*A). Applying [Bergeron et al., Theorem 1] gives a combinatorial interpretation for the row generating polynomials R(n,t): R(n,t) counts plane increasing trees on n+1 vertices where the non-leaf vertices of outdegree k come in t^(k-1)*(1+t) colors. An example is given below. Cf. A006351, which corresponds to the case t = 1. Applying [Dominici, Theorem 4.1] gives the following method for calculating the row polynomials R(n,t): Let f(x) = (1+x)/(1-x*t). Then R(n,t) = (f(x)*d/dx)^n(f(x)) evaluated at x = 0. (End)
%F A112493 Sum_{j=0..n} T(n-j,j) = A000110(n). - _Alois P. Heinz_, Jun 20 2022
%F A112493 From _Mikhail Kurkov_, Apr 01 2025: (Start)
%F A112493 E.g.f.: B(y) = -w/(x*(1+w)) where w = LambertW(-x/(1+x)*exp((y-x)/(1+x))) satisfies the first-order ordinary differential equation (1+x)*B'(y) = B(y)*(1+x*B(y))^2, hence row polynomials are P(n,x) = P(n-1,x) + x*Sum_{j=0..n-1} binomial(n, j)*P(j,x)*P(n-j-1,x) for n > 0 with P(0,x) = 1 (see MathOverflow link).
%F A112493 Conjecture: row polynomials are P(n,x) = Sum_{i=0..n} Sum_{j=0..i} Sum_{k=0..j} (n+i)!*Stirling1(n+j-k,j-k)*x^k*(x+1)^(j-k)*(-1)^(j+k)/((n+j-k)!*(i-j)!*k!). (End)
%F A112493 Conjecture: g.f. satisfies 1/(1 - x - x*y/(1 - 2*x - 2*x*y/(1 - 3*x - 3*x*y/(1 - 4*x - 4*x*y/(1 - 5*x - 5*x*y/(1 - ...)))))) (see A383019 for conjectures about combinatorial interpretation and algorithm for efficient computing). - _Mikhail Kurkov_, Apr 21 2025
%e A112493 Triangle starts:
%e A112493   [1]
%e A112493   [1, 1]
%e A112493   [1, 4,  3]
%e A112493   [1, 11, 25,  15]
%e A112493   [1, 26, 130, 210,  105]
%e A112493   [1, 57, 546, 1750, 2205, 945]
%e A112493   ...
%e A112493 The e.g.f. of [0,0,1,7,25,65,...], the k=3 column of A008278, but with offset n=0, is exp(x)*(1*(x^2)/2! + 4*(x^3)/3! + 3*(x^4)/4!).
%e A112493 Third row [1,4,3]: There are three plane increasing trees on 3 vertices. The number of colors are shown to the right of a vertex.
%e A112493 ...................................................
%e A112493 ....1o.(1+t)...........1o.t*(1+t).....1o.t*(1+t)...
%e A112493 ....|................. /.\............/.\..........
%e A112493 ....|................ /...\........../...\.........
%e A112493 ....2o.(1+t)........2o.....3o......3o....2o........
%e A112493 ....|..............................................
%e A112493 ....|..............................................
%e A112493 ....3o.............................................
%e A112493 ...................................................
%e A112493 The total number of trees is (1+t)^2 + t*(1+t) + t*(1+t) = 1+4*t+3*t^2 = R(2,t).
%p A112493 T := (n, k) -> add(combinat:-eulerian2(n, j)*binomial(n-j, n-k), j=0..n):
%p A112493 seq(seq(T(n, k), k=0..n), n=0..9); # _Peter Luschny_, Apr 11 2016
%t A112493 max = 11; f[x_, t_] := -1 - (1 + t)/t*ProductLog[-t/(1 + t)*Exp[(x - t)/(1 + t)]]; coes = CoefficientList[ Series[f[x, t], {x, 0, max}, {t, 0, max}], {x, t}]* Range[0, max]!; Table[coes[[n, k]], {n, 0, max}, {k, 1, n - 1}] // Flatten (* _Jean-François Alcover_, Nov 22 2012, from e.g.f. *)
%Y A112493 Row sums give A006351(k+1), k>=0.
%Y A112493 The column sequences start with A000012 (powers of 1), A000295 (Eulerian numbers), A112495, A112496, A112497.
%Y A112493 Cf. A008278, A008517, A048993, A054589, A075856, A134991, A201637, A124324.
%Y A112493 Antidiagonal sums give A000110.
%Y A112493 Cf. A356145.
%K A112493 nonn,easy,tabl
%O A112493 0,5
%A A112493 _Wolfdieter Lang_, Oct 14 2005
%E A112493 New name from _Peter Luschny_, Apr 11 2016