A002094 -id:A002094 - cp's OEIS frontend

A000598 Number of rooted ternary trees with n nodes; number of n-carbon alkyl radicals C(n)H(2n+1) ignoring stereoisomers.

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241, 48865, 124906, 321198, 830219, 2156010, 5622109, 14715813, 38649152, 101821927, 269010485, 712566567, 1891993344, 5034704828, 13425117806, 35866550869, 95991365288, 257332864506, 690928354105

Offset: 0

N. J. A. Sloane

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 hydrogen atoms 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.
The number of aliphatic amino acids with n carbon atoms in the side chain, and no rings or double bonds, has the same growth as this sequence. - Konrad Gruetzmann, Aug 13 2012

			From _Joerg Arndt_, Feb 25 2017: (Start)
The a(5) = 8 rooted trees with 5 nodes and out-degrees <= 3 are:
:         level sequence    out-degrees (dots for zeros)
:     1:  [ 0 1 2 3 4 ]    [ 1 1 1 1 . ]
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]    [ 1 1 2 . . ]
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]    [ 1 2 1 . . ]
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]    [ 2 1 1 . . ]
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]    [ 1 3 . . . ]
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]    [ 2 2 . . . ]
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]    [ 2 1 . 1 . ]
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]    [ 3 1 . . . ]
:  O--o--o
:  .--o
:  .--o
(End)

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.
Knop, Mueller, Szymanski and Trinajstich, Computer generation of certain classes of molecules.
D. Perry, The number of structural isomers ..., J. Amer. Chem. Soc. 54 (1932), 2918-2920.
G. Polya, Mathematical and Plausible Reasoning, Vol. 1 Prob. 4 pp. 85; 233.
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).

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000 (first 200 terms from N. J. A. Sloane)
Jean-François Alcover, Mathematica program translated from N. J. A. Sloane's Maple program for A000022, A000200, A000598, A000602, A000678.
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 (1988), 304-313.
A. Cayley, On the mathematical theory of isomers, Phil. Mag. vol. 67 (1874), 444-447 (a(6) is wrong). (Annotated scanned copy)
Frederic Chyzak, Enumerating alcohols and other classes of chemical molecules.
Maximilian Fichtner, K. Voigt, and S. Schuster, The tip and hidden part of the iceberg: Proteinogenic and non-proteinogenic aliphatic amino acids, Biochimica et Biophysica Acta (BBA)-General, 2016, Volume 1861, Issue 1, Part A, January 2017, pp. 3258-3269.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 478.
K. Grützmann, S. Böcker, and S. Schuster, Combinatorics of aliphatic amino acids, Naturwissenschaften, Vol. 98, No. 1, 79-86, 2011.
H. R. Henze and C. M. Blair, The number of structurally isomeric alcohols of the methanol series, J. Amer. Chem. Soc., 53 (8) (1931), 3042-3046.
H. R. Henze and C. M. Blair, The number of structurally isomeric alcohols of the methanol series, J. Amer. Chem. Soc., 53 (8) (1931), 3042-3045. (Annotated scanned copy)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1.
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)
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 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; Table I, line 2.
G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443; Table I, line 2. (Annotated scanned copy)
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. 20, Eq. (G); p. 27, Eq. 2.1.
Marko Riedel, Chris Grossack, Counting trees with a degree constraint, Math StackExchange.
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]
N. J. A. Sloane, Maple program and first 60 terms for A000022, A000200, A000598, A000602, A000678.
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.
Wikipedia, Polya's enumeration theorem.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000599, A000600, A000602, A000625, A000628, A000678, A010372, A010373, A086194, A086200, A261340.
Cf. A292553, A292554, A292555, A292556.
Cf. A000081, A001190, A014591, A032305, A295461, A298118, A298120, A298204, A298422, A298426.
Column k=3 of A299038.

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)];

