OFFSET
1,8
COMMENTS
Harary denotes the g.f. as P(x, y) on page 33 "... , and let P(x,y) = Sum Sum P_{nm} x^ny^m where P_{nm} is the number of planted trees with n points and m endpoints, in which again the plant has not been counted either as a point or as an endpoint." - Michael Somos, Nov 02 2014
REFERENCES
F. Harary, Recent results on graphical enumeration, pp. 29-36 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1275
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
FORMULA
G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.
G.f. satisfies A(x, y) = x*y - x + x * exp(Sum_{i>0} A(x^i, y^i) / i). [Harary, p. 34, equation (10)]. - Michael Somos, Nov 02 2014
Sum_k T(n, k) = A000081(n). - Michael Somos, Aug 24 2015
EXAMPLE
From Joerg Arndt, Aug 18 2014: (Start)
Triangle starts:
01: 1
02: 1 0
03: 1 1 0
04: 1 2 1 0
05: 1 4 3 1 0
06: 1 6 8 4 1 0
07: 1 9 18 14 5 1 0
08: 1 12 35 39 21 6 1 0
09: 1 16 62 97 72 30 7 1 0
10: 1 20 103 212 214 120 40 8 1 0
11: 1 25 161 429 563 416 185 52 9 1 0
12: 1 30 241 804 1344 1268 732 270 65 10 1 0
13: 1 36 348 1427 2958 3499 2544 1203 378 80 11 1 0
...
The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
: 1: [ 0 1 2 3 4 ] 1
: O--o--o--o--o
:
: 2: [ 0 1 2 3 3 ] 2
: O--o--o--o
: .--o
:
: 3: [ 0 1 2 3 2 ] 2
: O--o--o--o
: .--o
:
: 4: [ 0 1 2 3 1 ] 2
: O--o--o--o
: .--o
:
: 5: [ 0 1 2 2 2 ] 3
: O--o--o
: .--o
: .--o
:
: 6: [ 0 1 2 2 1 ] 3
: O--o--o
: .--o
: .--o
:
: 7: [ 0 1 2 1 2 ] 2
: O--o--o
: .--o--o
:
: 8: [ 0 1 2 1 1 ] 3
: O--o--o
: .--o
: .--o
:
: 9: [ 0 1 1 1 1 ] 4
: O--o
: .--o
: .--o
: .--o
:
This gives [1, 4, 3, 1, 0], row n=5 of the triangle.
(End)
G.f. = x*(y + x*y + x^2*(y + y^2) + x^3*(y + 2*y^2 + y^3) + x^4*(y + 4*y^2 + 3*x^3 + y^4) + ...).
MATHEMATICA
rut[n_]:=rut[n]=If[n===1, {{}}, Join@@Function[c, Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
Table[Length[Select[rut[n], Count[#, {}, {-2}]===k&]], {n, 13}, {k, n}] (* Gus Wiseman, Mar 19 2018 *)
PROG
(PARI) {T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*(y - 1 + exp( sum(i=1, j, 1/i * subst( subst( A + x * O(x^(j\i)), x, x^i), y, y^i) ) ))); polcoeff( polcoeff(A, n), k))}; /* Michael Somos, Aug 24 2015 */
CROSSREFS
KEYWORD
AUTHOR
Christian G. Bower, May 09 2000
STATUS
approved