0,4

Number of unlabeled rooted trees in which each node has out-degree <= 3.

Ignoring stereoisomers means that the children of a node are unordered. They can be permuted in any way and it is still the same tree. See A000625 for the analogous sequence with stereoisomers counted.

In alkanes every carbon has valence exactly 4 and every hydrogen has valence exactly 1. But the trees considered here are just the carbon "skeletons" (with all the hydrogens stripped off) so now each carbon bonds to 1 to 4 other carbons. The out-degree is then <= 3.

Other descriptions of this sequence: quartic planted trees with n nodes; ternary rooted trees with n nodes and height at most 3.

A. T. Balaban, J. W. Kennedy and L. V. Quintas, The number of alkanes having n carbons and a longest chain of length d, J. Chem. Education, 65 (No. 4, 1988), 304-313.

N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 62 (quoting Cayley, who is wrong).

A. Cayley, On the mathematical theory of isomers, Phil. Mag. vol. 67 (1874), 444-447 (a(6) is wrong).

J. L. Faulon, D. Visco and D. Roe, Enumerating Molecules, In: Reviews in Computational Chemistry Vol. 21, Ed. K. Lipkowitz, Wiley-VCH, 2005.

R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.397.

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

Handbook of Combinatorics, North-Holland '95, p. 1963.

H. R. Henze and C. M. Blair, The number of structurally isomeric alcohols of the methanol series, J. Amer. Chem. Soc., 53 (1931), 3042-3046.

Knop, Mueller, Szymanski and Trinajstich, Computer generation of certain classes of molecules.

Camden A. Parks and James B. Hendrickson, Enumeration of monocyclic and bicyclic carbon skeletons, J. Chem. Inf. Comput. Sci., vol. 31, 334-339 (1991).

D. Perry, The number of structural isomers ..., J. Amer. Chem. Soc. 54 (1932), 2918-2920.

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

G. Polya, Mathematical and Plausible Reasoning, Vol. 1 Prob. 4 pp. 85; 233.

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; see p. 20, Eq. (G); p. 27, Eq. 2.1.

R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes..., Tetrahedron 32 (1976), 355-361.

N. Trinajstich, Z. Jerievi, J. V. Knop, W. R. Muller and K. Szymanski, COMPUTER GENERATION OF ISOMERIC STRUCTURES, Pure & Appl. Chem., Vol. 55, No. 2, pp. 379-39O, 1983.

N. J. A. Sloane, Table of n, a(n) for n = 0..200

Frederic Chyzak, Enumerating alcohols and other classes of chemical molecules

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1

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

G.f. satisfies A(x) = 1+(1/6)*x*(A(x)^3+3A(x)A(x^2)+2A(x^3)).

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: A000598 := n->coeff(G000598, z, n);

[Another Maple program for g.f. G000598] G000598 := 1; f := proc(n) global G000598; coeff(series(1+(1/6)*x*(G000598^3+3*G000598*subs(x=x^2, G000598)+2*subs(x=x^3, G000598)), x, n+1), x, n); end; for n from 1 to 50 do G000598 := series(G000598+f(n)*x^n, x, n+1); od; G000598;

spec := [S, {Z=Atom, S=Union(Z, Prod(Z, Set(S, card=3)))}, unlabeled]: [seq(combstruct[count](spec, size=n), n=0..20)];

Cf. A000599, A000600, A000602, A000625, A000628, A000678, A010372, A010373, A086194, A086200.

Sequence in context: A055545 A036375 A036376 this_sequence A003008 A054199 A054197

Adjacent sequences: A000595 A000596 A000597 this_sequence A000599 A000600 A000601

nonn,easy,nice,eigen

njas

Additional comments from Steve Strand (snstrand(AT)comcast.net), Aug 20, 2003.