m = 45; Clear[f]; f[1, x_] := 1+x; f[n_, x_] := f[n, x] = Expand[1+x*(f[n-1, x]^3/6 + f[n-1, x^2]*f[n-1, x]/2 + f[n-1, x^3]/3)][[1 ;; n]]; Do[f[n, x], {n, 2, m}]; CoefficientList[f[m, x], x]
(* second program (after N. J. A. Sloane): *)
m = 45; gf[] = 0; Do[gf[z] = 1 + z*(gf[z]^3/6 + gf[z^2]*gf[z]/2 + gf[z^3]/3) + O[z]^m // Normal, m]; CoefficientList[gf[z], z]  (* Jean-François Alcover, Sep 23 2014, updated Jan 11 2018 *)
b[0, i_, t_, k_] = 1; m = 3; (* m = maximum children *)
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]}]];
Join[{1},Table[b[n-1, n-1, m, m], {n, 1, 35}]] (* Robert A. Russell, Dec 27 2022 *)

seq(n)={my(g=O(x)); for(n=1, n, g = 1 + x*(g^3/6 + subst(g,x,x^2)*g/2 + subst(g,x,x^3)/3) + O(x^n)); Vec(g)} \\ Andrew Howroyd, May 22 2018

def seq(n):
    B = PolynomialRing(QQ, 't', n+1);t = B.gens()
    R. = B[[]]
    T = sum([t[i] * z^i for i in range(1,n+1)]) + O(z^(n+1))
    lhs, rhs = T, 1 + z/6 * (T(z)^3 + 3*T(z)*T(z^2) + 2*T(z^3))
    I = B.ideal([lhs.coefficients()[i] - rhs.coefficients()[i] for i in range(n)])
    return [I.reduce(t[i]) for i in range(1,n+1)]
seq(33) # Chris Grossack, Mar 31 2025

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

a(n) ~ c * d^n / n^(3/2), where d = 1/A261340 = 2.8154600331761507465266167782426995425365065396907..., c = 0.517875906458893536993162356992854345458168348098... . - Vaclav Kotesovec, Aug 15 2015

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

A000602 Number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

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.

			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)

Klemens Adam, Die Anzahlbestimmung der isomeren Alkane, 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 Isomer Combinatorics: Stereostructure enumeration and graph-invariant and molecular-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.

Pontus von Brömssen, Table of n, a(n) for n = 0..1000 (terms n = 0..60 from N. J. A. Sloane)
Jean-François Alcover, Mathematica program translated from N. J. A. Sloane's Maple program for A000022, A000200, A000598, A000602, A000678
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 (1988), 304-313.
H. Bottomley, Illustration of initial terms of A000022, A000200, A000602
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 Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen, Chem. Ber. 8 (1875), 1056-1059. (Annotated scanned copy)
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.
R. K. Guy, Letter to N. J. A. Sloane, Mar. 1988
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, Ueber das Problem, die Anzahl der isomeren Paraffine der Formel C_n H_{2n+2} zu bestimmung, Chem. Ber., 30 (1897), 2423-2426. [II (1897), Annotated scanned copy]
F. Hermann, Entgegnung, Chem. Ber., 31 (1898), 91. [III (1898), Annotated scanned copy]
Lorentz Jäntschi and Lavinia-Lorena Pruteanu, Geometry of C_32 cyclic polyyne and some of its clusters, Carpathian J. Math. (2025) Vol. 41, No. 2, 371-391. See p. 371.
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
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, Maple program and first 60 terms for A000022, A000200, A000598, A000602, A000678
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.
Stephan Wagner, On the average Wiener index of degree-restricted trees
Sylvia Wenmackers, Huiswerk (met bijna twintig jaar vertraging) (in Dutch), 2015.
Index entries for sequences related to trees
Index entries for "core" sequences

Column k=4 of A144528.
A000602 = A000022 + A000200 for n>0.
Cf. A000598, A000625, A000628, A067608, A067609, A067610.

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

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

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

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

A000642 a(1)=0; for n>1, a(n) = number of isomeric hydrocarbons of the acetylene series with carbon content n.

Original entry on oeis.org

