Permutations with roots

We prove that the probability p₂(n) that a random permutation of length n has a square root is monotonically nonincreasing in n. More generally, we prove that the probability p_r(n) that a random permutation of length n has an rth root, r prime, is monotonically nonincreasing in n. We also show for all r≥2 that p_r(n)→0 as n→∞. While doing this, we combinatorially prove that p_r(n)=p_r(n+1) for r prime and for all n not congruent to −1 mod r, and we construct several bijections for sets of permutations defined by modular class restrictions on the cycle lengths. We also include a simple probabilistic proof that, for r≥2, p_r(n)→0 as n→∞. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 157–167, 2000