A010372 Number of unrooted quartic trees with n (unlabeled) nodes and possessing a centroid; number of n-carbon alkanes C(n)H(2n +2) with a centroid ignoring stereoisomers.

1, 0, 1, 1, 3, 2, 9, 8, 35, 39, 159, 202, 802, 1078, 4347, 6354, 24894, 38157, 148284, 237541, 910726, 1511717, 5731580, 9816092, 36797588, 64658432, 240215803, 431987953, 1590507121, 2917928218, 10660307791, 19910436898

Offset

1,5

Comments

The degree of each node is <= 4.

A centroid is a node with less than n/2 nodes in each of the incident subtrees, where n is the number of nodes in the tree. If a centroid exists it is unique.

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 A086194 for the analogous sequence with stereoisomers counted.

References

F. Harary, Graph Theory, p. 36, for definition of centroid.

Links

Table of n, a(n) for n=1..32.

A. Cayley, Über die analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen, Chem. Ber. 8 (1875), 1056-1059. (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.

Index entries for sequences related to trees

Maple

with(combstruct): Alkyl := proc(n) combstruct[count]([ U, {U=Prod(Z, Set(U, card<=3))}, unlabeled ], size=n) end:
centeredHC := proc(n) option remember; local f, k, z, f2, f3, f4; f := 1 + add(Alkyl(k)*z^k, k=0..iquo(n-1, 2));
f2 := series(subs(z=z^2, f), z, n+1); f3 := series(subs(z=z^3, f), z, n+1); f4 := series(subs(z=z^4, f), z, n+1);
f := series(f*f3/3+f4/4+f2^2/8+f2*f^2/4+f^4/24, z, n+1); coeff(f, z, n-1) end: seq(centeredHC(n), n=1..32);

Crossrefs

Cf. A010373, A000022, A086194, A000598, A000602.

A000602(n) = a(n) + A010373(n/2) for n even, A000602(n) = a(n) for n odd.

Sequence in context: A081233 A050676 A356185 * A374299 A199455 A287768

Adjacent sequences: A010369 A010370 A010371 * A010373 A010374 A010375

Keyword

nonn,easy,nice

Author

Paul Zimmermann, N. J. A. Sloane

Extensions

Description revised by Steve Strand (snstrand(AT)comcast.net), Aug 20 2003

Status

approved