0, 1, 1, 2, 3, 7, 14, 32, 72, 171, 405, 989, 2426, 6045, 15167, 38422, 97925, 251275, 648061, 1679869, 4372872, 11428365, 29972078, 78859809, 208094977, 550603722, 1460457242, 3882682803, 10344102122, 27612603765, 73844151259, 197818389539

Offset: 1

N. J. A. Sloane

The former definition was "Number of alkyl derivatives of acetylene X^{II} C_n H_{2n+2} with n carbon atoms" with offset 0.

a(n+1) is the number of rooted trees with n nodes and out-degree <= 2 on the root and out-degree <= 3 on all other nodes. See illustration of initial terms. - Washington Bomfim, Nov 28 2020

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

T. D. Noe, Table of n, a(n) for n = 1..201 (offset adapted by _Georg Fischer_, Jan 31 2019)
Washington Bomfim, Illustration of initial terms
D. D. Coffman, C. M. Blair and H. R. Henze, The number of structurally isomeric hydrocarbons of the acetylene series, J. Amer. Chem. Soc., 55 (1933), 252-253.
D. D. Coffman, C. M. Blair and H. R. Henze, The number of structurally isomeric hydrocarbons of the acetylene series, J. Amer. Chem. Soc., 55 (1933), 252-253. (Annotated scanned copy)
Jean-Loup Faulon, Donald P. Visco Jr., Diana Roe, Enumerating Molecules, In: Reviews in Computational Chemistry Vol. 21, Ed. K. Lipkowitz, Wiley-VCH, 2005.
R. J. Mathar, Illustration for graphs up to 6 carbons
G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443; line 8 of Table I, "R" of Table IV.
G. Polya, Algebraische Berechnung der Anzahl der Isomeren einiger organischer Verbindungen, Zeit. f. Kristall., 93 (1936), 415-443; line 8 of Table I, "R" of Table IV. (Annotated scanned copy)
R. C. Read, Some recent results in chemical enumeration, Lect. Notes Math. 303 (1972), 243-259.
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.
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.
Index entries for sequences related to rooted trees

Cf. A000598, A002094.

terms = 32; B[] = 0; Do[B[x] = 1 + (1/6)*x*(B[x]^3 + 3*B[x]*B[x^2] + 2*B[x^3]) + O[x]^terms // Normal, terms];
A[x_] = (1/2)*x*(B[x^2] + B[x]^2) + O[x]^terms;
CoefficientList[A[x], x] (* Jean-François Alcover, Jun 28 2012, updated Jan 10 2018 *)

\\ here G(n) is A000598 as g.f.
G(n)={my(g=O(x)); for(n=1, n, g = 1 + x*(g^3/6 + subst(g, x, x^2)*g/2 + subst(g, x, x^3)/3) + O(x^n)); g}
seq(n)={my(g=G(n)); Vec(subst(g,x,x^2) + g^2, -(n+1))/2} \\ Andrew Howroyd, Nov 28 2020

G.f.: A(x)=(1/2)*x*(B(x^2)+B(x)^2), where B(x) = g.f. for A000598.

a(n) ~ c * d^n / n^(3/2), where d = 1/A261340 = 2.815460033176... and c = 0.13833565403175156418512996853... - Vaclav Kotesovec, Feb 11 2019

I changed the definition and offset so as to agree with Coffman et al. (1933). - N. J. A. Sloane, Jan 13 2019

A000631 Number of ethylene derivatives with n carbon atoms.

Original entry on oeis.org

1, 1, 3, 5, 13, 27, 66, 153, 377, 914, 2281, 5690, 14397, 36564, 93650, 240916, 623338, 1619346, 4224993, 11062046, 29062341, 76581151, 202365823, 536113477, 1423665699, 3788843391, 10103901486, 26995498151, 72253682560, 193706542776

Offset: 2

N. J. A. Sloane

nonn

Number of structural isomers of alkenes C_n H_{2n} with n carbon atoms.
Number of unicyclic graphs of n nodes where a double-edge replaces the cycle, [A217781], end-points of the double-edge of out-degrees <= 2, other nodes having out-degrees <= 3.
Number of rooted trees on n+1 nodes where the root has degree 2, the 2 children of the root have out-degrees <= 2, and the other nodes have out-degrees <= 3.
See illustration of initial terms. - Washington Bomfim, Nov 30 2020

J. L. Faulon, D. Visco and D. Roe, Enumerating Molecules, In: Reviews in Computational Chemistry Vol. 21, Ed. K. Lipkowitz, Wiley-VCH, 2005.
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).

