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 Sn 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 n1/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](http://www.combinatorics.org/Volume_13/JOC/v13i1r107p.pdf) looks at permutations with o(n1/2-ε) cycles or Ω(n1/2+ε) cycles and shows that their cycle lengths are "Poisson distributed", but right around n1/2 is a transitional zone. And [this paper of Kazimirov](http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dm&paperid=212&option_lang=eng) 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.



How can I generate random permutations of [n] with k cycles, where k is much larger than log n?
Youll find the answer on page 38 of my lecture notes East Side, West Side, which are a free download from my web site. It's a complete, short Maple program. The problem was originally solved in 1978 in Combinatorial Algorithms, by Albert Nijenhuis and myself.


Herb Wilf 


