Counting $k$-ary labelled trees 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 ?  
 A: 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!$.
A: It is worth noting that we can derive the closed form expression
referenced by @joriki from Concrete Mathematics using a variant of
Lagrange inversion. Suppose the functional equation for these trees is
$$T(z) = 1 + z\times T(z)^k.$$
Re-write this as (putting $w=T(z)$)
$$z = \frac{w-1}{w^k}.$$
Following the procedure given in Wilf's generatingfunctionology (2nd
ed. section 5.1 LIF) we seek to compute
$$[z^n] T(z) = \frac{1}{n} [z^{n-1}] T'(z)
= \frac{1}{n}
\frac{1}{2\pi i}\int_{|z|=\varepsilon} \frac{1}{z^{n}}
T'(z) dz$$
which using the above substitution becomes (we have $w = 1 + z +
\cdots$ so as $z$ makes one turn around zero $w$ does as well, around
one, plus  lower order fluctuations so that the image contour maybe
deformed to a  small circle):
$$\frac{1}{n} \frac{1}{2\pi i}\int_{|w-1|=\gamma}
\frac{w^{kn}}{(w-1)^{n}} \; dw.$$
Expanding to get the Laurent series about $w=1$ we find
$$\frac{1}{n} \frac{1}{2\pi i}\int_{|w-1|=\gamma}
\frac{1}{(w-1)^{n}}
\sum_{q=0}^{kn} {kn \choose q} (w-1)^q
\; dw.$$
This is by the Cauchy Residue Theorem
$$\frac{1}{n} {kn\choose n-1}.$$
To get a formula that holds at $n=0$ as well we re-write as
suggested by @vonbrand
$$\frac{1}{n} {kn\choose n} \frac{n}{kn-n+1}$$
which is
$$\frac{1}{n(k-1)+1} {kn\choose n}.$$
A: Expanding on Marko Riedl's answer, we want to solve for the series $T(z)$ where:
$$
T(z) = 1 + z T(z)^k
$$
Change variables to $u \mapsto T(z) - 1$ so that:
$$
u = z (u + 1)^k
$$
The Bürmann-Lagrange inversion formula for $u = z \phi(u)$ gives
$$
[z^n] u(z) = \frac{1}{n} [u^{n - 1}] \phi^n (u)
$$
In our case:
\begin{align}
[z^n] u(z) 
  &= \frac{1}{n} [u^{n - 1}] (u + 1)^{k n} \\
  &= \frac{1}{n} \binom{k n}{n - 1}
\end{align}
This is valid for $n > 0$. But:
$$
\frac{1}{n} \binom{k n}{n - 1}
  = \frac{(k n)!}{n (n - 1)! (k n - n + 1)!}
  = \frac{1}{n (k - 1) + 1} \binom{k n}{n}
$$
By happy coincidence, this gives the correct value 1 for $n = 0$. And for $k = 2$ it gives the familiar Catalan numbers.
