A194649 Triangle of coefficients of a sequence of polynomials related to the enumeration of linear labeled rooted trees.

1, 1, 3, 4, 13, 36, 24, 75, 316, 432, 192, 541, 3060, 6360, 5760, 1920, 4683, 33244, 92880, 127680, 86400, 23040, 47293, 403956, 1418424, 2620800, 2688000, 1451520, 322560, 545835, 5449756, 23051952, 53548992, 73785600, 60318720, 27095040, 5160960, 7087261, 80985780, 400813080, 1122145920, 1943867520, 2133734400

Offset: 0

Author

Peter Bala, Sep 01 2011

Keywords

• nonn
• easy
• tabf

Comments

Define the sequence of polynomials {P(n,x)}n>=0 recursively by setting P(0,x) = 1, P(1,x) = 1 and P(n+1,x) = d/dx((1+x)*(1+2*x)*P(n,x)) for n >= 1. The first few values are P(2,x) = 3 + 4*x, P(3,x) = 13 + 36*x + 24*x^2 and P(4,x) = 75 + 316*x + 432*x^2 + 192*x^3.

This triangle shows the coefficients of the P(n,x) in ascending powers of x. The values of P(n,x) at an integer or half-integer value of x enumerate linear labeled rooted trees: in particular we have P(n,0) = A000670(n), P(n,1/2) = A050351(n), P(n,1) = A050352(n) and P(n,3/2) = A050353(n).

More generally, for m >= 2, P(n,m/2-1), n = 0,1,2,... counts m level linear labeled rooted trees (see the e.g.f. below and the comment of Benoit Cloitre in A050351).

Examples

			Triangle begins
n\k|......0.......1........2........3........4........5.......6
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
.0.|......1
.1.|......1
.2.|......3.......4
.3.|.....13......36.......24
.4.|.....75.....316......432......192
.5.|....541....3060.....6360.....5760.....1920
.6.|...4683...33244....92880...127680....86400....23040
.7.|..47293..403956..1418424..2620800..2688000..1451520..322560
..
		

Links

• L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, arXiv:math/0509207 [math.CO], 2005-2006.

Crossrefs

Cf. A000670, A002866 (main diagonal), A050351, A050352, A050353, A083411 (1/4*column 1).

Programs

Mathematica

T[0, 0] = T[1, 0] = 1; T[n_, k_] /; 0 <= k <= n-1 := T[n, k] = (k+1)*(2* T[n-1, k-1] + 3*T[n-1, k] + T[n-1, k+1]); T[, ] = 0;
{1}~Join~Table[T[n, k], {n, 1, 9}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Nov 13 2019 *)

Formula

T(n,k) = 2^k*Sum_{i = k+1..n} Stirling2(n,i)*i!*binomial(i-1,k).

Recurrence: T(n+1,k) = (k+1)*(2*T(n,k-1)+3*T(n,k)+T(n,k+1)).

E.g.f.: G(x,t) := 1 + (1-exp(t))/((2*x+1)*exp(t)-2*x-2) = Sum_{n>=0} P(n,x)*t^n/n! = 1 + t + (3 + 4*x)*t^2/2! + (13 + 36*x + 24*x^2)*t^3/3! + ....

Column k generating function: 2^k*((exp(x)-1)/(2-exp(x)))^(k+1) (apart from initial term 1 when k = 0).

The generating function G(x,t) satisfies the partial differential equation d/dx((1+x)*(1+2*x)*G(x,t)) - d/dt(G(x,t)) = 2*(2x+1). Hence the row polynomials P(n,x) satisfy the defining recurrence P(n+1,x) = d/dx((1+x)*(2+x)*P(n,x)), with P(0,x) = P(1,x) = 1.

Reflection property: P(n,x) = (-1)^n*P(n,-x-3/2).

The polynomial P(n,x) has all real zeros, lying in the interval [-1,-1/2] (apply [Liu et al, Theorem 1.1, Corollary 1.2] with f(x) = P(n,x-1/2) and g(x) = P'(n,x-1/2) and use the reflection property).

Row sums are A050352; Column 0: A000670; Column 1: 4*A083411; Main diagonal: A002866.