2
$\begingroup$

Is there any algorithm to build or count the labeled non-isomorphic trees on $n$ vertices ?

$\endgroup$
6
  • $\begingroup$ Is this the same as trees on unlabeled vertices? If so, it is oeis.org/A000055 $\endgroup$ Commented Mar 4, 2015 at 16:17
  • $\begingroup$ Not at all, two unlabeled trees may be isomorphic but the labeled version of the same trees may or may not be isomorphic . $\endgroup$
    – M a m a D
    Commented Mar 4, 2015 at 16:26
  • $\begingroup$ How are you defining isomorphic for the labeled version? I would think 1-3-2 and 1-2-3 are non-isomorphic as labeled trees because of the labeling, but isomorphic as unlabeled trees. If so, oeis.org/A000272 has the unrooted ones as $n^{n-2}$ and oeis.org/A000169 has the rooted ones as $n^{n-1}$ $\endgroup$ Commented Mar 4, 2015 at 16:29
  • $\begingroup$ In two isomorphic labeled trees, the degree of nodes with the same number is the same, so if $Deg(Node_1) = 3$ in $T_1$ then in $T_2$ , $Deg(Node_1) = 3$ as well but the only difference is its adjacent nodes. for example $Node_1$ in $T_1$ may be adjacent to $Node_3,Node_5,Node_6$ but in $T_2$ it may be adjacent to $Node_3,Node_2,Node_7$ $\endgroup$
    – M a m a D
    Commented Mar 4, 2015 at 16:34
  • $\begingroup$ When people refer to an "unlabeled tree" they really mean an isomorphism class of trees. So what do you mean by non-isomorphic labeled trees? Do you want a specific element of each isomorphism class as a labeled tree? If you choose a specific representative for each class, the number of representatives you have is the same as the number of unlabeled trees. $\endgroup$ Commented May 13, 2015 at 6:14

2 Answers 2

6
$\begingroup$

From your comment, it sounds like you consider two labeled trees isomorphic if they have the same (labeled) degree sequence. Thus to count the number of non-isomorphic labeled trees we'd want the number of labeled degree sequences of trees on $n$ vertices, which is ${2n-3 \choose n-1}$.

Why is it ${2n-3 \choose n-1}$? Well, a degree sequence corresponds to a tree if and only if every degree is at least 1 and the degree sum is 2n-2. Thus, we need the number of n-tuples of positive integers that sum to 2n-2, which is ${2n-3 \choose n-1}$.

$\endgroup$
0
$\begingroup$

It should be $C_{n-1}=\frac{1}{n}{2(n-1) \choose n-1}$, where $C_n$ is the $n^\text{th}$ Catalan number

$\endgroup$
1

You must log in to answer this question.

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