This site is supported by donations to The OEIS Foundation.

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A000672 Number of 3-valent 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), 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] 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, 2011 S. J. Cyvin, J. Brunvoll, B. N. Cyvin, Enumeration of constitutional isomers of polyenes, J. Molec. Struct. (Theochem) 357, no. 3 (1995) 255-261. Fack, V.; Lievens, S.; Van der Jeugt, J. On the diameter of the rotation graph of binary coupling trees, Discrete Math. 245 (2002), no. 1-3, 1--18. 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 4-Valent Trees)., J. Integer Sequences, Vol. 2 (1999), Article 99.1.1. 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) = 2b(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-2i) + 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.) 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[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 *) 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 EXTENSIONS Shifted index of A001190 in the formula - R. J. Mathar, Mar 08 2010 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 4 05:11 EST 2016. Contains 278748 sequences.