Quickselect and the distance to the identity permutation. (IV)

[Marko Riedel <mriedel@xxxxxxxxxxxxx>]

helmut@gauss.cam.wits.ac.za writes:
 > > with MAXIMA (the URL is http://www.ma.utexas.edu/maxima.html),
 > 
 > 
 > It does not seem to have an elementary solution. Perhaps A 
 > Panholzer can still do something about it, but it looked bad. 
 > 
 > As a consolation, I computed the coefficients of the expectation for 
 > you:
 > 
 > (n+1)n(n-1)/18-j/6(n+1)(n-1)+j^2/6(n-1)
 > 
 > 
[signature omitted]

Thanks. I checked your formula for small n and j, and it seems to be
correct.

Rewrite it as follows:


                   (n - 1) n (n + 1)   j (n - 1) (n - j + 1)
(D14)              ----------------- - ---------------------
                          18                     6

in order to see the symmetry wrt. j <-> n+1-j (the MAXIMA URL is

  http://www.ma.utexas.edu/maxima.html).

If I have time and if the material isn't too difficult for me I will
follow up on H.Prodinger's suggestion to study the case of median of
three quickselect, which is discussed in A. Panholzer's Ph.D. thesis
starting on page 193, the URL is

  http://www.wits.ac.za/helmut/pan.ps.gz.

Best regards,

Marko Riedel