HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Indecomposable permutations with a given number of cycles

Abstract : A permutation $a_1a_2 \ldots a_n$ is $\textit{indecomposable}$ if there does not exist $p \lt n$ such that $a_1a_2 \ldots a_p$ is a permutation of $\{ 1,2, \ldots ,p\}$. We compute the asymptotic probability that a permutation of $\mathbb{S}_n$ with $m$ cycles is indecomposable as $n$ goes to infinity with $m/n$ fixed. The error term is $O(\frac{\log(n-m)}{ n-m})$. The asymptotic probability is monotone in $m/n$, and there is no threshold phenomenon: it degrades gracefully from $1$ to $0$. When $n=2m$, a slight majority ($51.1 \ldots$ percent) of the permutations are indecomposable. We also consider indecomposable fixed point free involutions which are in bijection with maps of arbitrary genus on orientable surfaces, for these involutions with $m$ left-to-right maxima we obtain a lower bound for the probability of being indecomposable.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal.inria.fr/hal-01185443
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, August 20, 2015 - 11:10:04 AM
Last modification on : Monday, December 20, 2021 - 4:50:12 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:11:37 AM

File

dmAK0125.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Robert Cori, Claire Mathieu. Indecomposable permutations with a given number of cycles. 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), 2009, Hagenberg, Austria. pp.301-312, ⟨10.46298/dmtcs.2750⟩. ⟨hal-01185443⟩

Share

Metrics

Record views

70

Files downloads

303