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,2

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

Links

Table of n, a(n) for n=1..37.

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

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)

Example

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

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

Crossrefs

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

Sequence in context: A019615 A132744 A059604 * A305178 A295851 A368375

Adjacent sequences: A048157 A048158 A048159 * A048161 A048162 A048163

Keyword

nonn,easy,tabl,nice

Author

N. J. A. Sloane

Extensions

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

Status

approved