OFFSET
0,5
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
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
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) ~ 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
EXAMPLE
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 + ...
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 *)
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
STATUS
approved