cp's OEIS Frontend

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

%I A054589 #80 Jun 11 2025 16:35:29
%S A054589 1,1,1,2,4,3,6,18,25,15,24,96,190,210,105,120,600,1526,2380,2205,945,
%T A054589 720,4320,13356,26488,34650,27720,10395,5040,35280,128052,305620,
%U A054589 507430,575190,405405,135135
%N A054589 Table related to labeled rooted trees, cycles and binary trees.
%C A054589 The left column is (n-1)!, the right column is (2n-3)!!, the total of each row is n^(n-1).
%C A054589 Constant terms of polynomials related to Ramanujan psi polynomials (see Zeng reference).
%C A054589 From _Peter Bala_, Sep 29 2011: (Start)
%C A054589 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.].
%C A054589 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.
%C A054589 (End)
%H A054589 J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, <a href="http://arxiv.org/abs/1307.2010">Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure</a>, arXiv:1307.2010 [math.CO], 2013-2014.
%H A054589 William Y. C. Chen, Amy M. Fu, and Elena L. Wang, <a href="https://arxiv.org/abs/2506.01649">A Grammatical Calculus for the Ramanujan Polynomials</a>, arXiv:2506.01649 [math.CO], 2025. See p. 3.
%H A054589 William Y. C. Chen, Larry X. W. Wang, and Arthur L. B. Yang, <a href="http://arxiv.org/abs/0806.3641">Recurrence Relations for Strongly q-Log-Convex Polynomials</a>, arXiv:0806.3641v1 [math.CO], 2008.
%H A054589 Diego 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 A054589 Brian Drake, <a href="http://people.brandeis.edu/~gessel/homepage/students/drakethesis.pdf">An inversion theorem for labeled trees and some limits of areas under lattice paths</a>, A dissertation presented to the Faculty of the Graduate School of Arts and Sciences of Brandeis University.
%H A054589 Dominique Dumont and Armand Ramamonjisoa, <a href="https://doi.org/10.37236/1275">Grammaire de Ramanujan et Arbres de Cayley</a>, Electr. J. Combinatorics, Volume 3, Issue 2 (1996) R17 (see page 16).
%H A054589 D. J. Jeffrey, G. A. Kalugin, and N. Murdoch, <a href="https://www.uwo.ca/apmaths/faculty/jeffrey/pdfs/JeffreySYNASC2015paper17.pdf">Lagrange inversion and Lambert W</a>, Preprint 2015.
%H A054589 Matthieu Josuat-Vergès, <a href="http://arxiv.org/abs/1310.7531">Derivatives of the tree function</a>, arXiv preprint arXiv:1310.7531 [math.CO], 2013.
%H A054589 Peter W. Shor, <a href="https://doi.org/10.1016/0097-3165(95)90022-5">A new proof of Cayley's formula for counting labeled trees</a>, J. Combin. Theory Ser. A 71 (1995), no. 1, 154-158.
%H A054589 Jiang Zeng, <a href="http://math.univ-lyon1.fr/homes-www/zeng/public_html/paper/Cayley.ps">A Ramanujan sequence that refines the Cayley formula for trees</a>, Ramanujan J., 3(1999) 1, 45-54.
%F A054589 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.
%F A054589 From _Peter Bala_, Sep 29 2011: (Start)
%F A054589 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! + ....
%F A054589 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.
%F A054589 (End)
%F A054589 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
%F A054589 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
%F A054589 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
%e A054589 Triangle begins:
%e A054589   {1},
%e A054589   {1,  1},
%e A054589   {2,  4,  3},
%e A054589   {6, 18, 25, 15},
%e A054589   ...
%t A054589 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 *)
%t A054589 Clear[a];
%t A054589 a[1, 0] = 1;
%t A054589 a[n_, k_] /; k < 0 || k >= n := 0
%t A054589 a[n_, k_] /; 0 <= k <= n - 1 :=
%t A054589 a[n, k] = (n - 1) a[n - 1, k] + (n + k - 2) a[n - 1, k - 1]
%t A054589 Table[a[n, k], {n, 20}, {k, 0, n - 1}] (* _David Callan_, Oct 14 2012 *)
%Y A054589 Cf. A000169, A001147, A075856, A048159, A048160, A042977.
%K A054589 nonn,tabl
%O A054589 1,4
%A A054589 _F. Chapoton_, Apr 14 2000