4
$\begingroup$

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 ?

  • 0
    @To$m$: I see, I misunderstood your first response; I thought you were s$a$ying that the sequences weren't related to the question. Since you're now saying they are, I'$m$ not sure what gave you the i$m$pression that I didn't notice the "e.g.", but never mind...2012-05-16

3 Answers 3

7

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

  • 0
    I think this is what I am looking for. Thanks for the references.2012-05-16
3

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

2

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.

  • 0
    @MarkoRiedel, fixed. Thanks.2014-06-16