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 Some thoughts (Spoiler)
Your formula for A(m,r) is equivalent to mine. You also have a nice recursive A(m,0)=A(m) formula. This is included in the OEIS as http://www.research.att.com/~njas/sequences/A000255
The entry also gives an explicit formula:
a(n) = floor((1/e)*n!*(n+2)+1/2)
As n goes in infinity we can ignore the floor and +1/2
Also, this is offset by 1 so what we really want is
Posted by Jer
on 2009-12-18 16:37:57