[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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";
}