Information Technology Reference
In-Depth Information
Otter in the middle of last century, together with a complex asymptotic approximate
formula [232]. Recurrent formulae, deduced by means of elementary combinato-
rial arguments, but computationally less efficient than Otter's formula, are given in
[226, 227].
The number of labeled unordered rooted trees of
n
nodes is
n
n
−
1
. This formula
was discovered by Cayley. Here we present a proof of this result, which is based on
an interesting encoding of these trees as sequences of length
n
−
1 constructed over
the
n
nodes, due to Prufer [231], as reported in [224].
Encoding trees into sequences
.
Let
T
be a labeled rooted tree of
n
nodes numbered by 1
,
2
,...
n
. The following
procedure provides a sequence encoding
T
.For
i
=
1
,...
n
−
1, take the leaf
x
of
T
having the minimum index; set
x
i
=
father
(
x
)
and update
T
, by deleting
from
T
the node
x
and its edge. The sequence
(
x
1
,
x
2
,...,
x
n
−
1
)
is the encoding
of
T
.
Fig. 7.22
Representation of a tree of
n
nodes by means of sequence of length
n
−
1 over the
nodes
We can reverse the encoding process of trees given above. In fact, any sequence
of length
n
1 over
n
nodes uniquely individuates a labeled rooted tree over
n
nodes.
The following procedure allows us to reconstruct the tree of
n
nodes encoded by a
sequence of
n
−
−
1 nodes.
