What is Erdős–Turán “statistical group theory”? Erdős and Turán published a series of seven papers with this title, from 1965 to 1972, in which they proved many beautiful statistical or counting results about permutations. For example, if denotes the order of a permutation , they showed that when is chosen uniformly at random is approximately normally distributed, with mean and variance . Another typical result, though much simpler, is that if is any subset of , then the probability that a random permutation contains no cycle with length in is at most .

Although most of their results are of the above approximate nature, they prove at least one beautiful exact counting result, and I thought I might relate it here.

Theorem 1 If is a prime power then the proportion of with order not divisible by is exactly

Proof: The number of with cycles of length , cycles of length , , and cycles of length , where , is

Indeed, one can partition into sets of size for each in

ways, and then one can arrange each of the sets of size for each into cycles in

ways. Moreover, the order of every such is , so the order of is divisible by if and only if some is divisible by . (This is the where we use the hypothesis that is a prime power.) Thus the proportion of with order not divisible by is

where the sum runs over all and -tuples of positive integers such that and such that no is divisible by . But this is just the coefficient of in

where the last equality follows from the binomial formula. This completes the proof.

Such an explicit formula should make us feel foolish for having used generating functions. Is there a direct combinatorial proof?

By the way, for those who are not already aware of this invaluable resource, almost all of Erdős’s papers have been made freely available by the Renyi institute.