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.
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
KEYWORD
nonn,easy,nice
AUTHOR
STATUS
approved