2
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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 trees, meaning that the children of each node are assumed to be linearly ordered, and changing the order changes the tree. The situation for unordered trees is much messier even without restrictions on the degrees of the nodes: see OEIS $A000081$, for instance.

$\endgroup$
7
  • $\begingroup$ Thank you so much! Regarding your last paragraph, I want to clarify your plane definition. It is saying that for a given node with the some children, if I rearrange the order of the children (without changing the number of children), then it will give us a different order? Is that right? So in other words, I am asking if the Fuss-Catalan number can be used to give an upper bound on the number of unordered rooted $m$-ary tress -- which is my purpose. $\endgroup$
    – Resu
    Jun 30, 2020 at 3:25
  • 1
    $\begingroup$ @User: Yes, if you reorder the children of a node, of course letting them carry their descendants with them in the reordering, you have a different tree, unless the resulting trees are isomorphic taking order into account. That is, if for instance you swap two children that are the roots of isomorphic plane subtrees, you still have the same plane tree. So yes, this will give you an upper bound, as it distinguishes trees that you want to consider the same. $\endgroup$ Jun 30, 2020 at 3:31
  • $\begingroup$ I think the mapping you stated, "adding a suitable number of leaf children to each node that does not have $m$ children," is not injective, because the number of children added cannot be recovered. Indeed, even though $C_2^{(3)}=3$, the number of $3$-ary plane trees with $2$ nodes is only $1$. $\endgroup$ Jun 30, 2020 at 17:03
  • $\begingroup$ @MikeEarnest: Why do you think that it cannot be recovered? Any existing leaves at that node will have been extended and will no longer be leaves. Every leaf in the extended tree is new. $\endgroup$ Jun 30, 2020 at 17:18
  • 2
    $\begingroup$ Ah, you and I had different interpretations of OP's problem. I was thinking that an ordered tree was a rooted tree where every vertex was given an ordering of its children, and an $m$-ary ordered tree was one where each node has at most $m$ children. $\endgroup$ Jun 30, 2020 at 18:30
1
$\begingroup$

You wanted to count the number of unordered, unlabeled, $d$-ary, nonfull, rooted trees with $n$ vertices. As Brian's answer suggested, the unordered condition makes it unlikely for your problem to be tractable. However, it is possible to enumerate the number of trees satisfying all these conditions, but where "unordered" is replaced with "ordered."

Edit: I am defined an ordered tree to be "a rooted tree, together with an ordering of the children of each vertex," and a $d$-ary tree is one where every vertex has at most $d$ children. If you instead define an ordered $d$-ary tree to be a root vertex, together with a list of length $d$ where each entry is either empty or a subtree, then Brian's answer gives the correct enumeration.

This problem is best approached with generating functions. Let $t_n$ be the number of ordered, unlabeled, $d$-ary, nonfull, rooted trees with $n$ vertices, and let $T(x)=\sum_{n\ge 1}t_nx^n$. Standard generating function trickery shows $$ T(x)=x(1+T(x)+\dots+T(x)^d), $$ since a tree consists of a root, followed by an ordered sequence consisting of between $0$ and $d$ subtrees. Writing this equation as $$ x=\frac{T(1-T)}{1-T^{d+1}}, $$ we can see that $T(x)$ is the compositional inverse of $S(x)$, defined by $$ S(x)=\frac{x(1-x)}{1-x^{d+1}}. $$ Therefore, we can apply the Lagrange inversion formula to compute $t_n$ in terms of the coefficients of $S(x)$. The LIF states that whenever $f(x)$ and $g(x)$ are analytic functions for which $f(0)=g(0)=0$ and $f'(0)g'(0)\neq 0$ and $f(g(x))=g(f(x))=x$, then the coefficients of $f$ and $g$ are related by $$ [x^n]g(x)^k=\frac{k}n[x^{-k}]f(x)^n\tag{LIF} $$ Here, $[x^i]h(x)$ denotes the coefficient of $x^i$ in $h(x)$. Using this, \begin{align} t_n &=[x^n]T(x) \\&\stackrel{\text{LIF}}=\tfrac1n[x^{-1}]S(x)^{-n} \\&=\tfrac1n[x^{-1}]x^{-n}\left(\frac{1-x^{d+1}}{1-x}\right)^n \\&=\tfrac1n[x^{n-1}](1-x^{d+1})^n(1-x)^{-n} \\&=\boxed{\frac1n\sum_{k\ge 0}(-1)^k\binom{n}{k}\binom{2n-2-k(d+1)}{n-1-k(d+1)}.} \end{align}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .