A deck of M cards is numbered 1 to M and shuffled, and dealt from top to bottom.

Denoting the probability of dealing at least one pair of successive cards in their proper order (that is, a 1 followed by a 2 or, a 2 followed by a 3, and so on) at any position in the deck by s(M), determine s(M) as M → ∞ (The pairs may overlap. For example, for M=5, we have two successive pairs corresponding to 73452.)

As a bonus, what is the expected number of such successive pairs in an M card deck as a function of M?

(In reply to Recursive two-way formula. by Jer)

A little error.  My chart is in agreement with Charlies.  It was my formula that I typed in wrong.

C(M,N) = C(M-1,N-1) + (M-N-1)*C(M-1,N) + (N+1)*C(M-1,N+1)

Posted by Jer on 2009-12-17 10:16:29