A001383 Number of n-node rooted trees of height at most 3.

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

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

Crossrefs

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

Programs

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

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

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