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

1, 1, 1, 1, 2, 2, 4, 6, 11, 18, 37, 66, 135, 265, 552, 1132, 2410, 5098, 11020, 23846, 52233, 114796, 254371, 565734, 1265579, 2841632, 6408674, 14502229, 32935002, 75021750, 171404424, 392658842, 901842517, 2076217086, 4790669518, 11077270335

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

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

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

Examples

			The 4 trees with 6 nodes are:
._._._._._. . ._._._._. . ._._._._. . ._._._.
. . . . . . . . | . . . . . . | . . . . | |
G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 11*x^8 + ...
		

References

• Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.
• P. J. Cameron, Oligomorphic Permutation Groups, Cambridge; see Fig. 2 p. 35.
• 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).
• 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.
• R. C. Read, personal communication.
• 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).

Links

• R. J. Mathar, Table of n, a(n) for n = 0..191 [b-file corrected by _N. J. A. Sloane_, Oct 04 2010]
• Dominik Bendle, Janko Boehm, Yue Ren, and Benjamin Schröter, Parallel Computation of tropical varieties, their positive part, and tropical Grassmannians, arXiv:2003.13752 [math.AG], 2020.
• Nicolas Broutin and Philippe Flajolet, The distribution of height and diameter in random non-plane binary trees, Random Struct. Algorithms 41, No. 2, 215-252 (2012).
• P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
• P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183.
• M. Chan, Tropical hyperelliptic curves, arXiv preprint arXiv:1110.0273 [math.CO], 2011.
• Sergio Consoli, Jan Korst, Gijs Geleijnse, and Steffen Pauws, On the minimum quartet tree cost problem, arXiv:1807.00566 [cs.DM], 2018.
• S. J. Cyvin, J. Brunvoll, and B. N. Cyvin, Enumeration of constitutional isomers of polyenes, J. Molec. Struct. (Theochem) 357, no. 3 (1995) 255-261.
• V. Fack, S. Lievens, and J. Van der Jeugt, On the diameter of the rotation graph of binary coupling trees, Discrete Math. 245 (2002), no. 1-3, 1--18. MR1887046 (2003i:05047).
• Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, Six-Point Conformal Blocks in the Snowflake Channel, arXiv:2004.02824 [hep-th], 2020.
• Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, Seven-Point Conformal Blocks in the Extended Snowflake Channel and Beyond, arXiv:2006.13964 [hep-th], 2020.
• Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, All Global One- and Two-Dimensional Higher-Point Conformal Blocks, arXiv:2009.07674 [hep-th], 2020.
• M. D. Hendy, C. H. C. Little, David Penny, Comparing trees with pendant vertices labelled, SIAM J. Appl. Math. 44 (5) (1984) Table 1
• Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, PhD Dissertation, University of South Carolina, 2012. - From _N. J. A. Sloane_, Dec 22 2012
• R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
• E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
• R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
• Eric Weisstein's World of Mathematics, Trivalent Tree
• Index entries for sequences related to trees

Crossrefs

Column k = 3 of A144528.

A000672 = A000675 + A000673.

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

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

Programs

Mathematica

(* 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 *)
n = 50; (* algorithm from Rains and Sloane *)
S2[f_,h_,x_] := f[h,x]^2/2 + f[h,x^2]/2;
S3[f_,h_,x_] := f[h,x]^3/6 + f[h,x] f[h,x^2]/2 + f[h,x^3]/3;
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];
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 *)
n = 60; 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; (* as in program 1 above *)
gf[x_] := Sum[c[i+1] x^i, {i,0,n}]; (* g.f. for A001190(n+1) *)
ci[x_] := SymmetricGroupIndex[3, x] /. x[i_] -> gf[x^i];
CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 +
x ci[x], {x,0,n}]], x] (* Robert A. Russell, Jan 17 2023 *)

Formula

Rains and Sloane give a g.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]

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

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

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