Counting $k$-ary labelled trees

Solution 1:

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

Solution 2:

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

Solution 3:

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.