%I M0326 N0122 #114 Nov 19 2023 14:26:23

%S 1,1,1,1,2,2,4,6,11,18,37,66,135,265,552,1132,2410,5098,11020,23846,

%T 52233,114796,254371,565734,1265579,2841632,6408674,14502229,32935002,

%U 75021750,171404424,392658842,901842517,2076217086,4790669518,11077270335

%N Number of 3-valent trees (= boron trees or binary trees) with n nodes.

%C This can be described in 2 ways: (a) Trees with n nodes of valency <= 3, for n = 0,1,2,3,... (b) Trees with t = 2n+2 nodes of valency either 1 or 3 (implying that there are n nodes of valency 3 - the boron atoms - and n+2 nodes of valency 1 - the hydrogen atoms), for t = 2,4,6,8,...

%C Essentially the same sequences arises from studying the number of unrooted, unlabeled binary tree topologies with n leaves (see A129860). - _Steven Kelk_, Jul 22 2016

%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.

%D P. J. Cameron, Oligomorphic Permutation Groups, Cambridge; see Fig. 2 p. 35.

%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 Joseph Felsenstein, Inferring Phylogenies. Sinauer Associates, Inc., 2004, page 33. Note that at least the first two editions give an incorrect version of this sequence.

%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 R. J. Mathar, <a href="/A000672/b000672.txt">Table of n, a(n) for n = 0..191</a> [b-file corrected by _N. J. A. Sloane_, Oct 04 2010]

%H Dominik Bendle, Janko Boehm, Yue Ren, and Benjamin Schröter, <a href="https://arxiv.org/abs/2003.13752">Parallel Computation of tropical varieties, their positive part, and tropical Grassmannians</a>, arXiv:2003.13752 [math.AG], 2020.

%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 P. J. Cameron, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H P. J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a>, Quart. J. Math. Oxford, 38 (1987), 155-183.

%H M. Chan, <a href="http://arxiv.org/abs/1110.0273">Tropical hyperelliptic curves</a>, arXiv preprint arXiv:1110.0273 [math.CO], 2011.

%H Sergio Consoli, Jan Korst, Gijs Geleijnse, and Steffen Pauws, <a href="https://arxiv.org/abs/1807.00566">On the minimum quartet tree cost problem</a>, arXiv:1807.00566 [cs.DM], 2018.

%H S. J. Cyvin, J. Brunvoll, and B. N. Cyvin, <a href="http://dx.doi.org/10.1016/0166-1280(95)04329-6"> Enumeration of constitutional isomers of polyenes</a>, J. Molec. Struct. (Theochem) 357, no. 3 (1995) 255-261.

%H V. Fack, S. Lievens, and J. Van der Jeugt, <a href="http://dx.doi.org/0.1016/S0012-365X(01)00418-6">On the diameter of the rotation graph of binary coupling trees</a>, Discrete Math. 245 (2002), no. 1-3, 1--18. MR1887046 (2003i:05047).

%H Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, <a href="https://arxiv.org/abs/2004.02824">Six-Point Conformal Blocks in the Snowflake Channel</a>, arXiv:2004.02824 [hep-th], 2020.

%H Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, <a href="https://arxiv.org/abs/2006.13964">Seven-Point Conformal Blocks in the Extended Snowflake Channel and Beyond</a>, arXiv:2006.13964 [hep-th], 2020.

%H Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, <a href="https://arxiv.org/abs/2009.07674">All Global One- and Two-Dimensional Higher-Point Conformal Blocks</a>, arXiv:2009.07674 [hep-th], 2020.

%H M. D. Hendy, C. H. C. Little, David Penny, <a href="https://www.jstor.org/stable/2101137">Comparing trees with pendant vertices labelled</a>, SIAM J. Appl. Math. 44 (5) (1984) Table 1

%H Virginia Perkins Johnson, <a href="https://people.math.sc.edu/czabarka/Theses/JohnsonThesis.pdf">Enumeration Results on Leaf Labeled Trees</a>, PhD Dissertation, University of South Carolina, 2012. - From _N. J. A. Sloane_, Dec 22 2012