Andrew Howroyd, Table of n, a(n) for n = 2..500
Washington Bomfim, Illustration of initial terms
J. L. Faulon, D. Visco and D. Roe, Enumerating Molecules, In: Reviews in Computational Chemistry Vol. 21, Ed. K. Lipkowitz, Wiley-VCH, 2005.
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.
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-685. (Annotated scanned copy)
H. R. Henze and C. M. Blair, The number of structural isomers of the more important types of aliphatic compounds, J. Amer. Chem. Soc., 56 (1) (1934), 157-157.
C.-W. Lam, A Mathematical Relationship between the Number of Isomers of Alkenes and Alkynes: A Result Established from the Enumeration of Isomers of Alkenes from Alky Biradicals, J. Math. Chem., 23, 421 (1998).
R. J. Mathar, Illustration for graphs up to 6 carbons
R. C. Read, Some recent results in chemical enumeration, Lect. Notes Math. 303 (1972), 243-259.
R. C. Read, Some recent results in chemical enumeration, Preprint, circa 1972. (Annotated scanned copy)
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.
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.
Index entries for sequences related to rooted trees

Cf. A000642, A000598, A027852 (out-degrees of nodes not limited).

\\ Here G(n) is A000598 as g.f., h is A000642.
seq(n)={my(g=G(n), h=(subst(g, x, x^2) + g^2)/2); Vec(subst(h, x, x^2) + h^2)/2} \\ Andrew Howroyd, Dec 01 2020

a(n) = b(1)b(n-1) + b(2)b(n-2) + b(3)b(n-3) + ... + b(n/2)(b(n/2) + 1)/2 when n is even or b(1)b(n-1) + b(2)b(n-2) + b(3)b(n-3) + ... + b((n-1)/2)b((n + 1)/2) when n is odd, where b(n) = A000642(n). - Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 24 2008
a(n) = Sum_{k=1..(n-1)/2}( f(k) * f(n-k) ) + [n mod 2 = 0] * ( f(n/2)^2 + f(n/2) ) / 2 where f(n) = A000642(n+1). - Washington Bomfim, Nov 29 2020
G.f.: (g(x^2) + g(x)^2)/2 where x*g(x) is the g.f. of A000642. - Andrew Howroyd, Dec 01 2020

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Feb 24 2008

A261340 Decimal expansion of the radius of convergence of the generating function of A000598, the number of rooted ternary trees of n vertices.

Original entry on oeis.org

3, 5, 5, 1, 8, 1, 7, 4, 2, 3, 1, 4, 3, 7, 7, 3, 9, 2, 8, 8, 2, 2, 4, 4, 4, 7, 3, 6, 4, 7, 6, 3, 2, 6, 3, 6, 7, 0, 8, 7, 4, 6, 9, 5, 4, 1, 7, 5, 3, 2, 2, 1, 3, 4, 2, 3, 8, 1, 2, 9, 4, 9, 9, 7, 1, 2, 8, 0, 0, 1, 8, 0, 5, 7, 5, 5, 5, 7, 8, 2, 8, 8, 6, 7, 9, 8, 1, 3, 8, 1, 0, 8, 2, 4, 1, 6, 7

Offset: 0

Jean-François Alcover, Aug 15 2015

			0.35518174231437739288224447364763263670874695417532...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 5.6 Otter's tree enumeration constants, p. 298.

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; p. 478.

Cf. A000598, A000642, A002094, A121331, A244399.

