|
|
A048160
|
|
Triangle giving T(n,k) = number of (n,k) labeled rooted Greg trees (n >= 1, 0<=k<=n-1).
|
|
11
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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).
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)
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Apr 07 2000
|
|
STATUS
|
approved
|
|
|
|