In the match problem, say that (i, j ), i < j , is a pair if i chooses j ’s hat and j chooses i’s hat.

(a) Find the expected number of pairs.

(b) Let Qn denote the probability that there are no pairs, and derive a recursive formula for Qn in terms of Qj , j

Hint: Use the cycle concept.

(c) Use the recursion of part

(b) to find Q8.