Weakly Binary Tree

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.

A Rooted Tree for which the Root is adjacent to at most two Vertices, and all nonroot Vertices are adjacent to at most three Vertices. Let $b(n)$ be the number of weakly binary trees of order $n$, then $b(5)=6$. Let

$$g(z)=\sum_{i=0}^\infty g_i z^i,$$ (1)

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} = {\textstyle{1\over 2}}g_i(g_i+1)+\sum_{j=1}^{i-1} g_{2i-j} g_j.$$ (5)

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

$$\lim_{n\to\infty} {b(n)n^{3/2}\over\xi^n}=\eta,$$ (6)

where

$$\xi=2.48325\ldots$$ (7)

is the unique Positive Root of

$$g\left({1\over x}\right)=1,$$ (8)

and

$$\eta=0.7916032\ldots.$$ (9)

$\xi$ is also given by

$$\xi=\lim_{n\to\infty} (c_n)^{2^{-n}},$$ (10)

where $c_n$ is given by

$$c_0 = 2$$ (11)

$$c_n = (c_{n-1})^2+2,$$ (12)

giving

$$\eta={1\over 2}\sqrt{\xi\over\pi}\sqrt{3+{1\over c_1}+{1\over c_1c_2}+{1\over c_1c_2c_3}+\ldots}.$$ (13)

References

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/otter/otter.html

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, 2nd ed. Reading, MA: Addison-Wesley, 1973.

Otter, R. ``The Number of Trees.'' Ann. Math. 49, 583-599, 1948.