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(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