HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [13 references]

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

### 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⟩

Record views