|
%I M0977 N0366 #28 Sep 16 2018 16:58:36
%S 1,1,0,1,1,1,2,4,5,10,19,36,68,138,277,581,1218,2591,5545,12026,26226,
%T 57719,127685,284109,634919,1425516,3212890,7269605,16504439,37592604,
%U 85876345,196717882,451768247,1039990913,2399476030,5547849750
%N Number of centered 3-valent (or boron, or binary) trees with n nodes.
%D A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 451).
%D R. C. Read, personal communication.
%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 E. M. Rains and N. J. A. Sloane, <a href="https://cs.uwaterloo.ca/journals/JIS/cayley.html">On Cayley's Enumeration of Alkanes (or 4-Valent Trees)</a>, J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
%H R. C. Read, <a href="/A000684/a000684_1.pdf">Letter to N. J. A. Sloane, Oct. 29, 1976</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%t n = 50; (* algorithm from Rains and Sloane *)
%t S2[f_,h_,x_] := f[h,x]^2/2 + f[h,x^2]/2;
%t S3[f_,h_,x_] := f[h,x]^3/6 + f[h,x] f[h,x^2]/2 + f[h,x^3]/3;
%t T[-1,z_] := 1; T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S2[T,h-1,z]z, z], n+1];
%t Sum[Take[CoefficientList[z^(n+1) + S3[T,h-1,z]z - S3[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] (* _Robert A. Russell_, Sep 15 2018 *)
%Y A000672 = A000673 + A000675. Cf. A000022, A000200, A000602.
%K nonn,easy,nice
%O 0,7
%A _N. J. A. Sloane_
|
