The limit distribution of the number of nodes in low strata of random mapping (Q584285): Difference between revisions

A mapping from a set into itself yields a graph in which each component has exactly one cycle. The \(k^{th}\)-stratum consists of those nodes at distance k from the nearest node on a cycle. Now consider a random mapping of an n-element set into itself. The asymptotic distribution of \(n^{-1/2}\) times the size of the \(O^{th}\)-stratum (the `cyclic nodes') is well known. (It has density function \(xe^{-x^ 2/2}\) for \(x>0.)\) In this paper, combinatorial arguments yield exact formulae for the first and second moments of the sizes of the different strata. Then asymptotic results are derived which show that \(n^{-1/2}\) times the size of the \(k^{th}\)-stratum has asymptotically the same distribution for each \(k=o(n^{1/2})\).