On fixed points of permutations

The number of fixed points of a random permutation of {1,2,…,n} has a limiting Poisson distribution. We seek a generalization, looking at other actions of the symmetric group. Restricting attention to primitive actions, a complete classification of the limiting distributions is given. For most examples, they are trivial – almost every permutation has no fixed points. For the usual action of the symmetric group on k-sets of {1,2,…,n}, the limit is a polynomial in independent Poisson variables. This exhausts all cases. We obtain asymptotic estimates in some examples, and give a survey of related results. This paper is dedicated to the life and work of our colleague Manfred Schocker. We thank Peter Cameron for his help. Diaconis was supported by NSF grant DMS-0505673. Fulman received funding from NSA grant H98230-05-1-0031 and NSF grant DMS-0503901. Guralnick was supported by NSF grant DMS-0653873. This research was facilitated by a Chaire d’Excellence grant to the University of Nice Sophia-Antipolis.