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

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

Author

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

Keywords

• nonn
• easy
• nice

Examples

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

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

Programs

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 iA000678 := 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 *)

Formula

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