# Recurrence for $k$-ary trees

The question is to find a recurrence, and a generating function for the number of rooted complete $$k$$-ary trees with $$n$$ non-leaves, that is, those rooted trees in which each node has either 0 or $$k$$ children.

The thing is, i'm having trouble to understand how to construct a new k-ary tree with $$n+1$$ non-leaves using smaller trees, it just looks like there are too many cases. It may have a pretty Catalan-like recurrence.

• Are these ordered trees, or not? For the former, an $n$ branch tree is an ordered list of $k$ trees who have $n-1$ branches in total, which directly gives a generating function equation. For the latter, a tree is instead a multiset of trees, which is indeed much harder to deal with. – Mike Earnest Mar 17 at 22:57