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.

  • $\begingroup$ 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. $\endgroup$ – Mike Earnest Mar 17 at 22:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.