=+7. A permutation that satisfies the equation ((i)) = i for all i is called an involution

=+7. A permutation that satisfies the equation π(π(i)) = i for all i is called an involution [139]. Prove that a random permutation of {1,...,n}

is an involution with probability

 n 2



k=0 1

2kk!(n − 2k)!.

(Hint: An involution has only fixed points and two-cycles. Count the number of involutions and divide by n!.)