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:
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}}$
$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 ?