Rooted Tree

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

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

$$t(x) = 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.$$ (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},$$ (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

References

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

Ruskey, F. ``Information on Rooted Trees.'' http://sue.csc.uvic.ca/~cos/inf/tree/RootedTree.html.

Sloane, N. J. A. Sequence A000081/M1180 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.