Permutations with roots

We prove that the probability p(2)(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 ha s an r th root, r prime, is monotonically nonincreasing in n. We also show for all r greater than or equal to 2 that p(r)(n) --> 0 as n --> infinity W hile 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 bi jections for sets of permutations defined by modular class restrictions on the cycle lengths. We also include a simple probabilistic proof that, for r greater than or equal to 2, p(r)(n) --> 0 as n --> infinity. (C) 2000 John Wiley & Sons, Inc.