I know that the Catalan number $C_n$ is the number of full (i.e., 0 or 2 children per node) binary trees with $n+1$ leaves. I am interested in the generalization.
Note that I do not care about any labeling, ordering, or number of leaves. I just want the tree to be rooted and have total number of nodes equal $n$, that's all. I am also not referring to a full $m$-ary tree, i.e., in my case nodes can have any number of children $\in\{0,\dots,m\}$ (instead of just 0 or $m$ in the full case). To summarize, my trees are rooted, unordered, unlabeled, $m$-ary, incomplete, not full, and have $n$ nodes in total.
With that being said, I would also like to point out the Fuss-Catalan numbers. From the Wiki page of "m-ary tree", it states that the total number of possible m-ary tree with n nodes is
\begin{align}
C_n=\frac{1}{(m-1)n+1}\cdot{mn\choose n}.
\end{align}
Does this hold for non-full $m$-ary trees? If so, why? Can I see a derivation of this result with relation to the tree. I've checked the book "Concrete Mathematics 2nd edition" (p. 361) but their derivation wasn't with regards to the trees but instead with $m$-Raney sequences (perhaps a strong link exists with trees). Thanks.
Best Answer
If you have Concrete Mathematics, you know that the numbers $$C_n^{(m)}=\frac1{(m-1)n+1}\binom{mn}n$$ satisfy the recurrence
$$C_{n+1}^{(m)}=\sum_{\substack{0\le n_1,n_2,\ldots,n_m\\n_1+n_2+\ldots+n_m=n}}C_{n_1}^{(m)}C_{n_2}^{(m)}\ldots C_{n_m}^{(m)}+[n=0]\;;$$
see the bottom of page $361$. The same induction argument that shows that the Catalan number $C_n=C_n^{(2)}$ is the number of full binary trees with $n$ internal nodes shows that $C_n^{(m)}$ is the number of full $m$-ary trees with $n$ internal nodes. Any $m$-ary plane tree with $n$ nodes can be extended to a full $m$-ary tree with $n$ internal nodes by adding a suitable number of leaf children to each node that does not have $m$ children. Conversely, any full $m$-ary tree with $n$ internal nodes can be reduced to an $m$-ary plane tree with $n$ nodes by deleting all of its leaves. These two operations are inverses, so each is a bijection between full $m$-ary trees with $n$ internal nodes and $m$-ary plane trees with $n$ nodes. Thus, $C_n^{(m)}$ is also the number of $m$-ary plane trees with $n$ nodes.
Note, however, that this is for plane $m$-ary trees. This means that each node $v$ has $m$ slots for possible children, slots that we may label $S_1(v),S_2(v),\ldots,S_m(v)$ from left to right, and any of these slots may be empty. Thus, not only are the children of each node linearly ordered, but each child of a node $v$ fills a specific slot $S_k(v)$, and changing which slots are filled changes the tree even if it doesn’t change the degree of $v$. The situation for unordered trees is much messier even without restrictions on the degrees of the nodes: see OEIS $A000081$, for instance.