Special Session on Applications of Math Software to Mathematical Research

 

Title:   Modeling of the forest of random mapping with Mathematica.

Tatiana Myllari
Abo Akademi University, Turku/Abo, Finland

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.