A054589 - OEIS

%I #73 Jun 28 2023 22:38:41

%S 1,1,1,2,4,3,6,18,25,15,24,96,190,210,105,120,600,1526,2380,2205,945,

%T 720,4320,13356,26488,34650,27720,10395,5040,35280,128052,305620,

%U 507430,575190,405405,135135

%N Table related to labeled rooted trees, cycles and binary trees.

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

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

%C From _Peter Bala_, Sep 29 2011: (Start)

%C 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 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 (End)

%H 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 W. Chen, L. X. W. Wang and A. 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 D. 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 B. 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 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 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 M. 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 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 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 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 From _Peter Bala_, Sep 29 2011: (Start)

%F 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 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 (End)

%F 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 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 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 Triangle begins:

%e   {1},

%e   {1,  1},

%e   {2,  4,  3},

%e   {6, 18, 25, 15},

%e   ...

%t 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 Clear[a];

%t a[1, 0] = 1;

%t a[n_, k_] /; k < 0 || k >= n := 0

%t a[n_, k_] /; 0 <= k <= n - 1 :=

%t a[n, k] = (n - 1) a[n - 1, k] + (n + k - 2) a[n - 1, k - 1]

%t Table[a[n, k], {n, 20}, {k, 0, n - 1} (* _David Callan_, Oct 14 2012 *)

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

%K nonn,tabl

%O 1,4

%A _F. Chapoton_, Apr 14 2000