Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Cycle lengths in a permutation are typically Poisson. | Cycle lengths in a permutation are typically Poisson Andrew Granville Department de mathématiques et de statistique Universite de Montréal Montreal QC H3C 3J7 Canada andrew@ Submitted May 3 2006 Accepted Nov 10 2006 Published Nov 17 2006 Mathematics Subject Classifications Primary 62E20 Secondary 62E17 05A16. Abstract The set of cycle lengths of almost all permutations in Sn are Poisson distributed we show that this remains true even when we restrict the number of cycles in the permutation. The formulas we develop allow us to also show that almost all permutations with a given number of cycles have a certain normal order in the spirit of the Erdos-Turan theorem . Our results were inspired by analogous questions about the size of the prime divisors of typical integers. 1 Introduction Define Sn to be the set of permutations on n letters and let t ơ be the number of cycles of ơ 2 Sn. It is well-known that ơ log n for almost all ơ 2 Sn a fact we will reprove in Section 2 . More precisely we mean that for any Ỗ e 0 if n is sufficiently large then 1 Ố log n ơ 1 Ố log n for all but at most e n permutations ơ 2 Sn. Write ơ C1C2 C where the C ịS are cycles and ơ and let dị ơ d Ci be the number of elements of Gj. We may order the cycles so that 1 d1 ơ d2 ơ d ơ n and therefore 0 log di ơ log d2 ơ log d ơ log n. Thus for almost all ơ 2 Sn we have log n numbers log dị ơ in an interval 0 log n of length log n. How are these numbers distributed within the interval Other than near the L auteur est partiellement soutenu par une bourse de la CRSNG du Canada. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R107 1 beginning and end of the interval we might for want of a better idea guess that these numbers are randomly distributed in some appropriate sense given that the average gap is 1. That guess correctly formulated turns out to be correct. In probability theory one uses the notion of a Poisson point process when one wishes to show that the event times of a random
