A000678 Number of carbon (rooted) trees with n carbon atoms = unordered 4-tuples of ternary trees. (Formerly M1171 N0448)

0, 1, 1, 2, 4, 9, 18, 42, 96, 229, 549, 1347, 3326, 8330, 21000, 53407, 136639, 351757, 909962, 2365146, 6172068, 16166991, 42488077, 112004630, 296080425, 784688263, 2084521232, 5549613097, 14804572332, 39568107511, 105938822149

Offset

0,4

References

A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 454).

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 527.

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..60

Jean-François Alcover, Mathematica program translated from N. J. A. Sloane's Maple program for A000022, A000200, A000598, A000602, A000678

G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443; line 10 of Table I.

G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443; Table I, line 10 (Annotated scanned copy)

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.

R. C. Read, The Enumeration of Acyclic Chemical Compounds, pp. 25-61 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976. [Annotated scanned copy] See g.f. called P(x) on p. 28, 37.

N. J. A. Sloane, Maple program and first 60 terms for A000022, A000200, A000598, A000602, A000678

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

Formula

G.f.: A(x) = x*cycle_index(S4, B(x)), B(x) = g.f. for A000598.

Example

z+z^2+2*z^3+4*z^4+9*z^5+18*z^6+42*z^7+...

Maple

Let T_i(z) = g.f. for ternary trees of height at most i.
N := 45; G000598 := 0: i := 0: while i<(N+1) do G000598 := series(1+z*(G000598^3/6+subs(z=z^2, G000598)*G000598/2+subs(z=z^3, G000598)/3)+O(z^(N+1)), z, N+1): t[ i ] := G000598: i := i+1: od: # G000598 = g.f. for A000598
i := 0: while i<N+1 do T := t[ i ]: G000678 := series(z*(T^4/24+subs(z=z^2, T)*T^2/4+subs(z=z^2, T)^2/8+T*subs(z=z^3, T)/3+subs(z=z^4, T)/4)+O(z^(N+1)), z, N+1): q[ i ] := G000678: i := i+1: od: A000678 := n->coeff(G000678, z, n); # G000678 = g.f. for A000678.
(this Maple program continues in A000022.)

Mathematica

m = 45; (* T = G000598 *) T[_] = 0; Do[T[z_] = 1 + z*(T[z]^3/6 + T[z^2]*T[z]/2 + T[z^3]/3) + O[z]^m // Normal, m];
G000678[z_] = z*(T[z]^4/24 + T[z^2]*T[z]^2/4 + T[z^2]^2/8 + T[z]*T[z^3]/3 + T[z^4]/4) + O[z]^m;
CoefficientList[G000678[z], z] (* Jean-François Alcover, Jan 11 2018, after N. J. A. Sloane *)

Crossrefs

Sequence in context: A264649 A259803 A032175 * A362037 A368422 A283877

Adjacent sequences: A000675 A000676 A000677 * A000679 A000680 A000681

Keyword

nonn,easy,nice

Author

N. J. A. Sloane, E. M. Rains (rains(AT)caltech.edu)

Status

approved