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,3

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

Links

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

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

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.

Example

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

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 *)

Crossrefs

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

Sequence in context: A174684 A286917 A084315 * A062165 A243764 A201821

Adjacent sequences: A194646 A194647 A194648 * A194650 A194651 A194652

Keyword

nonn,easy,tabf

Author

Peter Bala, Sep 01 2011

Status

approved