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.

Improve this question
$\endgroup$
2

4 Answers 4

Reset to default
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)

Improve this answer
$\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

Improve this answer
$\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.

Improve this answer
$\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). $$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .