All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Supreme Successive Shuffle (Posted on 2009-12-15)
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?

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 re: Recursive two-way formula. | Comment 4 of 9 |
(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      110      -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

 Search: Search body:
Forums (45)