%H R. Otter, <a href="http://www.jstor.org/stable/1969046">The number of trees</a>, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.

%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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TrivalentTree.html">Trivalent Tree</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F Rains and Sloane give a g.f.

%F a(0)=a(1)=a(2)=1, a(n) = 2*b(n+1) - b(n+2) + b((n+1)/2) - 2*C(1+b(n/3), 3) - Sum_{i=1..[(n-1)/2]} C(b(i), 2)*b(n-2*i) + Sum_{i=1..[n/3]} b(i) Sum_{j=i..[(n-i)/2]} b(j)*b(n-i-j), where b(x) = A001190(x+1) if x is an integer, otherwise 0 (Cyvin et al.) [Index of A001190 shifted by _R. J. Mathar_, Mar 08 2010]

%F a(n) = A000673(n) + A000675(n).

%F a(n) ~ c * d^n / n^(5/2), where d = A086317 = 2.4832535361726368585622885181... and c = 1.2551088797592580080398489829149157375... . - _Vaclav Kotesovec_, Apr 19 2016

%F G.f.: B(x) - cycle_index(S2,-B(x)) + x * cycle_index(S3,B(x)) = B(x) - (B(x)^2 - B(x^2)) / 2 + x * (B(x)^3 + 3*B(x) B(x^2) + 2*B(x^3)) / 6, where B(x) = 1 + x * cycle_index(S2,B(x)) = 1 + x * (B(x)^2 + B(x^2)) / 2 is the generating function for A001190(n+1). - _Robert A. Russell_, Jan 17 2023

%e The 4 trees with 6 nodes are:

%e ._._._._._. . ._._._._. . ._._._._. . ._._._.

%e . . . . . . . . | . . . . . . | . . . . | |

%e G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 11*x^8 + ...

%t (* c = A001190 *) c[n_?OddQ] := c[n] = Sum[c[k]*c[n-k], {k, 1, (n-1)/2}]; c[n_?EvenQ] := c[n] = (1/2)*c[n/2]*(c[n/2] + 1) + Sum[c[k]*c[n-k], {k, 1, n/2-1}]; c[0] = 0; c[1] = 1; b[x_] := If[IntegerQ[x], c[x+1], 0]; a[0] = a[1] = a[2] = 1; a[n_] := b[n/2] - (1/3)*(b[(n-1)/3]-1)*b[(n-1)/3]*(b[(n-1)/3] + 1) + 2*b[n] - b[n+1] - Sum[(1/2)*(b[i]-1)*b[i]*b[-2*i + n - 1], {i, 1, (n-2)/2}] + Sum[b[i]*Sum[b[j]*b[n-i-j-1], {j, i, (1/2)*(n-i-1)}], {i, 1, (n-1)/3}]; Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Jan 19 2015 *)

%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] + 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 *)

%t n = 60; c[n_?OddQ] := c[n] = Sum[c[k]*c[n-k], {k,1,(n-1)/2}];

%t c[n_?EvenQ] := c[n] = (1/2)*c[n/2]*(c[n/2] + 1) + Sum[c[k]*c[n-k],

%t {k,1,n/2-1}]; c[0] = 0; c[1] = 1; (* as in program 1 above *)

%t gf[x_] := Sum[c[i+1] x^i, {i,0,n}]; (* g.f. for A001190(n+1) *)

%t ci[x_] := SymmetricGroupIndex[3, x] /. x[i_] -> gf[x^i];

%t CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 +

%t x ci[x], {x,0,n}]], x] (* _Robert A. Russell_, Jan 17 2023 *)

%Y Column k = 3 of A144528.

%Y A000672 = A000675 + A000673.

%Y Cf. A001190(n+1) (rooted trees).

%Y Cf. A052120, A000022, A000200, A000602, A129860.

%K nonn,easy,nice

%O 0,5

%A _N. J. A. Sloane_