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

Author

F. Chapoton, Apr 14 2000

Keywords

• nonn
• tabl

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)

Examples

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

Links

• 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.
• William Y. C. Chen, Amy M. Fu, and Elena L. Wang, A Grammatical Calculus for the Ramanujan Polynomials, arXiv:2506.01649 [math.CO], 2025. See p. 3.
• William Y. C. Chen, Larry X. W. Wang, and Arthur L. B. Yang, Recurrence Relations for Strongly q-Log-Convex Polynomials, arXiv:0806.3641v1 [math.CO], 2008.
• Diego Dominici, Nested derivatives: A simple method for Computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.
• Brian 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.
• Matthieu 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.

Crossrefs

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

Programs

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

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