On the number of indecomposable permutations with a given number of cycles (Q426818)

Summary: 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.