|
| |
|
|
A001383
|
|
Number of n-node rooted trees of height at most 3.
(Formerly M1107 N0422)
|
|
10
| |
|
|
1, 1, 1, 2, 4, 8, 15, 29, 53, 98, 177, 319, 565, 1001, 1749, 3047, 5264, 9054, 15467, 26320, 44532, 75054, 125904, 210413, 350215, 580901, 960035, 1581534, 2596913, 4251486, 6939635, 11296231, 18337815, 29692431, 47956995, 77271074, 124212966
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
REFERENCES
| J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| N. J. A. Sloane, Table of n, a(n) for n=0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 62
Index entries for sequences related to rooted trees
Index entries for sequences related to trees
|
|
|
FORMULA
| G.f.: S[ 3 ] := x*Product (1 - x^k)^(-p(k-1)), where p(k) = number of partitions of k.
a(n+1) is the Euler transform of p(n-1), where p() = A000041 is the partition function. - Frank Adams-Watters, Mar 01 2006
|
|
|
MAPLE
| s[ 2 ] := x/product('1-x^i', 'i'=1..30); # G.f. for trees of ht <=2, A000041
for k from 3 to 12 do # gets g.f. for trees of ht <= 3, 4, 5, ...
s[ k ] := series(x/product('(1-x^i)^coeff(s[ k-1 ], x, i)', 'i'=1..30), x, 31); od:
For Maple program see link in A000235.
with (numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d, j; if n=0 then 1 else add (add (d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: A000041:= etr (n-> 1): a:= n->`if`(n=0, 1, etr (k-> A000041(k-1))(n-1)): seq (a(n), n=0..36); [From Alois P. Heinz, Sep 08 2008]
|
|
|
MATHEMATICA
| m = 36; CoefficientList[ Series[x*Product[(1 - x^k)^(-PartitionsP[k - 1]), {k, 1, m}], {x, 0, m}], x] // Rest // Prepend[#, 1] & (* From Jean-François Alcover, Jul 05 2011, after g.f. *)
|
|
|
CROSSREFS
| Cf. A000041, A001383-A001385, A034823-A034826.
Sequence in context: A190160 A088532 A036621 * A108564 A066369 A000078
Adjacent sequences: A001380 A001381 A001382 * A001384 A001385 A001386
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
