cp's OEIS Frontend

A048160 Triangle giving T(n,k) = number of (n,k) labeled rooted Greg trees (n >= 1, 0<=k<=n-1).

%I A048160 #46 Aug 14 2025 06:06:28
%S A048160 1,2,1,9,10,3,64,113,70,15,625,1526,1450,630,105,7776,24337,31346,
%T A048160 20650,6930,945,117649,450066,733845,650188,329175,90090,10395,
%U A048160 2097152,9492289,18760302,20925065,14194180,5845455,1351350,135135,43046721
%N A048160 Triangle giving T(n,k) = number of (n,k) labeled rooted Greg trees (n >= 1, 0<=k<=n-1).
%C A048160 An (n,k) rooted Greg tree can be described as a rooted tree with n black nodes and k white nodes where only the black nodes are labeled and the white nodes have at least 2 children. - _Christian G. Bower_, Nov 15 1999
%H A048160 C. Flight, <a href="https://doi.org/10.1484/J.MSS.3.1335">How many stemmata?</a>, Manuscripta, 34 (1990), 122-128.
%H A048160 C. Flight, <a href="/A048159/a048159.pdf">How many stemmata?</a>, Manuscripta, 34 (1990), 122-128. (Annotated scanned copy)
%H A048160 C. Flight, <a href="/A005263/a005263.pdf">Letter to N. J. A. Sloane, Nov 1990</a>
%H A048160 D. J. Jeffrey, G. A. Kalugin, N. Murdoch, <a href="http://www.apmaths.uwo.ca/~djeffrey/Offprints/JeffreySYNASC2015paper17.pdf">Lagrange inversion and Lambert W</a>, Preprint 2015.
%H A048160 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 A048160 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A048160 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A048160 T(n, 0)=n^(n-1), T(n, k)=(n+k-2)*T(n-1, k-1)+(2*n+2*k-2)*T(n-1, k)+(k+1)*T(n-1, k+1).
%F A048160 From _Peter Bala_, Sep 29 2011: (Start)
%F A048160 E.g.f.: compositional inverse with respect to x of t*(exp(-x)-1) + (1+t)*x*exp(-x) = compositional inverse with respect to x of (x - (2+t)*x^2/2! + (3+2*t)*x^3/3! - (4+3*t)*x^4/4! + ...) = x + (2+t)*x^2/2! + (9+10*t+3*t^2)*x^3/3! + ....
%F A048160 The row generating polynomials R(n,t) satisfy the recurrence R(n+1,t) = (1+t)^2*R'(n,t)+n*(2+t)*R(n,t) with R(1,t) = 1.
%F A048160 The shifted row polynomials R(n,t-1) are the row generating polynomials of A054589. (End)
%F A048160 From _Peter Bala_, Sep 12 2012: (Start)
%F A048160 It appears that the entries in column k = 1 are given by T(n,1) = (n+1)^n - 2*n^n (checked up to n = 15) - see A176824.
%F A048160 Assuming this, we could then use the recurrence equation to obtain explicit formulas for columns k = 2,3,....
%F A048160 For example, T(n,2) = 1/2*{(n+2)^(n+1) - 4*(n+1)^(n+1) + (4*n+3)*n^n}. (End)
%e A048160 Triangle begins:
%e A048160   1;
%e A048160   2, 1;
%e A048160   9, 10, 3;
%e A048160   64, 113, 70, 15;
%e A048160   ...
%t A048160 t[n_ /; n >= 1, k_ /; k >= 0] /; 0 <= k <= n-1 := t[n, k] = (n+k-2) t[n-1, k-1] + (2n + 2k - 2)*t[n-1, k] + (k+1) t[n-1, k+1]; t[1, 0] = 1; t[_, _] = 0; Flatten[Table[t[n, k], {n, 1, 9}, {k, 0, n-1}]] (* _Jean-François Alcover_, Jul 20 2011, after formula *)
%Y A048160 Row sums give A005264. Cf. A005263, A048159, A052300-A052303. A054589.
%K A048160 nonn,easy,tabl,nice
%O A048160 1,2
%A A048160 _N. J. A. Sloane_
%E A048160 More terms from Larry Reeves (larryr(AT)acm.org), Apr 07 2000