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

1, 2, 1, 9, 10, 3, 64, 113, 70, 15, 625, 1526, 1450, 630, 105, 7776, 24337, 31346, 20650, 6930, 945, 117649, 450066, 733845, 650188, 329175, 90090, 10395, 2097152, 9492289, 18760302, 20925065, 14194180, 5845455, 1351350, 135135, 43046721

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• tabl
• nice

Comments

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

Examples

			Triangle begins:
  1;
  2, 1;
  9, 10, 3;
  64, 113, 70, 15;
  ...
		

Links

• C. Flight, How many stemmata?, Manuscripta, 34 (1990), 122-128.
• C. Flight, How many stemmata?, Manuscripta, 34 (1990), 122-128. (Annotated scanned copy)
• C. Flight, Letter to N. J. A. Sloane, Nov 1990
• D. J. Jeffrey, G. A. Kalugin, 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.
• Index entries for sequences related to rooted trees
• Index entries for sequences related to trees

Crossrefs

Row sums give A005264. Cf. A005263, A048159, A052300-A052303. A054589.

Programs

Mathematica

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

Formula

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

From Peter Bala, Sep 29 2011: (Start)

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! + ....

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.

The shifted row polynomials R(n,t-1) are the row generating polynomials of A054589. (End)

From Peter Bala, Sep 12 2012: (Start)

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.

Assuming this, we could then use the recurrence equation to obtain explicit formulas for columns k = 2,3,....

For example, T(n,2) = 1/2*{(n+2)^(n+1) - 4*(n+1)^(n+1) + (4*n+3)*n^n}. (End)

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Apr 07 2000