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!)
A036653 Number of 6-valent trees with n nodes. 4
1, 1, 1, 1, 2, 3, 6, 11, 22, 45, 101, 223, 520, 1223, 2954, 7208, 17905, 44863, 113738, 290605, 748711, 1941592, 5067433, 13297590, 35074788, 92939166, 247317085, 660681399, 1771321949, 4764829720, 12857155911, 34793296227, 94410222996, 256826514689, 700311754812, 1913868186951 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..500

R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.

E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees)., J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.

Index entries for sequences related to trees

FORMULA

a(n) = A036651(n) + A036652(n) for n > 0.

MATHEMATICA

n = 20; (* algorithm from Rains and Sloane *)

S5[f_, h_, x_] := f[h, x]^5/120 + f[h, x]^3 f[h, x^2]/12 + f[h, x]^2 f[h, x^3]/6 + f[h, x] f[h, x^2]^2/8 + f[h, x] f[h, x^4]/4 + f[h, x^2] f[h, x^3]/6 + f[h, x^5]/5;

S6[f_, h_, x_] := f[h, x]^6/720 + f[h, x]^4 f[h, x^2]/48 + f[h, x]^3 f[h, x^3]/18 + f[h, x]^2 f[h, x^2]^2/16 + f[h, x]^2 f[h, x^4]/8 + f[h, x] f[h, x^2] f[h, x^3]/6 + f[h, x] f[h, x^5]/5 + f[h, x^2]^3/48 + f[h, x^2] f[h, x^4]/8 + f[h, x^3]^2/18 + f[h, x^6]/6;

T[-1, z_] := 1;  T[h_, z_] := T[h, z] = Table[z^k, {k, 0, n}].Take[CoefficientList[z^(n+1) + 1 + S5[T, h-1, z]z, z], n+1];

Sum[Take[CoefficientList[z^(n+1) + S6[T, h-1, z]z - S6[T, h-2, z]z - (T[h-1, z] - T[h-2, z]) (T[h-1, z]-1), z], n+1], {h, 1, n/2}] + PadRight[{0, 1}, n+1] + Sum[Take[CoefficientList[z^(n+1) + (T[h, z] - T[h-1, z])^2/2 + (T[h, z^2] - T[h-1, z^2])/2, z], n+1], {h, 0, n/2}] (* Robert A. Russell, Sep 15 2018 *)

CROSSREFS

Column k=6 of A144528.

Cf. A036651, A036652.

Sequence in context: A274936 A244521 A096202 * A318031 A316500 A123769

Adjacent sequences:  A036650 A036651 A036652 * A036654 A036655 A036656

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

a(0) changed to 1 and terms a(32) and beyond from Andrew Howroyd, Dec 18 2020

STATUS

approved

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 August 14 12:51 EDT 2022. Contains 356116 sequences. (Running on oeis4.)