On the Number of Indecomposable Permutations with a Given Number of Cycles

Source abstract

A permutation $a_1a_2\ldots a_n$ is indecomposable if there does not exist $p<n$ 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.