70. Let N denote the number of cycles that result in the match problem.

(a) Let Mn = E[N], and derive an equation for Mn in terms of M1,..., Mn−1.

(b) Let Cj denote the size of the cycle that contains person j. Argue that N = n j=1 1/Cj and use the preceding to determine E[N].

(c) Find the probability that persons 1, 2,..., k are all in the same cycle.

(d) Find the probability that 1, 2,..., k is a cycle.