Components and Cycles of Random Mappings

MaRDI QIDQ6398904zbMATH OpenFDO

Authors Steven R. Finch

Publication date 11 May 2022

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Population dynamics (general) (92D25) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Laplace transform (44A10) Evaluation of number-theoretic constants (11Y60) Functional-differential equations (including equations with delayed, advanced or state-dependent argument) (34Kxx)

Abstract: Each connected component of a mapping $1,2,\mathrm{...},nightarrow1,2,\mathrm{...},n$ contains a unique cycle. The largest such component can be studied probabilistically via either a delay differential equation or an inverse Laplace transform. The longest such cycle likewise admits two approaches: we find an (apparently new) density formula for its length. Implications of a constraint -- that exactly one component exists -- are also examined. For instance, the mean length of the longest cycle is $(\mathrm{0.7824...})sqrtn$ in general, but for the special case, it is $(\mathrm{0.7978...})sqrtn$, a difference of less than $2\mathrm{\%}$.

This page was built for publication: Components and Cycles of Random Mappings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6398904)