Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
    
@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
add comment

3 Answers

up vote 4 down vote accepted

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

share|improve this answer
    
I think this is what I am looking for. Thanks for the references. –  user1419 May 16 '12 at 21:23
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
1  
(+1) Thanks. Upvoted. Looks like we revived a question. Please check the spelling of the name. –  Marko Riedel Jun 16 at 2:31
    
@MarkoRiedel, fixed. Thanks. –  vonbrand Jun 16 at 2:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.