digits = 97; m = 2 digits + 10; For[gf = 0; i = 0, i <= m, i++, gf = Series[1 + x*(gf^3/6 + (gf /. x -> x^2)*gf/2 + (gf /. x -> x^3)/3), {x, 0, m + 1}] // Normal];
g[r_] := Module[{r2, r3, X, ym}, r2 = gf /. x -> r^2; r3 = gf /. x -> r^3; X[y_] = (y - 1)/(y^3/6 + r2*y/2 + r3/3); ym = y /. FindRoot[X'[y] == 0, {y, 2}, WorkingPrecision -> digits + 5]; X[ym]]; rho = FixedPoint[g, 1/3, SameTest -> (Abs[#1 - #2] < 10^-digits &)]; RealDigits[rho, 10, digits] // First

More digits from Vaclav Kotesovec, Aug 15 2015

More digits and Mma code updated by Jean-François Alcover, Apr 18 2016

A317722 Number of connected graphs with n nodes and no node a member of more than one cycle.

Original entry on oeis.org

1, 1, 2, 3, 8, 18, 56, 165, 563, 1937, 7086, 26396, 101383, 395821, 1573317, 6335511, 25825861, 106344587, 441919711, 1851114466, 7809848543, 33162241547, 141636863809, 608144007472, 2623832050460, 11370768445682, 49478287669666, 216109924932762, 947216963083175

Offset: 0

R. J. Mathar, Aug 05 2018

nonn

The sequence counts connected, loopless, undirected graphs with cycles that do not overlap (cycles have length >= 2), which means any pair of cycles does not have common edges or nodes.
Examples of these graphs are the trees (A000055), the unicyclic graphs (A001429, A002094), or the graphs with cycles without chords.
The concept is both narrower and wider than the concept for Husimi trees, because cycles in Husimi trees may share nodes (but not edges), and because cycles in Husimi trees need to have length >= 3.
There is a mapping/contraction of these graphs to trees: replace each cycle by a single node, attaching all edges that enter a node in the cycle to that node. That tree associated with the graph could be called the skeleton tree.
By reversing that surjection of the graphs to trees, we may generate our graphs with non-overlapping cycles by generating the set of weighted trees (A303841) and replacing the nodes by cycles of lengths that equals their weight.

Andrew Howroyd, Table of n, a(n) for n = 0..500
R. J. Mathar, Counting connected graphs without overlapping cycles, arXiv:1808.06264 [math.CO] (2018), series c(n).
R. J. Mathar, Illustration of the graphs up to n=6

Cf. A036250, A381468 (without 2-cycles).

EulerMTS(p)={my(n=serprec(p,x)-1,vars=variables(p)); exp(sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i))}
raise(p,d) = {my(n=serprec(p,x)-1); substvec(p + O(x^(n\d+1)), [x, y], [x^d,y^d])}
R(n,y)={my(g=x+O(x^2)); for(n=2, n, my(p=x*EulerMTS(g), p2=raise(p,2)); g=p + p*y*(p/(1 - p) + (p + p2)/(1 - p2))/2); g}
G(n,y=1)={my(g=R(n,y), p = x*EulerMTS(g) + O(x*x^n));
  my( r=((1 + p)^2/(1 - raise(p,2)) - 1)/2 );
  my( c=-sum(d=1, n, eulerphi(d)/d*log(raise(1-p,d))) );
  1 + p + (raise(g,2) - g^2 + y*(r + c - 2*p))/2 }
{ Vec(G(30)) } \\ Andrew Howroyd, Feb 25 2025

a(n) >= A036250(n).

a(5) corrected. - R. J. Mathar, Aug 12 2018

cp's OEIS Frontend

A000598 Number of rooted ternary trees with n nodes; number of n-carbon alkyl radicals C(n)H(2n+1) ignoring stereoisomers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A000602 Number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000642 a(1)=0; for n>1, a(n) = number of isomeric hydrocarbons of the acetylene series with carbon content n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A000631 Number of ethylene derivatives with n carbon atoms.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A261340 Decimal expansion of the radius of convergence of the generating function of A000598, the number of rooted ternary trees of n vertices.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A317722 Number of connected graphs with n nodes and no node a member of more than one cycle.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions