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
**A000081**(M1180) in
Neil J. Sloane's
database
of integer sequences.

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
**A001190**(M0790) in
Neil J. Sloane's
database
of integer sequences.

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
**A000598**(M1146) in
Neil J. Sloane's
database
of integer sequences.

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
**A036718** in
Neil J. Sloane's
database
of integer sequences.

The asymptotic number of binary rooted trees has been studied by Otter and others. You may click here for further information.

n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

1 | |||||||||||||||

2 | 1 | ||||||||||||||

3 | 1 | 1 | |||||||||||||

4 | 1 | 2 | 1 | ||||||||||||

5 | 1 | 4 | 3 | 1 | |||||||||||

6 | 1 | 6 | 8 | 4 | 1 | ||||||||||

7 | 1 | 10 | 18 | 13 | 5 | 1 | |||||||||

8 | 1 | 14 | 38 | 36 | 19 | 6 | 1 | ||||||||

9 | 1 | 21 | 76 | 93 | 61 | 26 | 7 | 1 | |||||||

10 | 1 | 29 | 147 | 225 | 180 | 94 | 34 | 8 | 1 | ||||||

11 | 1 | 41 | 277 | 528 | 498 | 308 | 136 | 43 | 9 | 1 | |||||

12 | 1 | 55 | 509 | 1198 | 1323 | 941 | 487 | 188 | 53 | 10 | 1 | ||||

13 | 1 | 76 | 924 | 2666 | 3405 | 2744 | 1615 | 728 | 251 | 64 | 11 | 1 | |||

14 | 1 | 100 | 1648 | 5815 | 8557 | 7722 | 5079 | 2593 | 1043 | 326 | 76 | 12 | 1 | ||

15 | 1 | 134 | 2912 | 12517 | 21103 | 21166 | 15349 | 8706 | 3961 | 1445 | 414 | 89 | 13 | 1 |

The sum of the first two columns is the number of numerical partitions of *n*+1.
The sum of the first three columns is
**Sloane's A001383**(M1107).
The sum of the first four columns is
**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.

Programs available:

(Please note that the suffix XXXX must be removed from the preceeding email address.)

It was last updated Tuesday, 24-May-2011 10:56:18 PDT.

[Error Opening Counter File -- Click for more info]

©Frank Ruskey, 1995-2003.