4
$\begingroup$

As a follow up to this question (the number of rooted binary trees of size n), how many possible binary trees can you have if the nodes are now labeled, so that abc is different than bac cab etc ? In other words, order matters. Certainly it will be much more than the Catalan number.

What would the problem be if you have n-ary trees instead of binary ?

Are these known problems? reference ?

Improve this question
$\endgroup$
6
$\begingroup$

I am not sure, if I understood the question correctly, but are you asking for the number of rooted binary trees of size $n$, with nodes labeled from $1,...,n$, where isomorphic trees with different labelings are counted as different?

If so, isn't your labeling just adding $n!$ different possible labelings for each class of isomorphic trees? I.e. your total number of trees would be $n!C_n$, where $C_n$ is the $n$-th Catalan number.

Improve this answer
$\endgroup$
  • $\begingroup$ Yes, isomorphic trees w/ diff labeling are counted as different. I also think n!C_n is the # of total trees. Is there a known name for this ? like "ordered binary counting tree" ? so I can reference it. In the case of n-ary trees, isn't there some thing about there's a bijection btw general and binary tree ? so that the # of trees for binary tree is the same as n-ary tree ? $\endgroup$ – user1419 May 9 '12 at 23:13
  • 1
    $\begingroup$ If you mean with $k$-ary tree trees where every node has at most $k$ children, then no, I don't think that there is a bijection between the set of binary trees of size $n$ to the set of $k$-ary trees of size $n$, $k>2$. Simply because any binary tree is also a $k$-ary tree. $\endgroup$ – Syzygy May 9 '12 at 23:24
  • $\begingroup$ @user1419 $n! C_n = (2n)!/(n+1)! = (n+2)(n+3)\cdots(2n-1)(2n)$. $\endgroup$ – Gilles 'SO- stop being evil' May 11 '12 at 0:19
  • $\begingroup$ Is there a solution for n-ary tree instead of binary tree ? $\endgroup$ – user1419 May 11 '12 at 6:18
1
$\begingroup$

As partially answered above by Syzygy, for labelled binary trees, it is $n!C_n$, where $C_n$ being the Catalan number. Generalized this to labelled $k$-ary trees, it is $n!C^k_n$ where $C^k_n$ is the Fuzz-Catalan number $ \begin{equation} C^k_n= \binom{kn}{n}\frac{1}{(k-1)n+1} \end{equation} $

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.