$n$-ary trees with $k$-internal nodes - Catalan numbers

Question

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?

Answer 1

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).

Answer 2

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

Answer 3

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