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
re: Recursive two-way formula. Fixed. by Jer)
Indeed with the corrected formula, the numbers look better:
M N: 0 1 2 3 4 5 6 7 8 9
2 1 1
3 3 2 1
4 11 9 3 1
5 53 44 18 4 1
6 309 265 110 30 5 1
7 2119 1854 795 220 45 6 1
8 16687 14833 6489 1855 385 63 7 1
9 148329 133496 59332 17304 3710 616 84 8 1
10 14684571334961 600732 177996 38934 6678 924 108 9 1
from
defdbl a-z
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 + 1) * c(m - 1, n + 1)
END IF
END FUNCTION
The recursive nature leads to stack space problems, but, going up to M=15, for N=0, we get:
2 1
3 3
4 11
5 53
6 309
7 2119
8 16687
9 148329
10 1468457
11 16019531
12 190899411
13 2467007773
14 34361893981
15 513137616783
And 15! is 1307674368000 so the probability of no hits among 15 cards is 513137616783/1307674368000 or 0.3924047372495413169 vs 1/e = 0.3678794411714423216.
I'll have to work on going to higher numbers.
|
|
Posted by Charlie
on 2009-12-18 12:32:22 |
re(2): Recursive two-way formula. Fixed.
