login
Number of bicentered 3-valent (or boron, or binary) trees with n nodes.
(Formerly M0355 N0133)
3

%I M0355 N0133 #32 Dec 19 2020 03:13:00

%S 0,0,1,0,1,1,2,2,6,8,18,30,67,127,275,551,1192,2507,5475,11820,26007,

%T 57077,126686,281625,630660,1416116,3195784,7232624,16430563,37429146,

%U 85528079,195940960,450074270,1036226173,2391193488,5529420585

%N Number of bicentered 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 Nicolas Broutin and Philippe Flajolet, <a href="https://doi.org/10.1002/rsa.20393">The distribution of height and diameter in random non-plane binary trees</a>, Random Struct. Algorithms 41, No. 2, 215-252 (2012).

%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 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) + (T[h,z] - T[h-1,z])^2/2 + (T[h,z^2] - T[h-1,z^2])/2, z],n+1], {h,0,n/2}] (* _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_