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(3): Recursive two-way formula. Fixed. higher numbers | Comment 8 of 9 |
(In reply to re(2): Recursive two-way formula. Fixed. by Charlie)

10   dim C(101)
20   C(0)=1:C(1)=0
30   for M=2 to 10
40   for N=0 to M-1
45     NewA=NewB:NewB=NewC
50     if N=0 then
60          :NewC=(M-N-1)*C(N)+(N+1)*C(N+1)
70      :else
80          :NewC=C(N-1)+(M-N-1)*C(N)+(N+1)*C(N+1)
90     if N>1 then C(N-2)=NewA
100   next N
110   C(M-1-1)=NewB
120   C(M-1)=NewC
130   for I=0 to 5:print C(I);:next:print
140   next M

produces

1  1  0  0  0  0
3  2  1  0  0  0
11  9  3  1  0  0
53  44  18  4  1  0
309  265  110  30  5  1
2119  1854  795  220  45  6
16687  14833  6489  1855  385  63
148329  133496  59332  17304  3710  616
1468457  1334961  600732  177996  38934  6678

in agreement with preceding results. So to concentrate on c(m,0),

10   dim C(101)
20   C(0)=1:C(1)=0
30   for M=2 to 100
40   for N=0 to M-1
45     NewA=NewB:NewB=NewC
50     if N=0 then
60          :NewC=(M-N-1)*C(N)+(N+1)*C(N+1)
70      :else
80          :NewC=C(N-1)+(M-N-1)*C(N)+(N+1)*C(N+1)
90     if N>1 then C(N-2)=NewA
100   next N
110   C(M-1-1)=NewB
120   C(M-1)=NewC
130   print M,C(0)
140   next M

produces as its last line:

100     34676123944005442812847937302043903452689441643429542833378834285512032
60126090875711931039414949888013971937935734182467628150127669980115929442267844
0577387

and

?c(0)/!(100)

produces
0.3715582355831567447

vs

?1/exp(1)
0.3678794411714423216

going to 190:

190     35799348103223117566105084598765100341973213200908910180351509436968639
07230395480033628646331069457419060059136995197620749634164592162812757990468067
70281753213194639252293432183703358965242856426674855916937858449410326212550498
52488869439961552434286458870848301141671946559692435778962276560277816296893615
59290609834987170335691325698600744922317

?c(0)/!(190)

produces
0.3698156487565551758

 Posted by Charlie on 2009-12-18 13:44:32

 Search: Search body:
Forums (0)