Problem:
Let be a permutation chosen uniformly at random from the possible permutations. Compute the expected value of .
Solution
Solution:
We first compute the probability that . Note that if and only if is part of a cycle whose length divides .
We claim that for any given , the probability that is in a cycle of length is . Indeed, the probability that is . Given this, there are possible values remaining for , so the probability that is , and so on. Finally, there are possible values remaining for , so the probability that given all previous assumptions is . Thus, the probability that is in a cycle of length is
Hence, the probability that is the probability that is in a cycle of length , , , or , which is .
If , then is equally likely to be any of through by symmetry, averaging .
Therefore, the expected value of is
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.