

A000672


Number of 3valent trees (= boron trees or binary trees) with n nodes.
(Formerly M0326 N0122)


6



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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

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), 257305 = Math. Papers, Vol. 9, 427460 (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 [bfile corrected by N. J. A. Sloane, Oct 04 2010]
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), 155183.
M. Chan, Tropical hyperelliptic curves, arXiv preprint arXiv:1110.0273, 2011
S. J. Cyvin, J. Brunvoll, B. N. Cyvin, Enumeration of constitutional isomers of polyenes, J. Molec. Struct. (Theochem) 357, no. 3 (1995) 255261.
Fack, V.; Lievens, S.; Van der Jeugt, J. On the diameter of the rotation graph of binary coupling trees, Discrete Math. 245 (2002), no. 13, 118. MR1887046 (2003i:05047).
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012.  From N. J. A. Sloane, Dec 22 2012
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4Valent Trees)., J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
Eric Weisstein's World of Mathematics, Trivalent Tree
Index entries for sequences related to trees


FORMULA

Rains and Sloane give a g.f.
a(0)=a(1)=a(2)=1, a(n) = 2b(n+1)  b(n+2) + b((n+1)/2)  2 C(1+b(n/3), 3)  Sum_{i=1..[(n1)/2]} C(b(i), 2)b(n2i) + Sum_{i=1..[n/3]} b(i) Sum_{j=i..[(ni)/2]} b(j)b(nij), where b(x) = A001190(x+1) if x is an integer, otherwise 0 (Cyvin et al.)
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


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[nk], {k, 1, (n1)/2}]; c[n_?EvenQ] := c[n] = (1/2)*c[n/2]*(c[n/2] + 1) + Sum[c[k]*c[nk], {k, 1, n/21}]; 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[(n1)/3]1)*b[(n1)/3]*(b[(n1)/3] + 1) + 2*b[n]  b[n+1]  Sum[(1/2)*(b[i]1)*b[i]*b[2*i + n  1], {i, 1, (n2)/2}] + Sum[b[i]*Sum[b[j]*b[nij1], {j, i, (1/2)*(ni1)}], {i, 1, (n1)/3}]; Table[a[n], {n, 0, 35}] (* JeanFrançois Alcover, Jan 19 2015 *)


CROSSREFS

Cf. A000673, A000675, A052120, A000022, A000200, A000602, A129860.
Sequence in context: A033961 A201542 * A129860 A115868 A103299 A278246
Adjacent sequences: A000669 A000670 A000671 * A000673 A000674 A000675


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

Shifted index of A001190 in the formula  R. J. Mathar, Mar 08 2010


STATUS

approved



