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.

It is known that the Catalan numbers count the number of binary trees with $k$-internal nodes. I was thinking of how to count ternary trees or in general $n$-ary trees with $k$ internal nodes and got the following recurrence:

$F_{k+1}=\sum_{a_1+a_2+\ldots+a_n=k} F_{a_1} F_{a_2} \ldots F_{a_n}$

Where $F_k$ is the number of $n$-ary trees with $k$ internal nodes.

So then I tried writing a generating function for this recurrence. If $f(x)$ represents the generating function I found that $f(x)$ satisfies the following functional equation:

$x[f(x)]^n-f(x)+1=0$

I'm pretty sure this is one of the "nice" polynomials that has an elementary solution even when $n \geq 5$. The problem is that it gets nasty, so to speak, even for $n=3$. Therefore I am seeking a combinatorial solution: perhaps an $n$D grid and using multinomial coefficients?

share|improve this question

3 Answers 3

Number of $k$-ary trees («Fuss-Catalan number») is equal to number of lattice paths that never go above the diagonale of $n\times nk$ rectangle.

As usual, this number can be computed using a (variation of) reflection principle (see e.g. M. Renault. Lost (and Found) in Translation: Andre’s Actual Method and Its Application to the Generalized Ballot Problem).

share|improve this answer
    
Note that in this generalization you still have a 2D-lattice but different restriction for paths. (Perhaps, most natural multidimensional generalization of Catalan numbers is the number of standard Young tableux of a given shape. –  Grigory M Nov 16 '12 at 21:27
1  
It would be very helpful if you could explain this in further detail and more with respect to what I came up with and perhaps the Catalan numbers. –  Grigory Aleksandrov Nov 17 '12 at 2:02

Maybe you have already found better answer but here is mine if it may help. You can use the Lagrange–Bürmann inversion formula. You will find that your $f(X)$ can be expressed has a Taylor serie with the coefficient of $x^m$ being the generalized $n$-th Catalan number and then if I'm not wrong your $F(k)$ should be:

$F(k) = \frac{1}{(n-1)k + 1}{nk \choose k}$

Regards Gianfranco OLDANI

share|improve this answer

Catalan number $C_n$ is also equal to number of ways of bracketing n-fold non-cummutative, non-associative multiplications.
$(a\cdot b)\cdot c$ for example is different from $a\cdot(b\cdot c)$
It is clear that $C_1 = 1, C_2 = 1$.

Now observe that for an expression like $(a\cdot b\cdot c)\cdot (d\cdot e\cdot f \cdot g)$, the last multiplication always happens between two blocks, and each block has different ways of bracketing inside. In this example the left block has $C_3$ ways of bracketing and right block has $C_4$ ways of bracketing. $$C_n = \sum_{k = 1}^{n-1}C_kC_{n-k}$$

This looks like convolution of two series and calls badly for multiplication of generating function.
$$g(z): = \sum_{n = 1}^\infty C_n z^n$$ $$g(z)g(z) = (\sum_{n = 1}^\infty C_n z^n)(\sum_{n = 1}^\infty C_n z^n) = \sum_{n = 1}^\infty(\sum_{k = 1}^{n-1}C_k C_{n-k})= \sum_{n = 2}^\infty C_nz^n = g(z)-z$$ We yield $$g(z)^2-g(z)+z = 0$$ Use fact that $$f(x) = (1+x)^{1/2}= \sum_{k = 0}^\infty \frac{1}{k!}f^{(k)}(0)x^k = \sum_{k = 0}^\infty a_n x^k$$ where $$a_n = \binom{\frac{1}{2}}{n} = \frac{(-1)^{k-1}(2k-2)!}{2^{2k-1}k!(k-1)!}$$ Now $$g(z) = \frac{1\pm \sqrt{1-4z}}{2} = \frac{1}{2}(1\pm\sqrt{1-4z})$$ Since we know $C_n \ge 0$ $$ g(z) = \frac{1}{2}\sum_{n = 1}^\infty (-a_n)(-4z)^n = \frac{1}{2}\sum_{n = 1}^\infty (-1)(-1)\binom{2n-2}{2n-1}\frac{2}{n} = \sum_{n = 1}^\infty \binom{2n-2}{2n-1}\frac{1}{n}$$ $$\Longrightarrow C_n = \binom{2n-2}{n-1}\frac{1}{n}$$

share|improve this answer

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.