Information Technology Reference
In-Depth Information
In considering discrete structures, we discussed very often the passage from a rep-
resentation to another representation of the same structure. This is a crucial point
in their mathematical and computational analyses. A good representation has to
preserve the information. This means that it has to be possible to pass from a rep-
resentation of an object to another one of the same object and vice versa. However,
the equivalence of information content does not mean that two representations are
completely equivalent. In fact, very often, the information can be processed in a
better manner when an object is represented in one format rather than in another.
A typical example of this phenomenon is provided by the elementary arithmetical
algorithms, which can be easily defined within the positional representation of num-
bers, but become sometimes very difficult when numbers are represented in terms
of geometrical entities. In general, the computational evaluation of a representation
is an important issue in the algorithmic analysis of data structures and depends on
aspects related to the finality of their specific context of use. For example, the ad-
vantage of tag representations is given by the possibility of expressing, in textual
formats, complex information with graphical, and even multi-medial, features by
using only symbols of the standard 7-bit ASCII alphabet of 128 characters (Ameri-
can Standard Code for Information Interchange).
7.8.6
Tree Enumerations
Tree enumeration formulae are an old subject first investigated in connection to
chemical structures. In Knuth's topic [224] many classical results are reported for
different kinds of trees. Different notions of trees require different enumeration
methods. We recall briefly the aspects which are crucial in this regard. Trees can
be rooted or unrooted, ordered or unordered, or labeled or unlabeled. An unrooted
tree is a connected acyclic graph, while a rooted tree is an unrooted tree where a
node is chosen as an ancestor of all nodes of the tree. This means that a genealogi-
cal path with respect to the root can be assigned to every node of the tree. In ordered
trees, a generation order is established among the sons of a node, in unordered trees
no order is given among the sons of a node. In labeled trees all nodes are distinct,
while in unlabeled trees nodes are undistinguishable.
A
forest
is a sequence of trees (a multiset of trees, if order is not relevant). Of
course, there is a one-to-one correspondence between forests on
n
nodes and rooted
trees of
n
1 nodes. In fact, any tree becomes a forest after removing its root, and
conversely any forest become a tree if we add a node as father of the roots of the trees
in the forest. Forests of unlabeled ordered rooted trees on
n
nodes correspond to the
parenthesized expressions of
n
parenthesis pairs enumerated by Catalan numbers.
From this enumeration, the number
+
(
2
n
−
2
)
!
/
(
n
−
1
)
! of labeled ordered rooted
trees of
n
nodes easily follows.
For unlabeled unordered rooted trees no exact analytical formula is available,
but a recurrent formula, obtained by means of generating functions, was given by
