I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from S_n are both asymptotically log n, and the distribution is asymptotically normal.

I want to know what a typical permutation of [n] with k(n) cycles "looks like" (in terms of cycle structure), where k(n)/(log n) → ∞ as n → ∞. The special case I have in mind is permutations of [n] with n^1/2 cycles, since I've come across such permutations in another context, but I'm also curious about the more general problem. In order to do this I would like an algorithm that generates permutations of n with k cycles uniformly at random -- that is, it generates each one with probability 1/S(n,k) where S(n,k) is a Stirling number of the first kind -- so that I can experiment on them. (I'd be willing to settle for a Markov chain that converges to this distribution if it does so reasonably quickly.)

Unfortunately the only way I know to do this is to take a permutation of [n] uniformly at random (this is easy) and then throw it out if it doesn't have k cycles. If k is far from log(n) this is very inefficient, since those permutations are rare.

A few references I've come across that are related: This paper of Granville looks at permutations with o(n^1/2-ε) cycles or Ω(n^1/2+ε) cycles and shows that their cycle lengths are "Poisson distributed", but right around n^1/2 is a transitional zone. And this paper of Kazimirov studies "the asymptotic behavior of various statistics" under the distribution I've claimed, but I haven't read it yet because I can't read Russian and I'm waiting for the English translation. Finally, the algorithm I'm looking for might be in one of the fascicles of volume 4 of Knuth, but our library doesn't have them.

I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from S_n are both asymptotically log n, and the distribution is asymptotically normal.

I want to know what a typical permutation of [n] with k(n) cycles "looks like" (in terms of cycle structure), where k(n)/(log n) → ∞ as n → ∞. The special case I have in mind is permutations of [n] with n^1/2 cycles, since I've come across such permutations in another context, but I'm also curious about the more general problem. In order to do this I would like an algorithm that generates permutations of n with k cycles uniformly at random -- that is, it generates each one with probability 1/S(n,k) where S(n,k) is a Stirling number of the first kind -- so that I can experiment on them. (I'd be willing to settle for a Markov chain that converges to this distribution if it does so reasonably quickly.)

Unfortunately the only way I know to do this is to take a permutation of [n] uniformly at random (this is easy) and then throw it out if it doesn't have k cycles. If k is far from log(n) this is very inefficient, since those permutations are rare.

A few references I've come across that are related: This paper of Granville looks at permutations with o(n^1/2-ε) cycles or Ω(n^1/2+ε) cycles and shows that their cycle lengths are "Poisson distributed", but right around n^1/2 is a transitional zone. And this paper of Kazimirov studies "the asymptotic behavior of various statistics" under the distribution I've claimed, but I haven't read it yet because I can't read Russian and I'm waiting for the English translation. Finally, the algorithm I'm looking for might be in one of the fascicles of volume 4 of Knuth, but our library doesn't have them.