A000625 - OEIS

%I M1402 N0546 #73 Feb 17 2019 20:45:45

%S 1,1,1,2,5,11,28,74,199,551,1553,4436,12832,37496,110500,328092,

%T 980491,2946889,8901891,27012286,82300275,251670563,772160922,

%U 2376294040,7333282754,22688455980,70361242924,218679264772,681018679604,2124842137550,6641338630714,20792003301836

%N Number of n-node steric rooted ternary trees; number of n carbon alkyl radicals C(n)H(2n+1) taking stereoisomers into account.

%C Nodes are unlabeled, each node has out-degree <= 3.

%C Steric, or including stereoisomers, means that the children of a node are taken in a certain cyclic order. If the children are rotated it is still the same tree, but any other permutation yields a different tree. See A000598 for the analogous sequence with stereoisomers not counted.

%C Other descriptions of this sequence: steric planted trees with n nodes; total number of monosubstituted alkanes C(n)H(2n+1)-X with n carbon atoms.

%C Let the entries in the nine columns of Blair and Henze's Table I (JACS 54 (1932), p. 1098) be denoted by Ps(n), Pn(n), Ss(n), Sn(n), Ts(n), Tn(n), As(n), An(n), T(n) respectively (here P = Primary, S = Secondary, T = Tertiary, s = stereoisomers, n = non-stereoisomers and the last column T(n) gives total).

%C Then Ps (and As) = A000620, Pn (and An, Sn) = A000621, Ss = A000622, Ts = A000623, Tn = A000624, T = this sequence. Recurrences generating these sequences are given in the Maple program in A000620.

%D J. K. Percus, Combinatorial Methods, Lecture Notes, 1967-1968, Courant Institute, New York University, 212pp. See pp. 64-65.

%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="/A000625/b000625.txt">Table of n, a(n) for n = 0..1930</a> (first 200 terms from T. D. Noe)

%H C. M. Blair and H. R. Henze, <a href="http://dx.doi.org/10.1021/ja01342a036">The number of stereoisomeric and non-stereoisomeric mono-substitution products of the paraffins</a>, J. Amer. Chem. Soc., 54 (3) (1932), 1098-1106.

%H C. M. Blair and H. R. Henze, <a href="/A000620/a000620.pdf">The number of stereoisomeric and non-stereoisomeric mono-substitution products of the paraffins</a>, J. Amer. Chem. Soc., 54 (3) (1932), 1098-1105. (Annotated scanned copy)

%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 G. Polya, <a href="http://dx.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, Eq. (25).

%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, Eq. (25). (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. 44.

%H R. W. Robinson, F. Harary and A. T. Balaban, <a href="http://dx.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 <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) = 1 + x + x^2 + 2*x^3 + 5*x^4 + 11*x^5 + 28*x^6 + ... satisfies A(x) = 1 + x*(A(x)^3 + 2*A(x^3))/3.

%F a(0) = a(1) = 1; a(n+1) = 2*a(n/3)/3 + (Sum_{j=1..n} j*a(j)*(Sum_{i=1..n-j} a(i)*a(n-j-i)))/n for n >= 1, where a(k) = 0 if k not an integer (essentially eq (4) in the Robinson et al. paper). - _Emeric Deutsch_, May 16 2004

%F a(n) ~ c * b^n / n^(3/2), where b = 3.287112055584474991259... (see A239803), c = 0.346304267394183622435... (see A239810). - _Vaclav Kotesovec_, Mar 27 2014

%p A := 1; f := proc(n) global A; coeff(series( 1+(1/3)*x*(A^3+2*subs(x=x^3,A)), x, n+1), x, n); end; for n from 1 to 50 do A := series(A+f(n)*x^n,x,n +1); od: A;

%p A000625 := proc(n)

%p     local j,i,a ;

%p     option remember;

%p     if n <= 1 then

%p         1 ;

%p     else

%p         a :=0 ;

%p         for j from 1 to n-1 do

%p             a := a+ j*procname(j)*add(procname(i)*procname(n-j-i-1),i=0..n-j-1) ;

%p         end do:

%p         if modp(n-1,3) = 0 then

%p             a := a+2*(n-1)*procname((n-1)/3)/3 ;

%p         end if;

%p         a/ (n-1) ;

%p     end if;

%p end proc:

%p seq(A000625(n),n=0..30) ;

%t m = 31; c[0] = 1; gf[x_] = Sum[c[k] x^k, {k, 0, m}]; cc = Array[c, m]; coes = CoefficientList[ Series[gf[x] - 1 - (x*(gf[x]^3 + 2*gf[x^3])/3), {x, 0, m}], x] // Rest; Prepend[cc /. Solve[ Thread[ coes == 0], cc][[1]], 1]

%t (* _Jean-François Alcover_, Jun 24 2011 *)

%t a[0] = a[1] = 1; a[n_Integer] := a[n] = (Sum[j*a[j]*Sum[a[i]*a[n-i-j-1], {i, 0, n-j-1}], {j, 1, n-1}] + (2/3)*(n-1)*a[(n-1)/3])/(n-1); a[_] = 0; Table[a[n], {n, 0, 31}] (* _Jean-François Alcover_, Apr 21 2016, after _Emeric Deutsch_ *)

%t terms = 32; A[_] = 0; Do[A[x_] = Normal[1 + x*(A[x]^3 + 2*A[x^3])/3 + O[x]^terms], terms]; CoefficientList[A[x], x] (* _Jean-François Alcover_, Apr 22 2016, updated Jan 11 2018 *)

%o (PARI) a(n) = if(n, my(v=vector(n+1)); v[1]=1; v[2]=1; for(k=1, n-1, v[k+2] = sum(j=1, k, j*v[j+1]*(sum(i=0, k-j, v[i+1]*v[k-j-i+1])))/k + (2/3)*if(k%3, 0, v[k/3+1])); v[n+1], 1) \\ _Jianing Song_, Feb 17 2019

%Y Cf. A000598, A000602, A000620-A000624, A000628, A010732, A010733, A086194, A086200, A239803, A239810.

%K nonn,easy,nice

%O 0,4

%A _N. J. A. Sloane_

%E Additional comments from Bruce Corrigan, Nov 04 2002