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

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

$\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
\lim_{n\to\infty} {b(n)n^{3/2}\over\xi^n}=\eta,
\end{displaymath} (6)

\end{displaymath} (7)

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

\end{displaymath} (9)

$\xi$ is also given by
\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)

\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)


Finch, S. ``Favorite Mathematical Constants.''

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