|
%I M1146 N0436 N1341 #148 Mar 22 2024 08:58:16
%S 1,1,1,2,4,8,17,39,89,211,507,1238,3057,7639,19241,48865,124906,
%T 321198,830219,2156010,5622109,14715813,38649152,101821927,269010485,
%U 712566567,1891993344,5034704828,13425117806,35866550869,95991365288,257332864506,690928354105
%N Number of rooted ternary trees with n nodes; number of n-carbon alkyl radicals C(n)H(2n+1) ignoring stereoisomers.
%C Number of unlabeled rooted trees in which each node has out-degree <= 3.
%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 A000625 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 out-degree is then <= 3.
%C Other descriptions of this sequence: quartic planted trees with n nodes; ternary rooted trees with n nodes and height at most 3.
%C 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
%D N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 62 (quoting Cayley, who is wrong).
%D A. Cayley, On the mathematical theory of isomers, Phil. Mag. vol. 67 (1874), 444-447 (a(6) is wrong).
%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 R. A. Fisher, Contributions to Mathematical Statistics, Wiley, 1950, 41.397.
%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 Knop, Mueller, Szymanski and Trinajstich, Computer generation of certain classes of molecules.
%D D. Perry, The number of structural isomers ..., J. Amer. Chem. Soc. 54 (1932), 2918-2920.
%D G. Polya, Mathematical and Plausible Reasoning, Vol. 1 Prob. 4 pp. 85; 233.
%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).
%H Vaclav Kotesovec, <a href="/A000598/b000598.txt">Table of n, a(n) for n = 0..1000</a> (first 200 terms 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 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 A. Cayley, <a href="/A000598/a000598_1.pdf">On the mathematical theory of isomers</a>, Phil. Mag. vol. 67 (1874), 444-447 (a(6) is wrong). (Annotated scanned copy)
%H Frederic Chyzak, <a href="http://algo.inria.fr/libraries/autocomb/Polya-html/Polya.html">Enumerating alcohols and other classes of chemical molecules</a>.
%H Maximilian Fichtner, K. Voigt, and S. Schuster, <a href="https://doi.org/10.1016/j.bbagen.2016.08.008">The tip and hidden part of the iceberg: Proteinogenic and non-proteinogenic aliphatic amino acids</a>, Biochimica et Biophysica Acta (BBA)-General, 2016, Volume 1861, Issue 1, Part A, January 2017, pp. 3258-3269.
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 478.
%H K. Grützmann, S. Böcker, and S. Schuster, <a href="https://doi.org/10.1007/s00114-010-0743-2">Combinatorics of aliphatic amino acids</a>, Naturwissenschaften, Vol. 98, No. 1, 79-86, 2011.
%H H. R. Henze and C. M. Blair, <a href="https://doi.org/10.1021/ja01359a027">The number of structurally isomeric alcohols of the methanol series</a>, J. Amer. Chem. Soc., 53 (8) (1931), 3042-3046.
%H H. R. Henze and C. M. Blair, <a href="/A000598/a000598_2.pdf">The number of structurally isomeric alcohols of the methanol series</a>, J. Amer. Chem. Soc., 53 (8) (1931), 3042-3045. (Annotated scanned copy)
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1">Encyclopedia of Combinatorial Structures 1</a>.
%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 Camden A. Parks and James B. Hendrickson, <a href="http://pubs.acs.org/doi/pdf/10.1021/ci00002a021">Enumeration of monocyclic and bicyclic carbon skeletons</a>, J. Chem. Inf. Comput. Sci., vol. 31, 334-339 (1991).
%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; Table I, line 2.
%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; Table I, line 2. (Annotated scanned copy)
%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. 20, Eq. (G); p. 27, Eq. 2.1.
%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 N. J. A. Sloane, <a href="/A000602/a000602.txt">Maple program and first 60 terms for A000022, A000200, A000598, A000602, A000678</a>.
%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 Wikipedia, <a href="http://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem">Polya's enumeration theorem</a>.
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F G.f. A(x) satisfies A(x) = 1 + (1/6)*x*(A(x)^3 + 3*A(x)*A(x^2) + 2*A(x^3)).
%F a(n) ~ c * d^n / n^(3/2), where d = 1/A261340 = 2.8154600331761507465266167782426995425365065396907..., c = 0.517875906458893536993162356992854345458168348098... . - _Vaclav Kotesovec_, Aug 15 2015
%e From _Joerg Arndt_, Feb 25 2017: (Start)
%e The a(5) = 8 rooted trees with 5 nodes and out-degrees <= 3 are:
%e : level sequence out-degrees (dots for zeros)
%e : 1: [ 0 1 2 3 4 ] [ 1 1 1 1 . ]
%e : O--o--o--o--o
%e :
%e : 2: [ 0 1 2 3 3 ] [ 1 1 2 . . ]
%e : O--o--o--o
%e : .--o
%e :
%e : 3: [ 0 1 2 3 2 ] [ 1 2 1 . . ]
%e : O--o--o--o
%e : .--o
%e :
%e : 4: [ 0 1 2 3 1 ] [ 2 1 1 . . ]
%e : O--o--o--o
%e : .--o
%e :
%e : 5: [ 0 1 2 2 2 ] [ 1 3 . . . ]
%e : O--o--o
%e : .--o
%e : .--o
%e :
%e : 6: [ 0 1 2 2 1 ] [ 2 2 . . . ]
%e : O--o--o
%e : .--o
%e : .--o
%e :
%e : 7: [ 0 1 2 1 2 ] [ 2 1 . 1 . ]
%e : O--o--o
%e : .--o--o
%e :
%e : 8: [ 0 1 2 1 1 ] [ 3 1 . . . ]
%e : O--o--o
%e : .--o
%e : .--o
%e (End)
%p 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);
%p [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;
%p spec := [S, {Z=Atom, S=Union(Z, Prod(Z, Set(S, card=3)))}, unlabeled]: [seq(combstruct[count](spec, size=n), n=0..20)];
%t 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]
%t (* second program (after _N. J. A. Sloane_): *)
%t 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 *)
%t b[0, i_, t_, k_] = 1; m = 3; (* m = maximum children *)
%t b[n_,i_,t_,k_]:= b[n,i,t,k]= If[i<1,0,
%t Sum[Binomial[b[i-1, i-1, k, k] + j-1, j]*
%t b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
%t Join[{1},Table[b[n-1, n-1, m, m], {n, 1, 35}]] (* _Robert A. Russell_, Dec 27 2022 *)
%o (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
%Y Cf. A000599, A000600, A000602, A000625, A000628, A000678, A010372, A010373, A086194, A086200, A261340.
%Y Cf. A292553, A292554, A292555, A292556.
%Y Cf. A000081, A001190, A014591, A032305, A295461, A298118, A298120, A298204, A298422, A298426.
%Y Column k=3 of A299038.
%K nonn,easy,nice,eigen
%O 0,4
%A _N. J. A. Sloane_
%E Additional comments from Steve Strand (snstrand(AT)comcast.net), Aug 20 2003
|
