ng n distinct integers in just his thoughts.
He plays turns on the list. In each turn he does the following–
He takes a number (in its index’s order ) and swap it with any number in
the list including itself i.e. if it swap it with itself it doesn’t move at all (The
selection of the number is completely random).
He does the same for all the elements in their index’s order in that turn.
If initially the list was unsorted, such that, no element was in sorted position,
then find the probability that the list is sorted after m such turns.
Note : Take the assumption that if an element is not in its sorted
position then it can be in any other n − 1 positions equally likely.