login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001383 Number of n-node rooted trees of height at most 3.
(Formerly M1107 N0422)
19

%I M1107 N0422 #51 Dec 19 2021 09:57:48

%S 1,1,1,2,4,8,15,29,53,98,177,319,565,1001,1749,3047,5264,9054,15467,

%T 26320,44532,75054,125904,210413,350215,580901,960035,1581534,2596913,

%U 4251486,6939635,11296231,18337815,29692431,47956995,77271074,124212966

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

%C 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

%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="/A001383/b001383.txt">Table of n, a(n) for n=0..200</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=62">Encyclopedia of Combinatorial Structures 62</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 <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 G.f.: S[ 3 ] := x*Product (1 - x^k)^(-p(k-1)), where p(k) = number of partitions of k.

%F 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

%F 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

%p s[ 2 ] := x/product('1-x^i','i'=1..30); # G.f. for trees of ht <=2, A000041

%p for k from 3 to 12 do # gets g.f. for trees of ht <= 3,4,5,...

%p s[ k ] := series(x/product('(1-x^i)^coeff(s[ k-1 ],x,i)','i'=1..30),x,31); od:

%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): 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

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

%o (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

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

%K nonn,easy,nice

%O 0,4

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 07:48 EDT 2024. Contains 371235 sequences. (Running on oeis4.)