info prev up next book cdrom email home

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

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

where
$\displaystyle g_0$ $\textstyle =$ $\displaystyle 0$ (2)
$\displaystyle g_1$ $\textstyle =$ $\displaystyle g_2=g_3=1$ (3)
$\displaystyle g_{2i+1}$ $\textstyle =$ $\displaystyle \sum_{j=1}^i g_{2i+1-j}g_j$ (4)
$\displaystyle g_{2i}$ $\textstyle =$ $\displaystyle {\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
\begin{displaymath}
\lim_{n\to\infty} {b(n)n^{3/2}\over\xi^n}=\eta,
\end{displaymath} (6)

where
\begin{displaymath}
\xi=2.48325\ldots
\end{displaymath} (7)

is the unique Positive Root of
\begin{displaymath}
g\left({1\over x}\right)=1,
\end{displaymath} (8)

and
\begin{displaymath}
\eta=0.7916032\ldots.
\end{displaymath} (9)

$\xi$ is also given by
\begin{displaymath}
\xi=\lim_{n\to\infty} (c_n)^{2^{-n}},
\end{displaymath} (10)

where $c_n$ is given by
$\displaystyle c_0$ $\textstyle =$ $\displaystyle 2$ (11)
$\displaystyle c_n$ $\textstyle =$ $\displaystyle (c_{n-1})^2+2,$ (12)

giving
\begin{displaymath}
\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}.
\end{displaymath} (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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26