TOPICS

Weakly Binary Tree

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A weakly binary tree is a planted tree in which all nonroot graph vertices are adjacent to at most three graph vertices.

WeaklyBinaryTrees

Let

g(z)=sum_(i=0)^inftyg_iz^i,
(1)

be the generating function for the number of weakly binary trees on i nodes, where

g_0=0
(2)
g_1=g_2=g_3=1
(3)
g_(2i+1)=sum_(j=1)^(i)g_(2i+1-j)g_j
(4)
g_(2i)=1/2g_i(g_i+1)+sum_(j=1)^(i-1)g_(2i-j)g_j.
(5)

This gives the sequence 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, ... (OEIS A001190), sometimes also known as the Wedderburn-Etherington numbers.

Otter (Otter 1948, Harary and Palmer 1973, Knuth 1997) showed that

lim_(n->infty)(g_nn^(3/2))/(xi^(n-1))=eta,
(6)

where

xi=2.48325...
(7)

(OEIS A086317; Knuth 1997, p. 583; Finch 2003, p. 297) is the unique positive root of

g(1/x)=1,
(8)

and

eta=0.7916032...
(9)

(OEIS A086318; Knuth 1997, p. 583). xi is also given by the rapidly converging limit

xi=lim_(n->infty)c_n^(2^(-n)),
(10)

where c_n is given by

c_0=2
(11)
c_n=c_(n-1)^2+2,
(12)

the first few terms of which are 6, 38, 1446, 2090918, 4371938082726, ... (OEIS A072191), giving

eta=1/2sqrt(xi/pi)sqrt(3+1/(c_1)+1/(c_1c_2)+1/(c_1c_2c_3)+...).
(13)

See also

Binary Tree, Rooted Tree, Strongly Binary Tree, Tree

Explore with Wolfram|Alpha

References

Comtet, L. Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, p. 55, 1974.Cyvin, S. J. et al. . "Enumeration of Constitutional Isomers of Polyenes." J. Molec. Structure (Theorochem.) 357, 255-261, 1995.Etherington, I. M. H. "Non-Associate Powers and a Functional Equation." Math. Gaz. 21, 36-39 and 153, 1937.Etherington, I. M. H. "On Non-Associative Combinations." Proc. Royal Soc. Edinburgh 59, 153-162, 1938-39.Finch, S. R. "Otter's Tree Enumeration Constants." §5.6 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 295-316, 2003.Franklin, J. N. and Golomb, S. W. "A Function-Theoretic Approach to the Study of Nonlinear Recurring Sequences." Pacific J. Math. 56, 467, 1975.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1969.Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, 1973.Knuth, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1997.Olds, C. D. "Problem 4277: Genetic Algebra." Amer. Math. Monthly 56, 697-699, 1949.Otter, R. "The Number of Trees." Ann. Math. 49, 583-599, 1948.Sloane, N. J. A. Sequences A001190/M0790 A072191, A086317, and A086318 in "The On-Line Encyclopedia of Integer Sequences."Stanley, R. P. Problem 6.52 in Enumerative Combinatorics, Vol. 2. Cambridge, England: Cambridge University Press, 1999.Wedderburn, J. H. M. "The Functional Equation g(x^2)=2ax+[g(x)]^2." Ann. Math. 24, 121-140, 1922-1923.

Referenced on Wolfram|Alpha

Weakly Binary Tree

Cite this as:

Weisstein, Eric W. "Weakly Binary Tree." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/WeaklyBinaryTree.html

Subject classifications