8.5 The Number of Unlabeled Trees 1538.5 The Number of Unlabeled Trees
The number of unlabeled trees onnnodes, usually denoted byTn,iseven
more difficult to handle. No simple formula like Cayley’s theorem is known
for this number. Our goal is to get a rough idea of how large this number
is.
There is only one unlabeled tree on 1,2, or 3 nodes; there are two on
4 nodes (the path and the star). There are 3 on 5 nodes (the star, the
path, and the tree in Figure 8.3. These numbers are much smaller than the
number of labeled trees with these numbers of nodes, which are 1, 1 , 3 ,16,
and 125 by Cayley’s theorem.
It is of course clear that the number of unlabeled trees is less than the
number of labeled trees; every unlabeled tree can be labeled in many ways.
How many ways? If we draw an unlabeled tree, we can label its nodes inn!
ways. The labeled trees we get this way are not necessarily all different. For
example, if the tree is a star, then no matter how we permute the labels
of the leaves, we get the same labeled tree. So an unlabeled star yieldsn
labeled stars.
But at least we know that each labeled tree can be labeled in at mostn!
ways. Since the number of labeled trees isnn−^2 , it follows that the number
of unlabeled trees is at leastnn−^2 /n!. Using Stirling’s formula (Theorem
2.2.1), we see that this number is abouten/n^5 /^2
√
2 π.
This number is much smaller than the number of labeled trees,nn−^2 ,
but of course it is only alower boundon the number of unlabeled trees.
How can we obtain anupper boundon this number? If we think in terms of
storage, the issue is, can we store an unlabeled tree more economically than
labeling its nodes and then storing it as a labeled tree? Very informally,
how should we describe a tree if we want only the “shape” of it, and don’t
care which node gets which label?
Take ann-point treeG, and specify one of its leaves as its “root.” Next,
drawGin the plane without crossing edges; this can always be done, and
we almost always draw trees this way.
Now we imagine that the edges of the tree are walls, perpendicular to
the plane. Starting at the root, walk around this system of walls, keeping
the wall always to your right. We’ll call walking along an edge astep. Since
there aren−1 edges, and each edge has two sides, we’ll make 2(n−1)
steps before returning to the root (Figure 8.6).
Each time we make a stepawayfrom the root (i.e., a step from a father
to one of its sons), we write down a 1; each time we make a steptoward
the root, we write down a 0. This way we end up with a sequence of
length 2(n−1), consisting of 0’s and 1’s. We call this sequence theplanar
codeof the (unlabeled) tree. The planar code of the tree in Figure 8.6 is
1111100100011011010000.
Now this name already indicates that the planar code has the following
important property: