5
$\begingroup$

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.

$\endgroup$
2

4 Answers 4

4
$\begingroup$

Perhaps this article might be of use?

https://www.jstor.org/stable/1994483

(L. A. Shepp and S. P. Lloyd: Ordered cycle lengths in a random permutation)

$\endgroup$
2
$\begingroup$

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)

Link

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.

https://arxiv.org/abs/1001.1894

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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). $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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