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)

I think this recursive program follows your formulae:

DECLARE FUNCTION c! (m!, n!)
FOR m = 2 TO 10
  FOR n = 0 TO m - 1
    PRINT USING "#######"; c(m, n);
  NEXT
  PRINT
NEXT

FUNCTION c (m, n)
 IF m = 1 THEN
   IF n = 0 THEN c = 1:  ELSE c = 0
 ELSE
   c = c(m - 1, n - 1) + (m - n - 1) * c(m - 1, n) + n * c(m - 1, n + 1)
 END IF
END FUNCTION

However it produces:

 M       N:   0      1      2      3      4      5     6       7      8      9
 2            1      1
 3            1      2      1
 4           -1      6      3      1
 5          -19     20     14      4      1
 6         -151     75     70     25      5      1
 7        -1091    294    405    160     39      6      1
 8        -7841   1078   2639   1162    301     56      7      1
 9       -56519   2344  19236   9352   2590    504     76      8      1
10      -396271 -18531 155700  83118  24318   4986    780     99      9      1

Even discounting the spurious n=0 counts, the c(4,1) figure comes out as 6: c(3,0)+2*c(3,1)+1*c(3,2) = 1+2*2+1*1 = 6. In fact c(4,1) is 9. Even if c(3,0) were the correct 3, the formula would still give only 8, rather than 9 for c(4,1).

The 9 that make up c(4,1):

1243
1342
1423
2134
2314
3124
3421
4231
4312

Posted by Charlie on 2009-12-17 03:25:01