We study random forests corresponding to random
mappings.
Mathematica 6 is used for modeling and visualization of results.
Let T_n={1, 2, ..., n} be a finite set with n elements. We
represent a single-valued mapping S of a set T_n onto itself as
/ 1 2 ... n \
S = | |,
\ s_1 s_2 ... s_n /
where s_k denotes the element of the set T_n into which the element k is
changed under the mapping S, k=1,2,...n. Mapping S can be represented
as a directed graph with one arc leading from each vertex and joining
the vertex to its image. The number of arcs incoming to the vertex is
called the indegree of this vertex. Any connected component of a mapping
graph contains exactly one cycle. After removing all arcs joining
cycling vertices we get a forest of rooted trees, where cycling vertices
are the trees roots and arcs are directed from vertices to the roots.
We call this forest a mapping forest.
The number of trees in this forest is equal to the number of cycling
points of corresponding random mapping.
Let SIGMA_n be the set of all single-valued mappings T_n onto
itself. We assume that the uniform distribution on the set SIGMA_n is
given. It means that every mapping has the probability n^(-n). There are
proved limit theorems for some characteristics of this set: the maximal
size of tree in mapping forest, numbers of trees of the given size and
the number of vertices with given indegree.
Our theoretical predictions for characteristics of forest of
random mappings are checked by simulations, namely the number of
vertices with given indegree. Random mapping of the set {1,2,,N}, where N
is large enough number (100 000, 1 000 000, etc.), is generated. This
mapping is further processed; its characteristics are calculated as well
as characteristics of the corresponding forest: number of the cycles,
number of the trees in the forest, etc. Number of the vertices with
given degree is also calculated. These parameters are compared to the
theoretically predicted values.
|