= Recursively repetition-free labelled tree
{title2=$\mathcal T(D)$}
For a label <set> $D$, define $\mathcal T(D)$ inductively: choose a root label $d\in D$ and a <finite repetition-free sequence> of <rooted trees> in $\mathcal T(D\setminus\{d\})$ as its children. Each object is a finite ordered <rooted tree>. Labels are distinct along each root-to-leaf path, and child <rooted trees> at a vertex are distinct as whole <rooted trees>. Labels may repeat across different branches; children need not have distinct root labels. For a finite pool of size $m$, the exact number $t_m$ of <rooted trees> satisfies
$$
t_0=0,\qquad t_m=m\sum_{k=0}^{t_{m-1}}\frac{t_{m-1}!}{(t_{m-1}-k)!}.
$$
This follows by choosing the root and then an ordered repetition-free list from the finite pool of smaller <rooted trees>.
Back to article page
