TOPICS
Search

Erdős-Turán Theorem


For any integers a_i with

 1<=a_1<a_2<...<a_k<=n,

the proportion of permutations in the symmetric group S_n whose cyclic decompositions contain no cycles of lengths a_1, a_2, ..., a_k is at most

 (sum_(i=1)^k1/(a_i))^(-1)

(Erdős and Turán 1967, Dixon 1969).


See also

Permutation Cycle, Symmetric Group

Explore with Wolfram|Alpha

References

Dixon, J. D. "The Probability of Generating the Symmetric Group." Math. Z. 110, 199-205, 1969.Erdős, P. and Turán, P. "On Some Problems in Statistical Group Theory. II." Acta Math. Acad. Sci. Hung. 18, 151-163, 1967.

Referenced on Wolfram|Alpha

Erdős-Turán Theorem

Cite this as:

Weisstein, Eric W. "Erdős-Turán Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Erdos-TuranTheorem.html

Subject classifications