[Math] Counting $k$-ary labelled trees

combinatoricstrees

The (full) binary counting tree problems gives the number of binary trees can be formed using $N$ nodes $T(n)= C_n$, where $C_i$ are the Catalan numbers. The recursion form is $T_n = \sum_{i=0}^{n-1}T_iT_{n-1-i}$.
Now I want to generalize the binary counting tree by:

  1. Label the node, so that the order matters. This seems simple enough, the number of trees now is $T_n = n!C_n$. The recursion form is $n\sum_{i=0}^{n-1}{{n-1\choose i}T_iT_{n-1-i}}$

  2. $k$-ary tree: instead of binary, now it's $k$-ary (and of course with labelled nodes). I don't know if there's a name for this problem but I can't seem to find a "nice" recursion form or closed formula for $T_n$.

The question is thus asking for the recurrence form (and closed form if possible) of the $k$-ary labelled trees problem above.


What about a simpler version of counting ternary trees (no label) ? The recurrence form is easy to get but what about the closed form of it ?

Best Answer

The number of rooted, ordered, incomplete, unlabeled $k$-ary trees with $n$ vertices is given by

$$C^{(k)}_n=\frac1{(k-1)n+1}\binom{kn}n\;.$$

These are sometimes called Fuss-Catalan numbers; see Concrete Mathematics (p. 347) and MathWorld (which gives two references). Their generating function $C^{(k)}(x)=\sum_0^\infty C^{(k)}_nx^n$ satisfies $C^{(k)}(x)=1+xC^{(k)}(x)^k$. The numbers of rooted, ordered, incomplete, unlabeled ternary ($k=3$), quartic ($k=4$), qunitic ($k=5$), sextic ($k=6$), heptic ($k=7$) and octic ($k=8$) trees form OEIS sequences A001764, A002293, A002294, A002295, A002296 and A007556, respectively. To get the number of labeled trees, just multiply by $n!$.

Related Question