A000598 - OEIS

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

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

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.

Hugo Schiff, Zur Statistik chemischer Verbindungen, Berichte der Deutschen Chemischen Gesellschaft, Vol. 8, pp. 1542-1547, 1875. [Annotated scanned copy]

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.

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

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 := 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]

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

(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

Cf. A000599, A000600, A000602, A000625, A000628, A000678, A010372, A010373, A086194, A086200, A261340.

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