$n$-ary trees with $k$-internal nodes - Catalan numbers 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?
 A: 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}.$$
A: 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).
A: 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}$$
