TOPICS

# Weakly Binary Tree

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

Let

 (1)

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

 (2) (3) (4) (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

 (6)

where

 (7)

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

 (8)

and

 (9)

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

 (10)

where is given by

 (11) (12)

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

 (13)

Binary Tree, Rooted Tree, Strongly Binary Tree, Tree

## Explore with Wolfram|Alpha

More things to try:

## 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 Web Resource. https://mathworld.wolfram.com/WeaklyBinaryTree.html