Permutations With Equal Orders

Abstract

Let $P(n)$ be the probability that two independent, uniformly random permutations of $[n]$ have the same order, and let $K(n)$ be the probability that they are in the same conjugacy class. Answering a question of Thibault Godin, we prove that $P(n)=n^{-2+o(1)}$ and that $\lim \sup \frac{P(n)}{K(n)}=\infty .$

To appear in CPC. Added open problems, history, and a more quantitative lower bound