login
Number of n-node trees of height at most 4.
(Formerly M1172 N0449)
4

%I M1172 N0449 #41 Dec 19 2021 09:58:04

%S 1,1,1,2,4,9,19,42,89,191,402,847,1763,3667,7564,15564,31851,64987,

%T 132031,267471,539949,1087004,2181796,4367927,8721533,17372967,

%U 34524291,68456755,135446896,267444085,527027186,1036591718,2035083599

%N Number of n-node trees of height at most 4.

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H N. J. A. Sloane, <a href="/A001384/b001384.txt">Table of n, a(n) for n=0..200</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=63">Encyclopedia of Combinatorial Structures 63</a>

%H J. Riordan, <a href="http://dx.doi.org/10.1147/rd.45.0473">Enumeration of trees by height and diameter</a>, IBM J. Res. Dev. 4 (1960), 473-478.

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F Take Euler transform of A001383 and shift right. (_Christian G. Bower_)

%p For Maple program see link in A000235.

%p 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): b1:= etr(k-> A000041(k-1)): A001383:= n->`if`(n=0,1,b1(n-1)): b2:= etr(A001383): a:= n->`if`(n=0,1,b2(n-1)): seq(a(n), n=0..40); # _Alois P. Heinz_, Sep 08 2008

%t Prepend[Nest[CoefficientList[Series[Product[1/(1-x^i)^#[[i]],{i,1,Length[#]}],{x,0,40}],x]&,{1},4],1] (* _Geoffrey Critzer_, Aug 01 2013 *)

%Y See A001383 for details.

%K nonn

%O 0,4

%A _N. J. A. Sloane_