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?