On the number of indecomposable permutations with a given number of cycles
The electronic journal of combinatorics, Tome 19 (2012) no. 1
A permutation $a_1a_2\ldots a_n$ is indecomposable if there does not exist $p such that $a_1a_2\ldots a_p$ is a permutation of $\{ 1,2,\ldots,p\}$. We consider the probability that a permutation of ${\mathbb S}_n$ with $m$ cycles is indecomposable and prove that this probability is monotone non-increasing in $n$.We compute also the asymptotic probability when $n$ goes to infinity with $m/n$ tending to a fixed ratio. 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.117\ldots$ percent) of the permutations are indecomposable.
@article{10_37236_2071,
author = {Robert Cori and Claire Mathieu and John Michael Robson},
title = {On the number of indecomposable permutations with a given number of cycles},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {1},
doi = {10.37236/2071},
zbl = {1243.05008},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2071/}
}
TY - JOUR AU - Robert Cori AU - Claire Mathieu AU - John Michael Robson TI - On the number of indecomposable permutations with a given number of cycles JO - The electronic journal of combinatorics PY - 2012 VL - 19 IS - 1 UR - http://geodesic.mathdoc.fr/articles/10.37236/2071/ DO - 10.37236/2071 ID - 10_37236_2071 ER -
%0 Journal Article %A Robert Cori %A Claire Mathieu %A John Michael Robson %T On the number of indecomposable permutations with a given number of cycles %J The electronic journal of combinatorics %D 2012 %V 19 %N 1 %U http://geodesic.mathdoc.fr/articles/10.37236/2071/ %R 10.37236/2071 %F 10_37236_2071
Robert Cori; Claire Mathieu; John Michael Robson. On the number of indecomposable permutations with a given number of cycles. The electronic journal of combinatorics, Tome 19 (2012) no. 1. doi: 10.37236/2071
Cité par Sources :