login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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)
76
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).
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 290.
L. Bytautats, D. J. Klein, Alkane Isomere Combinatorics: Stereostructure enumeration and graph-invariant and molecylar-property distributions, J. Chem. Inf. Comput. Sci 39 (1999) 803, Table 1.
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.
Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.6.1 Chemical Isomers, p. 299.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 529.
Handbook of Combinatorics, North-Holland '95, p. 1963.
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.
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.
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.
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.
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.
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.
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
Pontus von Brömssen, Table of n, a(n) for n = 0..1000 (terms n = 0..60 from N. J. A. Sloane)
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.
Vijayakumar Ambat, Article about OEIS in Malayalam that mentions this sequence, Mathrubhumi (daily newspaper in Kerala State), circa Nov 20 2022.
R. Aringhieri, P. Hansen and F. Malucelli, Chemical Tree Enumeration Algorithms, Report TR-99-09, Dept. Informatica, Univ. Pisa, 1999.
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 (4 (1988), 304-313.
L. Bytautas and D. J. Klein, Chemical combinatorics for alkane-isomer enumeration and more, J. Chem. Inf. Comput. Sci., 38 (1998), 1063-1078.
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.
F. Harary and R. Z. Norman, Dissimilarity characteristic theorems for graphs, Proc. Amer. Math. Soc. 11 (1960), 332-334.
H. R. Henze and C. M. Blair, The number of isomeric hydrocarbons of the methane series, J. Amer. Chem. Soc., 53 (8) (1931), 3077-3085.
H. R. Henze and C. M. Blair, The number of isomeric hydrocarbons of the methane series, J. Amer. Chem. Soc., 53 (1931), 3077-3085. (Annotated scanned copy)
H. R. Henze and C. M. Blair, The number of structurally isomeric Hydrocarbons of the Ethylene Series, J. Amer. Chem. Soc., 55 (2) (1933), 680-686.
F. Hermann, Ueber das Problem, die Anzahl der isomeren Paraffine der Formel C_n H_{2n+2} zu bestimmung, Chem. Ber., 13 (1880), 792. [I (1880), Annotated scanned copy]
F. Hermann, Entgegnung, Chem. Ber., 31 (1898), 91. [III (1898), Annotated scanned copy]
Michael A. Kappler, GENSMI: Exhaustive Enumeration of Simple Graphs. Daylight CIS, Inc., EuroMUG '04;4-Nov 05 2004.
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, Letter to N. J. A. Sloane, Aug 13 1971
J. Lederberg, The topology of molecules, in The Mathematical Sciences. Cambridge, Mass.: MIT Press, 1969, pages 37-51. [Annotated scanned copy]
J. Lederberg, Dendral-64, I, Report to NASA, Dec 1964 [Annotated scanned copy]
J. Lederberg, Dendral-64, II, Report to NASA, Dec 1965 [Annotated scanned copy]
J. Lederberg, Dendral-64, III, Report to NASA, Dec 1968 [Annotated scanned copy]
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1 (1992), pp. 53-80.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926. (Annotated scanned copy)
S. M. Losanitsch, Bemerkungen zu der Hermasnnschen Mitteillung: Die Anzahl..., Chem. Ber., 30 (1897), 3059-3060 [Annotated scanned copy]
A. Masoumi, M. Antoniazzi, and M. Soutchanski, Modeling organic chemistry and planning organic synthesis, GCAI 2015. Global Conference on Artificial Intelligence (2015), pp. 176-195.
W. R. Mueller et al., Molecular topological index, J. Chem. Inf. Comput. Sci., 30 (1990),160-163.
R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
D. Perry, The number of structural isomers of certain homologs of methane and methanol, J. Amer. Chem. Soc. 54 (1932), 2918-2920. [Gives a(60) correctly] (Annotated scanned copy)
G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443. (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 p. 28.
R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron 32 (3) (1976), 355-361.
R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron 32 (3) (1976), 355-361. (Annotated scanned copy)
Hugo Schiff, Zur Statistik chemischer Verbindungen, Berichte der Deutschen Chemischen Gesellschaft, Vol. 8, pp. 1542-1547, 1875. [Annotated scanned copy]
Nicholas I. Shepherd-Barron, Asymptotic period relations for Jacobian elliptic surfaces, arXiv:1904.13344 [math.AG], 2019.
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 5.
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-390, 1983.
Sylvia Wenmackers, Huiswerk (met bijna twintig jaar vertraging) (in Dutch), 2015.
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 + ...
G.f.: B(x) - cycle_index(S2,-B(x)) + x * cycle_index(S4,B(x)) = B(x) - (B(x)^2 - B(x^2)) / 2 + x * (B(x)^4 + 6*B(x)^2*B(x^2) + 8*B(x)*B(x^3) + 3*B(x^2)^2 + 6*B(x^4)) / 24, where B(x) = 1 + x * cycle_index(S3,B(x)) = 1 + x * (B(x)^3 + 3*B(x)*B(x^2) + 2*B(x^3)) / 6 is the generating function for A000598. - Robert A. Russell, Jan 16 2023
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
1
else
end if;
end proc:
MATHEMATICA
n = 40; (* algorithm from Rains and Sloane *)
S3[f_, h_, x_] := f[h, x]^3/6 + f[h, x] f[h, x^2]/2 + f[h, x^3]/3;
S4[f_, h_, x_] := f[h, x]^4/24 + f[h, x]^2 f[h, x^2]/4 + f[h, x] f[h, x^3]/3 + f[h, x^2]^2/8 + f[h, x^4]/4;
T[-1, z_] := 1; T[h_, z_] := T[h, z] = Table[z^k, {k, 0, n}].Take[CoefficientList[z^(n+1) + 1 + S3[T, h-1, z]z, z], n+1];
Sum[Take[CoefficientList[z^(n+1) + S4[T, h-1, z]z - S4[T, h-2, z]z - (T[h-1, z] - T[h-2, z]) (T[h-1, z]-1), z], n+1], {h, 1, n/2}] + PadRight[{1, 1}, n+1] + Sum[Take[CoefficientList[z^(n+1) + (T[h, z] - T[h-1, z])^2/2 + (T[h, z^2] - T[h-1, z^2])/2, z], n+1], {h, 0, n/2}] (* Robert A. Russell, Sep 15 2018 *)
b[n_, i_, t_, k_] := b[n, i, t, k] = If[i<1, 0, Sum[Binomial[b[i-1, i-1,
k, k] + j-1, j]* b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
b[0, i_, t_, k_] = 1; m = 3; (* m = maximum children *) n = 40;
gf[x_] = 1 + Sum[b[j-1, j-1, m, m]x^j, {j, 1, n}]; (* G.f. for A000598 *)
ci[x_] = SymmetricGroupIndex[m+1, x] /. x[i_] -> gf[x^i];
CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
{x, 0, n}]], x] (* Robert A. Russell, Jan 19 2023 *)
CROSSREFS
Column k=4 of A144528.
A000602 = A000022 + A000200 for n>0.
Sequence in context: A355190 A208986 A080091 * A034790 A047121 A363307
KEYWORD
nonn,easy,core,nice
AUTHOR
EXTENSIONS
Additional comments from Steve Strand (snstrand(AT)comcast.net), Aug 20 2003
STATUS
approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 04:58 EDT 2024. Contains 370952 sequences. (Running on oeis4.)