# Number of labeled non-isomorphic trees on $n$ vertices

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

• Is this the same as trees on unlabeled vertices? If so, it is oeis.org/A000055 Commented Mar 4, 2015 at 16:17
• Not at all, two unlabeled trees may be isomorphic but the labeled version of the same trees may or may not be isomorphic . Commented Mar 4, 2015 at 16:26
• 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}$ Commented Mar 4, 2015 at 16:29
• 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$ Commented Mar 4, 2015 at 16:34
• 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. Commented May 13, 2015 at 6:14

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}$.
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