A rooted tree may be regarded as an equivalence class of ordered trees. Two ordered trees are equivalent if one may be transformed into the other by re-ordering subtrees. In the figure above the number of ordered trees in the equivalence class of each rooted tree is 1, 1, 2, 2, 1, 2, 1, 3, 1, respectively. The sum of these numbers is 14, the 5th Catalan number and the number of ordered trees on 5 nodes.
One natural way of encoding an ordered tree is to record the parent of each node in preorder. In the figure on the left each node points to its parent. Taking 0 to be the parent of the root, the sequence obtained is 0121156685. This is called the parent array.
Another way of encoding an ordered tree is to record the level (distance from the root) at which its nodes occur in preorder. In the tree shown on the right the numbers give a preorder labelling and by recording the level number of those nodes we obtain the sequence 0121123342. This is called the level sequence.
The two trees shown above are the same when regarded as unlabelled rooted trees, since one may be obtained from the other by reordering subtrees. Among all ordered trees that are equivalent we choose the one whose parent array is lexicographically largest (i.e., biggest when regarded as a number) and call it canonic. By generating canonic ordered trees, we generate all rooted trees. The second tree illustrated is canonic (the one with parent array 0123432181). Intuitively, we transform an ordered tree into a canonic tree by recursively pushing subtrees with greater height to the left. The list of all trees with 5 nodes shown at the top of this page shows the canonic tree from each equivalence class.
For n = 1,2,3,...,15 the number of rooted trees is 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811. This is sequence Anum=A000081"> A000081(M1180) in
The number of binary rooted trees with n = 1,2,3,...,15 internal nodes is 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, respectively. This is sequence Anum=A001190"> A001190(M0790) in
Rooted trees where each node has at most 3 children are sometimes called quartic planted trees. For n = 1,2,3,...,15 internal nodes, there are 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241, 48865 of them, respectively. This is sequence Anum=A000598"> A000598(M1146) in
Rooted trees where each node has at most 4 children are counted for n = 1,2,3,...,20 nodes, by the numbers 1, 1, 2, 4, 9, 19, 45, 106, 260, 643, 1624, 4138, 10683, 27790, 72917, 192548, 511624, 1366424, 3666930, 9881527, respectively. This is sequence Anum=A036718"> A036718 in
The asymptotic number of binary rooted trees has been studied by Otter and others. You may click here for further information.
The sum of the first two columns is the number of numerical partitions of n+1. The sum of the first three columns is Anum=A001383"> Sloane's A001383(M1107). The sum of the first four columns is Anum=A001384"> Sloane's A001384(M1172).
In COS the user can output the parent array (standard representation) or the level sequence (alternate representation). An upper bound on the number of children of a node can be specified (as m). Upper and lower bounds on the height can also be specified (as lb and ub). The algorithm used in COS is from Gang Li and Frank Ruskey, The Advantages of Forward Thinking in Generating Rooted and Free Trees, 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (1999) S939-940.