A001383 Number of n-node rooted trees of height at most 3. (Formerly M1107 N0422)

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

Offset

0,4

Comments

a(n+1) is also the number of n-vertex graphs that do not contain a P_4, C_4, or K_4 as induced subgraph (K_4-free trivially perfect graphs, cf. A123467). - Falk Hüffner, Jan 10 2016

References

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

J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.

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. - Franklin T. Adams-Watters, Mar 01 2006

G.f.: 1 + x*exp( Sum_{n>=1} x^n/n * Product_{k>=1} 1/(1 - x^(n*k)) ). - Paul D. Hanna, Nov 01 2012

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..40);  # 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] & (* Jean-François Alcover, Jul 05 2011, after g.f. *)

Prog

(PARI) {a(n)=polcoeff(1+x*exp(sum(m=1, n, x^m/m/prod(k=1, n\m+1, 1-x^(m*k)+x*O(x^n)))), n)} \\ Paul D. Hanna, Nov 01 2012

Crossrefs

Cf. A000041, A001383-A001385, A034823-A034826.

Sequence in context: A088532 A271364 A036621 * A217733 A208976 A278554

Adjacent sequences: A001380 A001381 A001382 * A001384 A001385 A001386

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Status

approved