|
%I M0718 N0267 #215 Mar 22 2024 08:57:48
%S 1,1,1,1,2,3,5,9,18,35,75,159,355,802,1858,4347,10359,24894,60523,
%T 148284,366319,910726,2278658,5731580,14490245,36797588,93839412,
%U 240215803,617105614,1590507121,4111846763,10660307791,27711253769
%N Number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers.
%C Trees are unrooted, nodes are unlabeled. Every node has degree <= 4.
%C 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.
%C 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.
%D K. Adam, Title?, MNU 1983, 36, 29 (in German).
%D F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 290.
%D 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.
%D A. Cayley, Über die analytischen Figuren, welche in der Mathematik Baeume genannt werden..., Chem. Ber. 8 (1875), 1056-1059.
%D 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.
%D J. L. Faulon, D. Visco and D. Roe, Enumerating Molecules, In: Reviews in Computational Chemistry Vol. 21, Ed. K. Lipkowitz, Wiley-VCH, 2005.
%D Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.6.1 Chemical Isomers, p. 299.
%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 529.
%D Handbook of Combinatorics, North-Holland '95, p. 1963.
%D 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.
%D 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.
%D 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.
%D 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 D. Perry, The number of structural isomers ..., J. Amer. Chem. Soc. 54 (1932), 2918-2920. [Gives a(60) correctly - compare first link below]
%D M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, I-graphs and others, Croatica Chem. Acta, 78 (2005), 563-567.
%D 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
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D Marten J. ten Hoor, Formula for Success?, Education in Chemistry, 2005, 42(1), 10.
%D 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.
%H Pontus von Brömssen, <a href="/A000602/b000602.txt">Table of n, a(n) for n = 0..1000</a> (terms n = 0..60 from N. J. A. Sloane)
%H Jean-François Alcover, <a href="/A000602/a000602_1.txt">Mathematica program translated from N. J. A. Sloane's Maple program for A000022, A000200, A000598, A000602, A000678</a>
%H M. van Almsick, H. Dolhaine and H. Honig, <a href="https://doi.org/10.1021/ci990121m">Efficient algorithms to enumerate isomers and diamutamers with more than one type of substituent</a>, J. Chem. Info. and Computer Science, 40 (2000), 956-966.
%H Vijayakumar Ambat, <a href="/A000602/a000602.jpg">Article about OEIS in Malayalam that mentions this sequence</a>, Mathrubhumi (daily newspaper in Kerala State), circa Nov 20 2022.
%H R. Aringhieri, P. Hansen and F. Malucelli, <a href="http://citeseer.ist.psu.edu/aringhieri99chemical.html">Chemical Tree Enumeration Algorithms</a>, Report TR-99-09, Dept. Informatica, Univ. Pisa, 1999.
%H A. T. Balaban, J. W. Kennedy and L. V. Quintas, <a href="https://doi.org/10.1021/ed065p304">The number of alkanes having n carbons and a longest chain of length d</a>, J. Chem. Education, 65 (1988), 304-313.
%H H. Bottomley, <a href="/A000602/a000602.gif">Illustration of initial terms of A000022, A000200, A000602</a>
%H L. Bytautas and D. J. Klein, <a href="https://doi.org/10.1021/ci980095c">Chemical combinatorics for alkane-isomer enumeration and more</a>, J. Chem. Inf. Comput. Sci., 38 (1998), 1063-1078.
%H A. Cayley, <a href="/A000022/a000022.pdf">Über die analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen</a>, Chem. Ber. 8 (1875), 1056-1059. (Annotated scanned copy)
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 478
%H Alfred W. Francis, <a href="http://pubs.acs.org/doi/pdf/10.1021/ja01198a507">Numbers of Isomeric Alkylbenzenes</a>, J. Am. Chem. Soc., 69:6 (1947), pp. 1536-1537.
%H R. K. Guy, <a href="/A000602/a000602.pdf">Letter to N. J. A. Sloane, Mar. 1988</a>
%H F. Harary and R. Z. Norman, <a href="https://doi.org/10.1090/S0002-9939-1960-0111699-6">Dissimilarity characteristic theorems for graphs</a>, Proc. Amer. Math. Soc. 11 (1960), 332-334.
%H H. R. Henze and C. M. Blair, <a href="https://doi.org/10.1021/ja01359a034">The number of isomeric hydrocarbons of the methane series</a>, J. Amer. Chem. Soc., 53 (8) (1931), 3077-3085.
%H H. R. Henze and C. M. Blair, <a href="/A000601/a000601_1.pdf">The number of isomeric hydrocarbons of the methane series</a>, J. Amer. Chem. Soc., 53 (1931), 3077-3085. (Annotated scanned copy)
%H H. R. Henze and C. M. Blair, <a href="https://doi.org/10.1021/ja01329a033">The number of structurally isomeric Hydrocarbons of the Ethylene Series</a>, J. Amer. Chem. Soc., 55 (2) (1933), 680-686.
%H F. Hermann, <a href="/A000602/a000602_3.pdf">Ueber das Problem, die Anzahl der isomeren Paraffine der Formel C_n H_{2n+2} zu bestimmung</a>, Chem. Ber., 13 (1880), 792. [I (1880), Annotated scanned copy]
%H F. Hermann, <a href="/A000602/a000602_2.pdf">Ueber das Problem, die Anzahl der isomeren Paraffine der Formel C_n H_{2n+2} zu bestimmung/a>, Chem. Ber., 30 (1897), 2423-2426. [II (1897), Annotated scanned copy]
%H F. Hermann, <a href="/A000602/a000602_4.pdf">Entgegnung</a>, Chem. Ber., 31 (1898), 91. [III (1898), Annotated scanned copy]
%H Michael A. Kappler, <a href="http://www.daylight.com/meetings/emug04/Kappler/GenSmi.html">GENSMI: Exhaustive Enumeration of Simple Graphs.</a> Daylight CIS, Inc., EuroMUG '04;4-Nov 05 2004.
%H E. V. Konstantinova and M. V. Vidyuk, <a href="https://doi.org/10.1021/ci025659y">Discriminating tests of information and topological indices; animals and trees</a>; J. Chem. Inf. Comput. Sci., 43 (2003), 1860-1871.
%H J. Lederberg, <a href="/A000602/a000602_7.pdf">Letter to N. J. A. Sloane</a>, Aug 13 1971
%H J. Lederberg, <a href="/A000602/a000602_8.pdf">The topology of molecules</a>, in The Mathematical Sciences. Cambridge, Mass.: MIT Press, 1969, pages 37-51. [Annotated scanned copy]
%H J. Lederberg, <a href="/A000602/a000602_9.pdf">Dendral-64, I</a>, Report to NASA, Dec 1964 [Annotated scanned copy]
%H J. Lederberg, <a href="/A000602/a000602_10.pdf">Dendral-64, II</a>, Report to NASA, Dec 1965 [Annotated scanned copy]
%H J. Lederberg, <a href="/A000602/a000602_11.pdf">Dendral-64, III</a>, Report to NASA, Dec 1968 [Annotated scanned copy]
%H P. Leroux and B. Miloudi, <a href="http://www.labmath.uqam.ca/~annales/volumes/16-1/PDF/053-080.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Québec, Vol. 16, No. 1 (1992), pp. 53-80.
%H P. Leroux and B. Miloudi, <a href="/A000081/a000081_2.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
%H S. M. Losanitsch, <a href="https://doi.org/10.1002/cber.189703002144">Die Isomerie-Arten bei den Homologen der Paraffin-Reihe</a>, Chem. Ber. 30 (1897), 1917-1926.
%H S. M. Losanitsch, <a href="/A000602/a000602_1.pdf">Die Isomerie-Arten bei den Homologen der Paraffin-Reihe</a>, Chem. Ber. 30 (1897), 1917-1926. (Annotated scanned copy)
%H S. M. Losanitsch, <a href="/A000602/a000602_12.pdf">Bemerkungen zu der Hermasnnschen Mitteillung: Die Anzahl...</a>, Chem. Ber., 30 (1897), 3059-3060 [Annotated scanned copy]
%H A. Masoumi, M. Antoniazzi, and M. Soutchanski, <a href="http://www.cs.ryerson.ca/~mes/publications/MasoumiAntoniazziSoutchanskiModelOrganicChemistryPlanningOrganicSynthesis_GCAI2015.pdf">Modeling organic chemistry and planning organic synthesis</a>, GCAI 2015. Global Conference on Artificial Intelligence (2015), pp. 176-195.
%H W. R. Mueller et al., <a href="https://doi.org/10.1021/ci00066a011">Molecular topological index</a>, J. Chem. Inf. Comput. Sci., 30 (1990),160-163.
%H R. Otter, <a href="http://www.jstor.org/stable/1969046">The number of trees</a>, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
%H D. Perry, <a href="/A000602/a000602_6.pdf">The number of structural isomers of certain homologs of methane and methanol</a>, J. Amer. Chem. Soc. 54 (1932), 2918-2920. [Gives a(60) correctly] (Annotated scanned copy)
%H G. Polya, <a href="https://doi.org/10.1524/zkri.1936.93.1.415">Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen</a>, Zeit. f. Kristall., 93 (1936), 415-443
%H G. Polya, <a href="/A000598/a000598_3.pdf">Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen</a>, Zeit. f. Kristall., 93 (1936), 415-443. (Annotated scanned copy)
%H E. M. Rains and N. J. A. Sloane, <a href="https://cs.uwaterloo.ca/journals/JIS/cayley.html">On Cayley's Enumeration of Alkanes (or 4-Valent Trees)</a>, J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
%H R. C. Read, <a href="/A000598/a000598.pdf">The Enumeration of Acyclic Chemical Compounds</a>, pp. 25-61 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976. [Annotated scanned copy] See p. 28.
%H R. W. Robinson, F. Harary and A. T. Balaban, <a href="https://doi.org/10.1016/0040-4020(76)80049-X">Numbers of chiral and achiral alkanes and monosubstituted alkanes</a>, Tetrahedron 32 (3) (1976), 355-361.
%H R. W. Robinson, F. Harary and A. T. Balaban, <a href="/A000625/a000625.pdf">Numbers of chiral and achiral alkanes and monosubstituted alkanes</a>, Tetrahedron 32 (3) (1976), 355-361. (Annotated scanned copy)
%H Hugo Schiff, <a href="/A002094/a002094.pdf">Zur Statistik chemischer Verbindungen</a>, Berichte der Deutschen Chemischen Gesellschaft, Vol. 8, pp. 1542-1547, 1875. [Annotated scanned copy]
%H Nicholas I. Shepherd-Barron, <a href="https://arxiv.org/abs/1904.13344">Asymptotic period relations for Jacobian elliptic surfaces</a>, arXiv:1904.13344 [math.AG], 2019.
%H N. J. A. Sloane, <a href="/A000602/a000602.txt">Maple program and first 60 terms for A000022, A000200, A000598, A000602, A000678</a>
%H N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 5.
%H N. Trinajstich, Z. Jerievi, J. V. Knop, W. R. Muller and K. Szymanski, <a href="https://doi.org/10.1351/pac198855020379">Computer Generation of Isomeric Structures</a>, Pure & Appl. Chem., Vol. 55, No. 2, pp. 379-390, 1983.
%H Stephan Wagner, <a href="http://www.cs.sun.ac.za/~swagner/avwiener.pdf">On the average Wiener index of degree-restricted trees</a>
%H Sylvia Wenmackers, <a href="http://www.sylviawenmackers.be/blog/2015/08/huiswerk-met-bijna-twintig-jaar-vertraging/">Huiswerk (met bijna twintig jaar vertraging)</a> (in Dutch), 2015.
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F a(n) = A010372(n) + A010373(n/2) for n even, a(n) = A010372(n) for n odd.
%F 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 + ...
%F 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
%e 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)
%p A000602 := proc(n)
%p if n=0 then
%p 1
%p else
%p A000022(n)+A000200(n);
%p end if;
%p end proc:
%t n = 40; (* algorithm from Rains and Sloane *)
%t S3[f_,h_,x_] := f[h,x]^3/6 + f[h,x] f[h,x^2]/2 + f[h,x^3]/3;
%t 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 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];
%t 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 *)
%t b[n_, i_, t_, k_] := b[n,i,t,k] = If[i<1, 0, Sum[Binomial[b[i-1,i-1,
%t k,k] + j-1, j]* b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
%t b[0, i_, t_, k_] = 1; m = 3; (* m = maximum children *) n = 40;
%t gf[x_] = 1 + Sum[b[j-1,j-1,m,m]x^j,{j,1,n}]; (* G.f. for A000598 *)
%t ci[x_] = SymmetricGroupIndex[m+1, x] /. x[i_] -> gf[x^i];
%t CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x],
%t {x, 0, n}]],x] (* _Robert A. Russell_, Jan 19 2023 *)
%Y Column k=4 of A144528.
%Y A000602 = A000022 + A000200 for n>0.
%Y Cf. A000598, A000625, A000628, A067608, A067609, A067610.
%K nonn,easy,core,nice
%O 0,5
%A _N. J. A. Sloane_
%E Additional comments from Steve Strand (snstrand(AT)comcast.net), Aug 20 2003
|
