# Random mappings with a given number of cyclical points

Jennie C. Hansen, Jerzy Jaworski

Research output: Contribution to journalArticle

### Abstract

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.

Original language English 341-359 19 Ars Combinatoria 94 Published - Jan 2010

### Fingerprint

Random Mapping
Random Permutation
Random Forest
Random number
Order Statistics
Joint Distribution
Digraph
Asymptotic distribution
Dirichlet
Finite Set
Siméon Denis Poisson
Roots
Converge
Cycle

### Cite this

Hansen, Jennie C. ; Jaworski, Jerzy. / Random mappings with a given number of cyclical points. In: Ars Combinatoria. 2010 ; Vol. 94. pp. 341-359.
@article{20f66301f60242b593c3b74888c4d16a,
title = "Random mappings with a given number of cyclical points",
abstract = "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.",
author = "Hansen, {Jennie C.} and Jerzy Jaworski",
note = "The research in this paper was supported by the Marie Curie Intra-European Fellowship No. 501863 (RANDIGRAPH) within the 6th European Community Framework Programme.",
year = "2010",
month = "1",
language = "English",
volume = "94",
pages = "341--359",
journal = "Ars Combinatoria",
issn = "0381-7032",
publisher = "Charles Babbage Research Centre",

}

Random mappings with a given number of cyclical points. / Hansen, Jennie C.; Jaworski, Jerzy.

In: Ars Combinatoria, Vol. 94, 01.2010, p. 341-359.

Research output: Contribution to journalArticle

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

VL - 94

SP - 341

EP - 359

JO - Ars Combinatoria

JF - Ars Combinatoria

SN - 0381-7032

ER -