This site is supported by donations to The OEIS Foundation.

 Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000598 Number of rooted ternary trees with n nodes; number of n-carbon alkyl radicals C(n)H(2n+1) ignoring stereoisomers. (Formerly M1146 N0436 N1341) 86
 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 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS 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 REFERENCES 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). 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. LINKS N. J. A. Sloane and Vaclav Kotesovec, Table of n, a(n) for n = 0..1000 (first 200 terms from N. J. A. Sloane) 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. 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, 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, Pages 3258-3269. P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 478 K. Grützmann, S. Böcker, S. Schuster, Combinatorics of aliphatic amino acids, Naturwissenschaften, Vol. 98, No. 1, 79-86, 2011. H. R. Henze, 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, 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. 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] Wikipedia, Polya's enumeration theorem FORMULA 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 EXAMPLE 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) MAPLE 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)]; MATHEMATICA 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 *) PROG (PARI) 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 CROSSREFS 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. Sequence in context: A241671 A036375 A036376 * A003008 A185352 A054199 Adjacent sequences:  A000595 A000596 A000597 * A000599 A000600 A000601 KEYWORD nonn,easy,nice,eigen 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 13 15:03 EST 2018. Contains 318086 sequences. (Running on oeis4.)