39. A deck of n cards, numbered 1 through n, is randomly shuffled so that all n!

possible permutations are equally likely. The cards are then turned over one at a time until card number 1 appears. These upturned cards constitute the first cycle.

We now determine (by looking at the upturned cards) the lowest numbered card that has not yet appeared, and we continue to turn the cards face up until that card appears. This new set of cards represents the second cycle. We again determine the lowest numbered of the remaining cards and turn the cards until it appears, and so on until all cards have been turned over. Let mn denote the mean number of cycles.

(a) Derive a recursive formula for mn in terms of mk, k = 1,...,n − 1.

(b) Starting with m0 = 0, use the recursion to find m1,m2,m3, and m4.

(c) Conjecture a general formula for mn.

(d) Prove your formula by induction on n. That is, show it is valid for n = 1, then assume it is true for any of the values 1,...,n − 1 and show that this implies it is true for n.

(e) Let Xi equal 1 if one of the cycles ends with card i, and let it equal 0 otherwise, i=1,...,n. Express the number of cycles in terms of these Xi.

(f) Use the representation in part

(e) to determine mn.

(g) Are the random variables X1,...,Xn independent? Explain.

(h) Find the variance of the number of cycles.