# 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:

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 ?

-
@Tom: I don't see how those sequences are related to the question. –  joriki May 16 '12 at 6:18
@Tom: I did notice the "e.g.". I thought you were offering these as examples of sequences which might be worth checking; I didn't expect links to random sequences just to demonstrate that there is such a thing as OEIS sequences. –  joriki May 16 '12 at 12:30
@Tom: I see, I misunderstood your first response; I thought you were saying that the sequences weren't related to the question. Since you're now saying they are, I'm not sure what gave you the impression that I didn't notice the "e.g.", but never mind... –  joriki May 16 '12 at 19:25

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!$.

-
I think this is what I am looking for. Thanks for the references. –  user1419 May 16 '12 at 21:23

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}$$ and observe that $$dz = \left(\frac{1-k}{w^k} + \frac{k}{w^{k+1}}\right) dw.$$ Following the procedure given in Wilf's generatingfunctionology (2nd ed. section 5.1 LIF) we seek to compute $$[z^n] T(z) = \frac{1}{2\pi i}\int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) dz$$ which using the above substitution becomes $$\frac{1}{2\pi i}\int_{|w-1|=\epsilon} \frac{w^{k(n+1)}}{(w-1)^{n+1}} \times w \times \left( \frac{1-k}{w^k} + \frac{k}{w^{k+1}} \right) dw.$$ This is $$\frac{1}{2\pi i}\int_{|w-1|=\epsilon} \left((1-k) \frac{w^{kn+1}}{(w-1)^{n+1}} + k \frac{w^{kn}}{(w-1)^{n+1}}\right)dw.$$ Now expand the two terms, getting $$w^{kn+1} = \sum_{q=0}^{kn+1} {kn+1\choose q} (w-1)^q \quad\text{and}\quad w^{kn} = \sum_{q=0}^{kn} {kn\choose q} (w-1)^q.$$ Extracting the term for $q=n$ from these sums we get $$(1-k) {kn+1\choose n} + k {kn\choose n}.$$ This is $$(1-k) \frac{kn+1}{(k-1)n+1} {kn\choose n} + k {kn\choose n}$$ which is $$\frac{1}{(k-1)n+1} {kn\choose n}.$$

-

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.

-
(+1) Thanks. Upvoted. Looks like we revived a question. Please check the spelling of the name. –  Marko Riedel Jun 16 '14 at 2:31
@MarkoRiedel, fixed. Thanks. –  vonbrand Jun 16 '14 at 2:34