TY - JOUR
T1 - Random mappings with a given number of cyclical points
AU - Hansen, Jennie C.
AU - Jaworski, Jerzy
N1 - The research in this paper was supported by the
Marie Curie Intra-European Fellowship
No. 501863 (RANDIGRAPH) within the 6th European Community Framework Programme.
PY - 2010/1
Y1 - 2010/1
N2 - In this paper we consider a random mapping, T^n, of the finite set {1, 2,..., n} into itself for which the digraph representation Gn is constructed by: (1) selecting a random number, L^n, of cyclic vertices, (2) constructing a uniform random forest of size n with the selected cyclic vertices as roots, and (3) forming 'cycles' of trees by applying a random permutation to the selected cyclic vertices. We investigate k^n, the size of a 'typical' component of Gn, and, under the assumption that the random permutation on the cyclical vertices is uniform, we obtain the asymptotic distribution of k^n conditioned on L^n = m(n). As an application of our results, we show in Section 3 that provided L^n is of order much larger than vn, then the joint distribution of the normalized order statistics of the component sizes of Gn converges to the Poisson-Dirichlet(1) distribution as n ? 8. Other applications and generalizations are also discussed in Section 3.
AB - In this paper we consider a random mapping, T^n, of the finite set {1, 2,..., n} into itself for which the digraph representation Gn is constructed by: (1) selecting a random number, L^n, of cyclic vertices, (2) constructing a uniform random forest of size n with the selected cyclic vertices as roots, and (3) forming 'cycles' of trees by applying a random permutation to the selected cyclic vertices. We investigate k^n, the size of a 'typical' component of Gn, and, under the assumption that the random permutation on the cyclical vertices is uniform, we obtain the asymptotic distribution of k^n conditioned on L^n = m(n). As an application of our results, we show in Section 3 that provided L^n is of order much larger than vn, then the joint distribution of the normalized order statistics of the component sizes of Gn converges to the Poisson-Dirichlet(1) distribution as n ? 8. Other applications and generalizations are also discussed in Section 3.
UR - http://www.scopus.com/inward/record.url?scp=77949525176&partnerID=8YFLogxK
M3 - Article
SN - 0381-7032
VL - 94
SP - 341
EP - 359
JO - Ars Combinatoria
JF - Ars Combinatoria
ER -