[Information Index] [Generation Index] [COS homepage]

Information on Free Plane Trees

A free tree is an undirected graph that is both connected and acyclic. A free tree that has been embedded in the plane is called a free plane tree.

We represent a free tree as a rooted tree by picking a centroid of the free tree to be the root. The size of a subtree is the number of nodes it contains. A node is a centroid of a tree if the size of the largest subtree that results when the node is removed is minimum. For trees, there might be either one or two centroids. If it has one centroid, we say that it is unicentroidal; if it has two centroids then we say that it is bicentroidal. A node v is a unique centroid if and only if the size of the largest subtree that results when v is removed is less than or equal to (n-1)/2. If a tree has two centroids then they are adjacent and the removal of the edge connecting them splits the tree into two substrees, each with n/2 nodes. Each unlabeled free plane tree is uniquely represented by a canonic rooted plane tree.

The figure on the left shows a free plane tree with two centroids, a and b. The figure on the right shows a free plane tree with only one centroid a. When a tree has two centroids, we can simply generate two level sequences of size n/2 (corresponding to the two subtrees obtained when the edge is removed between the two centroids) such that the second level sequence is lexicographically greater than or equal to the first level sequence. Then by adding 1 to each value in the second level sequence and appending it to the first level sequence, we obtain a rooted plane tree with n nodes whose root is the canonical centroid. This final step joins the two centroids back together by making the second centroid a child of the canonical centroid. The level sequence of the free plane tree on the left is 0 1 1 1 1 2 2 2, the one on the right is 0 1 1 2 1 2 2.

Our program will generate free plane trees of n nodes using the level sequence representation. An alternative representation is that of the parent array. For more information on the level sequence and parent array representations, see the rooted plane tree information page.

Let r(n) denote the number of non-isomorphic rooted plane trees with n nodes.

r(n+1)   =  
 1
2n
 
__
\
/   
d | n
Ø(n/d) (
2d
d
)
 

Let f(n) denote the number of non-isomorphic free plane trees with n nodes.
f(n)   =   r(n) -  
 1
2n
(
2(n-1)
n-1
)  + 
 1
 n
(
n-2
(n/2)-1
)

For n = 1,2,3,...,29, 30 the number f(n) of free plane trees is 1, 1, 1, 1, 2, 3, 6, 14, 34, 95, 280, 854, 2694, 8714, 28640, 95640, 323396, 1105335, 3813798, 13269146,46509358, 164107650, 582538732, 2079165208, 7457847082, 26873059986, 97239032056, 353218528324, 1287658723550, 4709785569184.

This is sequence A002995 (Formerly M0805) in Neil J. Sloane's database of integer sequences. This sequence also corresponds to the number of non-crossing handshakes of 2(n-1) people (each using only one hand) at a round table, up to rotations.


COS options

In COS the user can output the level sequence (standard representation) or the parent array (alternate representation). The algorithm used in COS is from Joe Sawada, Generating rooted and free plane trees, 2002, submitted to ACM Transactions on Algorithms.


Programs available:
[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Tuesday, 24-May-2011 10:59:34 PDT.
There have been 4711 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.