# Counting $k$-ary ordered trees

The (full) binary counting tree problems give the number of binary trees that 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. the order of children nodes 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 ordered nodes). I am not sure if there is a specific name for this issue, but I can't find a "nice" recursion form or closed formula for $$T_n$$.

The question thus asks for the recurrence form (and closed form if possible) of the $$k$$-ary ordered 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. Commented May 16, 2012 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. Commented May 16, 2012 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... Commented May 16, 2012 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. Commented May 16, 2012 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}.$$

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

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. Commented Jun 16, 2014 at 2:31
• @MarkoRiedel, fixed. Thanks. Commented Jun 16, 2014 at 2:34

Here is a sketch of a bijective proof of the formula $$C^{(k)}_n=\frac1{(k-1)n+1}\binom{kn}n.$$ I will give a bijection between $$k$$-ary trees and ballot sequences, and then refer to Four proofs of the ballot theorem by Marc Renault (link to paper) for a proof that the number of ballot sequences is given by the above formula. My proof is morally equivalent to the one given in Concrete Mathematics (see Brian's answer for a presentation of this proof).

Define a ballot sequence to be a sequence of $$(k-1)n$$ zeroes and $$n$$ ones such that, in any initial segment, the proportion of numbers which are $$1$$ is at most $$1/k$$.

Given a $$k$$-ary tree with $$n$$ internal nodes, we produce a ballot sequence as follows. Traverse the tree in depth first order. Every time you traverse an edge upwards from child to parent, you append either a $$0$$ or a $$1$$ to the sequence. If you are traversing the rightmost edge of the parent node, you write down a $$1$$, and otherwise you write down a zero. It is simple to prove that the resulting sequence is a ballot sequence; at any point during the traversal, each $$1$$ has been preceded by at least $$(k-1)$$ zeroes, corresponding to the siblings of the edge that produced the $$1$$.

The inverse bijection is trickier to describe. Given a ballot sequence, define the weight of each initial segment to be $$(\text{# zeroes})-(k-1)(\text{# ones})$$. By definition, the weight is always nonnegative. For each $$i\in \{1,\dots,k-1\}$$, define the $$i^\text{th}$$ critical zero to be the rightmost zero in the sequence, such that the weight of the segment ending with that zero is $$i$$. If you delete all $$(k-1)$$ critical zeroes, and also if you delete the final $$1$$ of the ballot sequence, then the whole sequence is split into $$k$$ subsequences. With some thought, you can prove that all of these subsequences are also valid ballot sequences. This gives a recursive bijection with $$k$$-ary trees; you recursively find the bijection of each of the $$k$$ subsequences with a $$k$$-ary tree, and then join these $$k$$ trees from left to right under a root node to get the entire tree.