login
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.
14

%I #54 Sep 30 2022 22:28:33

%S 1,1,1,1,4,3,1,11,25,15,1,26,130,210,105,1,57,546,1750,2205,945,1,120,

%T 2037,11368,26775,27720,10395,1,247,7071,63805,247555,460845,405405,

%U 135135,1,502,23436,325930,1939630,5735730,8828820,6756750,2027025,1

%N 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 Previous name was: Coefficient triangle of polynomials used for e.g.f.s of Stirling2 diagonals.

%C For the o.g.f. of diagonal k of the Stirling2 triangle one has a similar result. See A008517 (second-order Eulerian triangle).

%C 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 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 It appears that the triangles in this sequence and A124324 have identical columns, except for shifts. - _Jörgen Backelin_, Jun 20 2022

%C 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 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 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 Wolfdieter Lang, <a href="/A112493/a112493_1.txt">First ten rows.</a>

%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.

%F 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 From _Peter Bala_, Sep 30 2011: (Start)

%F 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 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 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 Sum_{j=0..n} T(n-j,j) = A000110(n). - _Alois P. Heinz_, Jun 20 2022

%e Triangle starts:

%e [1]

%e [1, 1]

%e [1, 4, 3]

%e [1, 11, 25, 15]

%e [1, 26, 130, 210, 105]

%e [1, 57, 546, 1750, 2205, 945]

%e ...

%e 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 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 ...................................................

%e ....1o.(1+t)...........1o.t*(1+t).....1o.t*(1+t)...

%e ....|................. /.\............/.\..........

%e ....|................ /...\........../...\.........

%e ....2o.(1+t)........2o.....3o......3o....2o........

%e ....|..............................................

%e ....|..............................................

%e ....3o.............................................

%e ...................................................

%e 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 T := (n, k) -> add(combinat:-eulerian2(n, j)*binomial(n-j, n-k), j=0..n):

%p seq(seq(T(n, k), k=0..n), n=0..9); # _Peter Luschny_, Apr 11 2016

%t 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 Row sums give A006351(k+1), k>=0.

%Y The column sequences start with A000012 (powers of 1), A000295 (Eulerian numbers), A112495, A112496, A112497.

%Y Cf. A008278, A008517, A048993, A054589, A075856, A134991, A201637, A124324.

%Y Antidiagonal sums give A000110.

%Y Cf. A356145.

%K nonn,easy,tabl

%O 0,5

%A _Wolfdieter Lang_, Oct 14 2005

%E New name from _Peter Luschny_, Apr 11 2016