Problem:
Let be a uniformly random permutation of the set . The probability that and can be expressed as , where and are relatively prime positive integers. Compute . (Here, means iterated times.)
Solution
Solution:
We look at the cycles formed by . Let denote the smallest such that . In particular, the condition implies that and .
Claim 1. and cannot be in the same cycle.
Proof. If and were in the same cycle, then for some . Then since the cycle contains both and , but implies , a contradiction.
Claim 2. The probability that for some fixed such that is .
Proof. We can just count these permutations. We first choose elements of to be in the cycle of , then we similarly choose to be in the cycle of . We then have ways to reorder within the cycle of , ways to reorder within the cycle of , and ways to permute the remaining elements. The total number of ways is just
so the probability this happens is just .
Now, since and , we have possible values for and for , so in total we have a probability that the condition is satisfied.