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?

Some thoughts. All m! permutations of m cards can be produced by inserting the card marked ‘m’ into each of the m possible places in each of the (m – 1)! permutations of m – 1 cards. If a(m – 1, k) is the number of permutations of m – 1 cards that contain k successive pairs (s-pairs), then the insertion of card ‘m’ will have one of the following effects. (A)An Insertion just after card ‘m – 1’ will increase the number of s-pairs by 1. (B)An insertion that splits an s-pair will decrease the number of s-pairs by 1. (C)An Insertion in any other place will not change the number of s-pairs. A, B and C can happen in 1, k and m – 1 – k ways respectively, and the resulting permutation will contain r s-pairs only if A, B and C are applied to permutations initially containing (k =) r – 1, r and r + 1 s-pairs respectively. This gives:

Using r = 0 in (1) gives:a(m, 0) = a(m – 1, 1) + (m – 1) a(m – 1, 0) and the using the fact that a(m - 1, 1) = (m – 2) a(m – 2, 0) gives:a(m, 0) = (m – 2) a(m – 2, 0) + (m – 1) a(m – 1, 0)

Abbreviating a(m, 0) to A(m) we can then write: A(m) = (m – 1) A(m – 1) + (m – 2) A(m – 2) with A(1) = A(2) = 1(2) where A(m) is the number of permutations of m cards that contain no s-pairs. [The number of perms with at least 1 s-pair will be m! – A(m)].

(2) allows easier evaluation of A(m) values, which are shown below together with A(m)/m! , the probability of no s-pairs.

It appears that the probability of having no s-pairs tends to a limit which could well be 1/e (whose value is 0.36787944117..). The probability of at least one s-pair would then be 1 – 1/e, as Charlie conjectured.

However, I’ve not yet proved that this is the limit, though (2) should be sufficient information to complete a proof. I’ll keep trying.