Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Are there any good references (either books or on-line) on the subject of the distribution of various cycle properties amongst permutations, particularly ones containing exact, closed-forms?

For example, what is the probability that a random permutation of N objects contains some cycle having length between A and B? Or, what is the probability that all cycles in a random permutation of N objects have lengths between A and B?

I would be particularly interested in references that survey what is known in this field, preferably with a little detail.

Thanks.

share|improve this question
5  
google is your friend: en.wikipedia.org/wiki/Random_permutation_statistics –  Suresh Venkat Jul 23 '10 at 23:38
2  
Wikipedia article doesn't appear to contain survey or textbook references. –  Victor Protsak Jul 24 '10 at 5:26

4 Answers 4

Perhaps this article might be of use?

http://www.jstor.org/pss/1994483

(Ordered cycle lengths in a random permutation)

share|improve this answer

The following paper may be what you're looking for:

Schramm, Oded. Compositions of random transpositions. Israel J. Math. 147 (2005), 221--243. MR2166362 (2006h:60024)

http://www.springerlink.com/content/f572513876635mj5/

This paper is concerned with the distribution of a random permutation in $S_n$ generated by $c n$ random transpositions (where $c>1/2$). Schramm calculates the limiting distribution of the cycle lengths (ordered from largest to smallest).

A recent paper of Nathanael Berestycki, Oded Schramm, and Ofer Zeitouni has extended the techniques of Schramm's earlier paper to the case where the random permutation is generated by random $k$-cylces. I don't know if this recent paper answers the same questions, but it might be relevant.

http://arxiv.org/abs/1001.1894

share|improve this answer

The following paper:

On the distribution of the length of the longest increasing subsequence of random permutations J. Baik, P Deift, K Johansson - Journal of the American Mathematical, 1999

https://www.ams.org/journals/jams/1999-12-04/S0894-0347-99-00307-0/S0894-0347-99-00307-0.pdf

is fairly recent and contains at least a solution to a related problem. Maybe the literature revue is helpful or the translation to young tableaus.

share|improve this answer

The exponential generating function of the number of permutations of length $n$ such than all their cycle sizes are in a certain set $A\subset \mathbb N$ is $$ P(z) = \exp\left(\sum_{n\in A}\frac{z^n}{n}\right). $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.