login
This site is supported by donations to The OEIS Foundation.

 

Logo

110 people attended OEIS-50 (videos, suggestions); annual fundraising drive to start soon (donate); editors, please edit! (stack is over 300), your editing is more valuable than any donation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000602 Number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers.
(Formerly M0718 N0267)
29
1, 1, 1, 1, 2, 3, 5, 9, 18, 35, 75, 159, 355, 802, 1858, 4347, 10359, 24894, 60523, 148284, 366319, 910726, 2278658, 5731580, 14490245, 36797588, 93839412, 240215803, 617105614, 1590507121, 4111846763, 10660307791, 27711253769 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

Trees are unrooted, nodes are unlabeled. Every node has degree <= 4.

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 A000628 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 hydrogen atoms stripped off) so now each carbon bonds to 1 to 4 other carbons. The degree of each node is then <= 4.

REFERENCES

K. Adam, Title?, MNU 1983, 36, 29 (in German).

M. van Almsick, H. Dolhaine and H. Honig, Efficient algorithms to enumerate isomers and diamutamers with more than one type of substituent, J. Chem. Info. and Computer Science, 40 (2000), 956-966.

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.

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 290.

L. Bytautas and D. J. Klein, Chemical combinatorics for alkane-isomer enumeration and more, J. Chem. Inf. Comput. Sci., 38 (1998), 1063-1078.

A. Cayley, Über die analytischen Figuren, welche in der Mathematik Baeume genannt werden..., Chem. Ber. 8 (1875), 1056-1059.

R. Davies and P. J. Freyd, C_{167}H_{336} is The Smallest Alkane with More Realizable Isomers than the Observable Universe has Particles, Journal of Chemical Education, Vol. 66, 1989, pp. 278-281.

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

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

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

F. Harary and R. Z. Norman, Dissimilarity characteristic theorems for graphs, Proc. Amer. Math. Soc. 11 (1960), 332-334.

J. B. Hendrickson and C. A. Parks, "Generation and Enumeration of Carbon skeletons", J. Chem. Inf. Comput. Sci, vol. 31 (1991) pp. 101-107. See Table 2, column 2 on page 103.

H. R. Henze and C. M. Blair, The number of isomeric hydrocarbons of the methane series, J. Amer. Chem. Soc., 53 (1931), 3077-3085.

H. R. Henze and C. M. Blair, The number of structurally isomeric hydrocarbons of the ethylene series, J. Amer. Chem. Soc., 55 (1933), 680-686.

M. D. Jackson and T. I. Bieber, Applications of degree distribution, 2: construction and enumeration of isomers in the alkane series, J. Chem. Info. and Computer Science, 33 (1993), 701-708.

E. V. Konstantinova and M. V. Vidyuk, Discriminating tests of information and topological indices; animals and trees; J. Chem. Inf. Comput. Sci., 43 (2003), 1860-1871.

J. Lederberg et al., Applications of artificial intelligence for chemical systems, I: The number of possible organic compounds. Acyclic structures containing C, H, O and N, J. Amer. Chem. Soc., 91 (1969), 2973-2097.

P. Leroux and B. Miloudi, ``G\'{e}n\'{e}ralisations de la formule d'Otter,'' Ann. Sci. Math. Qu\'{e}bec, Vol. 16, No. 1, pp. 53-80, 1992.

S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926.

L. M. Masinter, Applications of artificial intelligence for chemical systems, XX, Exhaustive generation of cyclic and acyclic isomers, J. Amer. Chem. Soc., 96 (1974), 7702-7714.

W. R. Mueller et al., Molecular topological index, J. Chem. Inf. Comput. Sci., 30 (1990),160-163.

D. Perry, The number of structural isomers ..., J. Amer. Chem. Soc. 54 (1932), 2918-2920. [Gives a(60) correctly - compare first link below]

M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, I-graphs and others, Croatica Chem. Acta, 78 (2005), 563-567.

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

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

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

D. H. Rouvray, An introduction to the chemical applications of graph theory, Congress. Numerant., 55 (1986), 267-280. - N. J. A. Sloane, Apr 08 2012

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

Marten J. ten Hoor, Formula for Success?, Education in Chemistry, 2005, 42(1), 10.

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.

S. Wagner, Graph-theoretical enumeration and digital expansions: an analytic approach, Dissertation, Fakult. f. Tech. Math. u. Tech. Physik, Tech. Univ. Graz, Austria, Feb., 2006.

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

R. Aringhieri, P. Hansen and F. Malucelli, Chemical Tree Enumeration Algorithms, Report TR-99-09, Dept. Informatica, Univ. Pisa, 1999.

H. Bottomley, Illustration of initial terms of A000022, A000200, A000602

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 478

Alfred W. Francis, Numbers of Isomeric Alkylbenzenes, J. Am. Chem. Soc., 69:6 (1947), pp. 1536-1537.

Michael A. Kappler, GENSMI: Exhaustive Enumeration of Simple Graphs. Daylight CIS, Inc., EuroMUG '04;4-5 November 2004.

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.

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

Stephan Wagner, On the average Wiener index of degree-restricted trees

Index entries for sequences related to trees

Index entries for "core" sequences

FORMULA

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

Also equals A000022 + A000200 (n>0), both of which have known generating functions. Also g.f. = A000678(x)-A000599(x)+A000598(x^2) = (x+x^2+2x^3...)-(x^2+x^3+3x^4...)+(1+x^2+x^4+...) = 1+x+x^2+x^3+2x^4+3x^5...

EXAMPLE

a(6)=5 because hexane has five isomers: n-hexane; 2-methylpentane; 3-methylpentane; 2,2-dimethylbutane; 2,3-dimethylbutane. - Michael Lugo (mtlugo(AT)mit.edu), Mar 15 2003 (corrected by Andrey V. Kulsha, Sep 22 2011)

MAPLE

A000602 := proc(n) if n=0 then RETURN(1) else A000022(n)+A000200(n); fi; end;

CROSSREFS

Cf. A000598, A000625, A000628, A067608-A067610.

Sequence in context: A056766 A208986 A080091 * A034790 A047121 A182080

Adjacent sequences:  A000599 A000600 A000601 * A000603 A000604 A000605

KEYWORD

nonn,easy,core,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

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

Kappler reference from Jonathan Vos Post, Dec 15 2005

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified October 31 22:26 EDT 2014. Contains 248871 sequences.