login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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

S. J. Cyvin et al., Enumeration of constitutional isomers of polyenes, J. Molec. Structure (Theochem), 357 (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).

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.

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

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..[(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.

Cf. A052120, A000022, A000200, A000602.

Sequence in context: A124346 A033961 A201542 * A115868 A103299 A195204

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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified July 1 18:11 EDT 2016. Contains 274322 sequences.