info prev up next book cdrom email home

Rooted Tree

\begin{figure}\begin{center}\BoxedEPSF{RootedTrees.epsf scaled 700}\end{center}\end{figure}

A Tree with a special node called the ``Root'' or ``Eve.'' Denote the number of rooted trees with $n$ nodes by $T_n$, then the Generating Function is
$T(x)\equiv\sum_{n=0}^\infty T_n x^n =x+x^2+2x^3+4x^4+9x^5+20x^6$
$ +48x^7+115x^8+286x^9+719x^{10}+\ldots\quad$ (1)
(Sloane's A000081). This Power Series satisfies

$\displaystyle T(x)$ $\textstyle =$ $\displaystyle x\mathop{\rm exp}\nolimits \left[{\,\sum_{r=1}^\infty {1\over r} T(x^r)}\right]$ (2)
$\displaystyle t(x)$ $\textstyle =$ $\displaystyle T(x)-{\textstyle{1\over 2}}[T^2(x)-T(x^2)],$ (3)

where $t(x)$ is the Generating Function for unrooted Trees. A Generating Function for $T_n$ can be written using a product involving the sequence itself as
x\prod_{n=1}^\infty {1\over(1-x^n)^{T_n}}=\sum_{n=1}^\infty T_n x^n.
\end{displaymath} (4)

The number of rooted trees can also be calculated from the Recurrence Relation

T_{i+1}={1\over i}\sum_{j=1}^i \left({\sum_{d\vert j} d T_d}\right)T_{i-j+1},
\end{displaymath} (5)

with $T_0=0$ and $T_1=1$, where the second sum is over all $d$ which Divide $j$ (Finch).

See also Ordered Tree, Red-Black Tree, Weakly Binary Tree


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

Ruskey, F. ``Information on Rooted Trees.''

Sloane, N. J. A. Sequence A000081/M1180 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

© 1996-9 Eric W. Weisstein