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 For M=1 to 10 by counting---plus conjecture by Charlie)

Looking up the last column in Sloane's OLEoIS, we find n*n!, which here equates to (M-1)*(M-1)!, so the expected number of successive matches comes out to  (M-1)*(M-1)! / M! = (M-1)/M, which does indeed approach 1.

Sloane is tantalizing on the "at least one hit" column, as there is a sequence that begins 1,3,13,67,411, but the next entry is 2911 rather than 2921, and there is no 0 before the 1.

Posted by Charlie on 2009-12-15 12:12:20