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

Home > Probability
Supreme Successive Shuffle (Posted on 2009-12-15) Difficulty: 4 of 5
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(2): Recursive two-way formula. Fixed. | Comment 7 of 9 |
(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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information