A054589 Table related to labeled rooted trees, cycles and binary trees.

1, 1, 1, 2, 4, 3, 6, 18, 25, 15, 24, 96, 190, 210, 105, 120, 600, 1526, 2380, 2205, 945, 720, 4320, 13356, 26488, 34650, 27720, 10395, 5040, 35280, 128052, 305620, 507430, 575190, 405405, 135135

Offset

1,4

Comments

The left column is (n-1)!, the right column is (2n-3)!!, the total of each row is n^(n-1).

Constant terms of polynomials related to Ramanujan psi polynomials (see Zeng reference).

From Peter Bala, Sep 29 2011: (Start)

Differentiating n times the Lambert function W(x) = Sum_{n>=1} n^(n-1)*x^n/n! with respect to x yields (d/dx)^n W(x) = exp(n*W(x))/(1-W(x))^n*R(n,1/(1-W(x))), where R(n,x) is the n-th row polynomial of this triangle. The first few values are R(1,x) = 1, R(2,x) = 1+x, R(3,x) = 2+4*x+3*x^2. The Ramanujan polynomials R(n,x) are strongly x-log-convex [Chen et al.].

Shor and Dumont-Ramamonjisoa have proved independently that the coefficient of x^k in R(n,x) counts rooted labeled trees on n vertices with k improper edges. Drake, Example 1.7.3, gives another combinatorial interpretation for this triangle as counting a family of labeled trees.

(End)

Links

Table of n, a(n) for n=1..36.

J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013-2014.

W. Chen, L. X. W. Wang and A. L. B. Yang, Recurrence Relations for Strongly q-Log-Convex Polynomials, arXiv:0806.3641v1 [math.CO], 2008.

D. Dominici, Nested derivatives: A simple method for Computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.

B. Drake, An inversion theorem for labeled trees and some limits of areas under lattice paths, A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.

Dominique Dumont and Armand Ramamonjisoa, Grammaire de Ramanujan et Arbres de Cayley, Electr. J. Combinatorics, Volume 3, Issue 2 (1996) R17 (see page 16).

D. J. Jeffrey, G. A. Kalugin, and N. Murdoch, Lagrange inversion and Lambert W, Preprint 2015.

M. Josuat-Vergès, Derivatives of the tree function, arXiv preprint arXiv:1310.7531 [math.CO], 2013.

Peter W. Shor, A new proof of Cayley's formula for counting labeled trees, J. Combin. Theory Ser. A 71 (1995), no. 1, 154-158.

Jiang Zeng, A Ramanujan sequence that refines the Cayley formula for trees, Ramanujan J., 3(1999) 1, 45-54.

Formula

The polynomials p_n = Sum a[n, k]x^k satisfy p_1=1 and p_(n+1) = x*x*dp_n/dx+n*(1+x)*p_n.

From Peter Bala, Sep 29 2011: (Start)

E.g.f.: series reversion with respect to x of (1-t+(t-1+x*t)*exp(-x)) = x + (1+t)*x^2/2! + (2+4*t+3*t^2)*x^3/3! + ....

The sequence of shifted row polynomials {p_n(1+t)}n>=1 begins [1,2+t,9+10*t+3*t^2,...]. These are the row polynomials of A048160.

(End)

Let f(x) = exp(x)/(1-t*x). The e.g.f. A(x,t) = x + (1+t)*x^2/2! + (2+4*t+3*t^2)*x^3/3! + ... satisfies the autonomous differential equation dA/dx = f(A). The n-th row polynomial (n>=1) equals D^(n-1)(f(x)) evaluated at x = 0, where D is the operator f(x)*d/dx (apply [Dominici, Theorem 4.1]). - Peter Bala, Nov 09 2011

The polynomials (1+t)^(n-1)*p_n(1/(1+t)) are (up to sign) the row polynomials of A042977. - Peter Bala, Jul 23 2012

Let q_n = Sum_{k>=0} a(n,k)*t^(n-k), with q_0 = 1. (So q_1=t, q_2 = t+t^2, and q_3 = 3*t + 4*t^2 + 2*t^3.) Then Sum_{n>=0} q_n*x^n/n! = t - W((t-1-t^2*x)*exp(t-1)), where W is the Lambert function. - Ira M. Gessel, Jan 06 2012

Example

Triangle begins:
  {1},
  {1,  1},
  {2,  4,  3},
  {6, 18, 25, 15},
  ...

Mathematica

p[1] = 1; p[n_] := p[n] = Expand[x^2*D[p[n-1], x] + (n-1)(1+x)p[n-1]]; Flatten[ Table[ CoefficientList[ p[n], x], {n, 1, 8}]] (* Jean-François Alcover, Jul 22 2011 *)
Clear[a];
a[1, 0] = 1;
a[n_, k_] /; k < 0 || k >= n := 0
a[n_, k_] /; 0 <= k <= n - 1 :=
a[n, k] = (n - 1) a[n - 1, k] + (n + k - 2) a[n - 1, k - 1]
Table[a[n, k], {n, 20}, {k, 0, n - 1} (* David Callan, Oct 14 2012 *)

Crossrefs

Cf. A000169, A001147, A075856, A048159, A048160, A042977.

Sequence in context: A091274 A330745 A122525 * A051851 A336165 A011171

Adjacent sequences: A054586 A054587 A054588 * A054590 A054591 A054592

Keyword

nonn,tabl

Author

F. Chapoton, Apr 14 2000

Status

approved