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

Let

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

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

where

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

and

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

where is given by

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

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