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

Robert Cori, Claire Mathieu, John Michael Robson


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.

Full Text: PDF