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
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 11:10:04 AM
Last modification on : Thursday, January 11, 2018 - 6:20:17 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:11:37 AM


Publisher files allowed on an open archive


  • HAL Id : hal-01185443, version 1



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. ⟨hal-01185443⟩



Record views


Files downloads