# Quickselect and the number of cycles. (VII)

```

Greetings.

I am very happy to announce that I have solved the DE for the expected
number of cycles of length less than or equal to \$n after a single
quickselect. Commentary is invited, especially if you have verified my
results. I would be very glad if someone were to check my results with
MAPLE.

The solution works as follows: I wrote a Perl script that outputs a
MAXIMA script (the URL is http://www.ma.utexas.edu/maxima.html; MAXIMA
was easy to install on two of the SuSE Linux machines that I use at
work) that solves the DE.

Here are the first few solutions:

n=1
2 LOG(1 - u z)           3 u z          2 u LOG(1 - z)
(D35)     - ----------------- - ----------------- - -----------------
(1 - z) (1 - u z)   (1 - z) (1 - u z)   (1 - z) (1 - u z)
n=2
2  2      2
u  z    u z
- ----- - ---- - 4 u z
5 LOG(1 - u z)          4      4               5 u LOG(1 - z)
(D42) - ------------------- + ---------------------- - -------------------
2 (1 - z) (1 - u z)     (1 - z) (1 - u z)      2 (1 - z) (1 - u z)
n=3
3  3      3      2  2        2
u  z    u z    5 u  z    5 u z    14 u z
- ----- - ---- - ------- - ------ - ------
17 LOG(1 - u z)         9      9       12        12       3
(D51) - ------------------- + ------------------------------------------
6 (1 - z) (1 - u z)               (1 - z) (1 - u z)

17 u LOG(1 - z)
- -------------------
6 (1 - z) (1 - u z)
n=4
37 LOG(1 - u z)
(D62) - --------------------
12 (1 - z) (1 - u z)

4  4      4      3  3        3       2  2         2
u  z    u z    7 u  z    7 u z    13 u  z    13 u z    31 u z
- ----- - ---- - ------- - ------ - -------- - ------- - ------
16      16      36        36        24        24        6
+ ---------------------------------------------------------------
(1 - z) (1 - u z)

37 u LOG(1 - z)
- --------------------
12 (1 - z) (1 - u z)
n=5
5  5      5      4  4        4       3  3
197 LOG(1 - u z)        u  z    u z    9 u  z    9 u z    47 u  z
(D75) - -------------------- + (- ----- - ---- - ------- - ------ - --------
60 (1 - z) (1 - u z)       25      25      80        80       180

3       2  2         2
47 u z    77 u  z    77 u z    167 u z
- ------- - -------- - ------- - -------)/((1 - z) (1 - u z))
180       120        120       30

197 u LOG(1 - z)
- --------------------
60 (1 - z) (1 - u z)
n=6
6  6      6       5  5         5       4  4
69 LOG(1 - u z)         u  z    u z    11 u  z    11 u z    37 u  z
(D90) - -------------------- + (- ----- - ---- - -------- - ------- - --------
20 (1 - z) (1 - u z)       36      36      150        150       240

4       3  3         3       2  2         2
37 u z    19 u  z    19 u z    29 u  z    29 u z    59 u z
- ------- - -------- - ------- - -------- - ------- - ------)
240        60        60         40        40        10

69 u LOG(1 - z)
/((1 - z) (1 - u z)) - --------------------
20 (1 - z) (1 - u z)

These solutions can be used to investigate the limiting case where all
cycles are counted. This might be necessary if the DE for the number
of cycles of any size after a single quickselect does not immediately
yield a closed-form solution.

Can you predict the scalar of the two logarithmic terms?

Best regards,

Marko Riedel

----------------------------------------------------------------------
Here's the MAXIMA script for n=2 as output by the Perl script.

1/(1-z);
1/(1-z)*(z+z^2/2);
z*u/(1-z)/(1-z*u);
u*SUBST(z*u, z, D1)*D3;
u*SUBST(z*u, z, D2)*D3;
u*SUBST(z*u, z, D1)*G(z);
u*SUBST(z*u, z, D1)*D1;
u*SUBST(z*u, z, D2)*D1;
u*SUBST(z*u, z, D1)*D2;
D1*D3;
D2*D3;
D1*G(z);
FACTOR(RAT(D4+D5+D7+D8+D9+D10+D11));
FACTOR(RAT(D6+D12));
f*u/(1-z)/(1-z*u)*log(1/(1-z));
f/(1-z)/(1-z*u)*log(1/(1-z*u));
(a0b0 + a0b1*u^0*z^1 + a0b2*u^0*z^2 + a0b3*u^0*z^3 + a1b0*u^1*z^0 + a1b1*u^1*z^1
+ a1b2*u^1*z^2 + a1b3*u^1*z^3 + a2b0*u^2*z^0 + a2b1*u^2*z^1 + a2b2*u^2*z^2 + a2
b3*u^2*z^3 + a3b0*u^3*z^0 + a3b1*u^3*z^1 + a3b2*u^3*z^2 + a3b3*u^3*z^3);
D15+D16+D17/(1-z)/(1-z*u);
EXPAND(RAT((1-z)^2*(1-z*u)^2*DIFF(D15+D16, z)+DIFF(D17, z)*(1-z)*(1-z*u)-D17*DIF
F((1-z)*(1-z*u), z)));
EXPAND(RAT((1-z)^2*(1-z*u)^2*D13));
RAT(SUBST((D15+D16)*(1-z)^2*(1-z*u)^2+D17*(1-z)*(1-z*u), G(z), D14));
EXPAND(D19-D20-D21);
COEFF(COEFF(D22, u, 0), z, 0)=0;
COEFF(COEFF(D22, u, 0), z, 1)=0;
COEFF(COEFF(D22, u, 0), z, 2)=0;
COEFF(COEFF(D22, u, 0), z, 3)=0;
COEFF(COEFF(D22, u, 1), z, 0)=0;
COEFF(COEFF(D22, u, 1), z, 1)=0;
COEFF(COEFF(D22, u, 1), z, 2)=0;
COEFF(COEFF(D22, u, 1), z, 3)=0;
COEFF(COEFF(D22, u, 2), z, 0)=0;
COEFF(COEFF(D22, u, 2), z, 1)=0;
COEFF(COEFF(D22, u, 2), z, 2)=0;
COEFF(COEFF(D22, u, 2), z, 3)=0;
COEFF(COEFF(D22, u, 3), z, 0)=0;
COEFF(COEFF(D22, u, 3), z, 1)=0;
COEFF(COEFF(D22, u, 3), z, 2)=0;
COEFF(COEFF(D22, u, 3), z, 3)=0;
LINSOLVE([D23, D24, D25, D26, D27, D28, D29, D30, D31, D32, D33, D34, D35, D36,
D37, D38],
[f, a0b0, a0b1, a0b2, a0b3, a1b0, a1b1, a1b2, a1b3, a2b0, a2b1, a2b2, a2b3, a3b0
, a3b1, a3b2, a3b3]);
SUBLIS(D39, D18);
[%R1=0, %R2=0, %R3=0, %R4=0, %R5=0, %R6=0, %R7=0, %R8=0, %R9=0, %R10=0, %R11=0,
%R12=0, %R13=0, %R14=0, %R15=0, %R16=0];
SUBLIS(D41, D40);

----------------------------------------------------------------------

#! /usr/bin/perl -w
#

MAIN: {
my (\$n, \$k, \$l) = @ARGV;

die "\$0 <n> where <n> ism positive\n"
if not defined \$n or \$n<1;

print "1/(1-z);\n";

print "1/(1-z)*(z";
for(\$k=2; \$k<=\$n; \$k++){
print "+z^\$k/\$k";
}
print ");\n";

print "z*u/(1-z)/(1-z*u);\n";

print "u*SUBST(z*u, z, D1)*D3;\n";
print "u*SUBST(z*u, z, D2)*D3;\n";
print "u*SUBST(z*u, z, D1)*G(z);\n";
print "u*SUBST(z*u, z, D1)*D1;\n";
print "u*SUBST(z*u, z, D2)*D1;\n";
print "u*SUBST(z*u, z, D1)*D2;\n";
print "D1*D3;\n";
print "D2*D3;\n";
print "D1*G(z);\n";

print "FACTOR(RAT(D4+D5+D7+D8+D9+D10+D11));\n";
print "FACTOR(RAT(D6+D12));\n";

print "f*u/(1-z)/(1-z*u)*log(1/(1-z));\n";
print "f/(1-z)/(1-z*u)*log(1/(1-z*u));\n";

for(\$k=0; \$k<=\$n+1; \$k++){
for(\$l=0; \$l<=\$n+1; \$l++){
if(\$k==0 && \$l==0){
print "(a0b0";
}
else{
print " + a\$k" ."b\$l*u^\$k*z^\$l";
}
}
}
print ");\n";

print "D15+D16+D17/(1-z)/(1-z*u);\n";
print "EXPAND(RAT((1-z)^2*(1-z*u)^2*DIFF(D15+D16, z)+" .
"DIFF(D17, z)*(1-z)*(1-z*u)-D17*DIFF((1-z)*(1-z*u), z)));\n";
print "EXPAND(RAT((1-z)^2*(1-z*u)^2*D13));\n";
print "RAT(SUBST((D15+D16)*(1-z)^2*(1-z*u)^2+D17*(1-z)*(1-z*u), " .
"G(z), D14));\n";

print "EXPAND(D19-D20-D21);\n";

for(\$k=0; \$k<=\$n+1; \$k++){
for(\$l=0; \$l<=\$n+1; \$l++){
print "COEFF(COEFF(D22, u, \$k), z, \$l)=0;\n";
}
}

print "LINSOLVE([D23";
for(\$k=24; \$k<23+(\$n+2)*(\$n+2); \$k++){
print ", D\$k";
}
print "],\n[f";
for(\$k=0; \$k<=\$n+1; \$k++){
for(\$l=0; \$l<=\$n+1; \$l++){
print ", a\$k" . "b\$l";
}
}
print "]);\n";

my (\$pos) = (23+(\$n+2)*(\$n+2));
print "SUBLIS(D\$pos, D18);\n";

print "[%R1=0";
for(\$k=2; \$k<=(\$n+2)*(\$n+2); \$k++){
print ", %R\$k=0";
}
print "];\n";

print "SUBLIS("
. "D" . (\$pos+2) . ", "
. "D" . (\$pos+1) . ");\n";
}
```