\documentclass[a4paper,reqno,11pt]{amsart}






\marginparwidth 0pt 
\oddsidemargin -0.4 in 
\evensidemargin -0.4 in 
\marginparsep 0pt
\topmargin -0.3 in 
\textwidth 7in 
\textheight 9.8 in 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\makeatletter
\def\@theoremfont{\it}
\def\slanttheorems{\def\@theoremfont{\sl}}

\def\@begintheorem#1#2[#3]{%
\@theoremfont\trivlist \global\setbox0=\hbox{\bf
 #1}\global\setbox1=\hbox{\bf #2}\item[\hskip \labelsep{\bf #1\ #2.}]}
\let\@opargbegintheorem\relax
\makeatother
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\slanttheorems

\hfuzz=30pt

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{proposition}{Proposition}%[section]
\newtheorem{lemma}[theorem]{Lemma}%[section]
\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{}
\theorembodyfont{\slshape}
\newtheorem{ncor}[theorem]{Corollary}

\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}

\newcommand\U{{\mathcal{U}}}
\newcommand\E{{\mathcal{E}}}
\newcommand\T{{\mathcal{T}}}
\renewcommand\P{{\mathcal{P}}}
\renewcommand\a{{\bold{a}}}
\newcommand\p{{\bold{p}}}
\newcommand\mcirc{{\bigcirc}}
\newcommand\dilog{\operatorname{dilog}}
\newcommand\C{{\mathcal C}}


\newcommand\bl{\operatorname{L}}

%\newcommand{\mcirc}{\unitlength=1mm
%\special{em:linewidth 0.4pt}
%\linethickness{0.4pt}
%\begin{picture}(3.00,3.00)
%\put(1.50,1.50){\circle{2.83}}
%\end{picture}}
%

\RequirePackage{theorem}



\newtheorem{rem}{Remark}
\renewcommand{\therem}{}
\newtheorem{nrem}{Remark}

% Acknowledgements
% Entorno para escribir agradecimientos; similar al entorno abstract
% \begin{ackno} We thank Menganito Smith for ... \end{ackno}

\newcommand{\ackno}{\subsection*{\acknoname}}
\newcommand{\acknoname}{Acknowledgement}
\def\endackno{\par}


\begin{document}
\title[Analysis of grand averages for Multiple Quickselect]
{A generating functions approach for the analysis of
grand averages for Multiple Quickselect}
\author[A. Panholzer and H.~Prodinger]
{Alois Panholzer and Helmut Prodinger}
\address{  Institut f\"ur Algebra und Diskrete Mathematik\\
Technical University of Vienna\\
Wiedner Hauptstrasse 8--10\\ A-1040 Vienna, Austria.}
\email{e9125354@@fbma.tuwien.ac.at
 ({\sc Alois Panholzer})
}\vskip0pt
\email{Helmut.Prodinger@@tuwien.ac.at\vskip0pt
{\it WWW-address{\rm :\ %%@
}}\texttt{http://info.tuwien.ac.at/theoinf/proding.htm}
}



\date{\today}
\begin{abstract} 
Hoare's Find algorithm can be used to select 
$p$ specified order statistics
$j_1,\dots,j_p$ from a file of $n$ elements simultaneously.
Averaging over all $\binom{n}{p}$ subsets of $\{1,\dots,n\}$ 
defines the grand averages of 
 the  number of passes and
 comparisons.
We use a generating functions approach to compute averages and
variances of these parameters.

Additionally we sketch analogous developments for the instance
of median-of-three partition and binary (Catalan) trees.

\end{abstract} 


\maketitle

  
   \section{Introduction }





Hoare's {\sc Find} algorithm (``{\sc Quickselect}'')
\cite{Hoare61} uses the idea of {\sl Quicksort}
\cite{Hoare62, Knuth73} in order to select the $j$th element of a file of $n$ elements.
In each partitioning step, a certain element  will be brought into its
correct position $k$.
In the process, elements are moved---those brought to the left of it
are smaller, and those brought to the right are larger.
If $k=j$, the element is found; if $k<j$, one has to continue on the right
side, searching for the $(j-k)$th element; if $k>j$, one has to continue
on the left side, still searching for the $j$th element.

Two parameters are of interest: the (average) number of passes
(recursive calls) $P[n;j]$ and the (average) number of comparisons
$C[n;j]$. In Knuth's book \cite{Knuth73} we  already find the values
$$
P[n;j]=H_{j}+H_{n+1-j}-1
$$
and
$$
C[n;j]=2\Big(n+3+(n+1)H_n-(j+2)H_j-(n+3-j)H_{n+1-j}\Big)
$$
where $H_n=1+\frac12+\dots+\frac1n$ denotes the $n$th harmonic number;
compare also \cite{Knuth72}
and \cite{MaMoSm95}.




Hoare's idea can be extended as follows: Assume that we 
simultaneously search for the $p$ elements with ranks
$j_1,j_2,\dots,j_p$
where $1\le j_1<j_2<\dots<j_p\le n$ is a fixed set of $p$ values. Then,
according into which interval of the values $j_1,\dots,j_p$ the 
pivot element
falls, we may have found one of the elements and/or have to continue
on both sides, but with  smaller sets. The idea is quite simple;
a nice description of the algorithm can be found in \cite{LenMah95}.




In \cite{Prodinger95},  explicit formul{\ae} for both the
average number of passes $P[n;j_1,\dots,j_p]$ and the average number
of comparisons, $C[n;j_1,\dots,j_p]$ were given. As a corollary, the
{\sl grand} averages,
$$
\P_{n,p}=\frac{1}{\binom{n}{p}}\sum_{1\le j_1<j_2<\dots<j_p\le n}
P[n;j_1,\dots,j_p]
$$
and
$$
\C_{n,p}=\frac{1}{\binom{n}{p}}\sum_{1\le j_1<j_2<\dots<j_p\le n}
C[n;j_1,\dots,j_p]\ 
$$
were also computed (compare also 
\cite{LenMah95}). However, the approach used in this previous paper
was a mixture of guessing and proofs by induction. 

In the present paper, we use a generating functions approach to attack
the analysis of the grand averages directly. This enables us
to compute the respective variances, something that was out of reach
with the old method.

In both instances (passes resp. comparisons) we will use a trivariate
generating function $\Phi(z,u,v)$ where the coefficient of $[z^n/n!u^pv^m]$ 
is the number of permutations of $\{1,2,\dots,n\}$ and the subsets of $p$ 
elements of $\{1,2,\dots,n\}$ such that the parameter of interest has
value $m$. 

Then, for fixed $n$ and $p$ with $0\le p\le n$,
\begin{equation*}   
\frac{[z^nu^p]\Phi(z,u,v)}{\binom{n}{p} }
\end{equation*} 
is the probability generating function of interest. 
Apart from the normalization factor $\binom{n}{p}$, the functions
\begin{equation*}   
M_1(z,u)=\frac{\partial }{\partial v}\Phi(z,u,v)\Big|_{v=1}
\end{equation*} 
and
\begin{equation*}   
M_2(z,u)=\frac{\partial^2 }{\partial v^2}\Phi(z,u,v)\Big|_{v=1}
\end{equation*} 
are the generating functions of the expectations and the second factorial
moments. To be more precise, the expectation $E_{n,p}$ and the variance 
$V_{n,p}$ are given by
\begin{align}\begin{split}
E_{n,p}&=\frac{[z^nu^p]M_1(z,u)}{\binom{n}{p} }\;,\\
V_{n,p}&=\frac{[z^nu^p]M_2(z,u)}{\binom{n}{p} }+E_{n,p}-(E_{n,p})^2\;.
\end{split}
\end{align}
(Since we decided not to overload the notation by an additional superscript
$[P]$ (for passes) and $[C]$ (for comparisons), we have chosen the neutral
$E_{n,p}$ which means $\P_{n,p}$    or $\C_{n,p}$, dependening on the 
section.) 

For the following it is more suggestive to think about the binary
search tree that is naturally associated to a permutation via the
{\sc Quicksort} procedure; the pivot element corresponds to the root, 
and the left (right) subfile corresponds to the left (right) subtree.

The last sections sketch analogous computations for median-of-three
quickselect (see e.g. \cite{KiMaPr97}); for the sake of shortness we
confine ourselves to the instance of the expectations, since they are already
quite complex. However, in principle, the variances could be obtained 
explicitly.

For reasons of comparisons we included also a section about binary
(Catalan) trees. Things are a bit easier, since instead of differential
equations we have to deal with algebraic equations. Again, we only give
the expectations.

We also want to draw the reader's attention to the papers
\cite{MaMoSm95} and \cite{MaSm96} which attack quickselect resp.
multiple quickselect with probabilistic tools.
The main achievements in these papers are the establishing of
the limiting distributions.
 However, we choose
the present approach (suggested to us by Philippe Flajolet)
since we find it more promising in order to get {\sl explicit\/} results.






\section{Average number of passes}

Let $\phi_p(z,v)$ be the following generating function: The coefficient of %%@
$z^n/n!v^k$ 
is the sum over all trees of size $n$ and all labellings of exactly $p$ %%@
nodes, 
such that the smallest subtree containing the root and these $p$ nodes
(which corresponds to the number of passes!) is $k$. Then we have the %%@
recurrence
\begin{equation}\label{recursion}   
\phi'_p(z,v)=v\sum_{i=0}^{p}\phi_{i}(z,v)\phi_{p-i}(z,v)
+v\sum_{i=0}^{p-1}\phi_{i}(z,v)\phi_{p-1-i}(z,v)
\end{equation} 
for $p\ge1$ and $\phi_0(z)=\frac{1}{1-z}$. 
(The first sum refers to a nonlabelled, and
the second sum to  labelled root.)

Typically in such analyses, a first derivative appears because of the 
(uniform) splitting probability $\frac{1}{n}$ (every element can be the
root, with equal probability); the multiplication of the recursion then
introduces a factor $n$ on the left hand side, which means  (in terms
of generating functions) a derivative. This is quite classical (see for 
instance \cite{Knuth73}) and we confine ourselves with this brief statement.

Observe that
\begin{equation*}   
\frac{1}{\binom{n}{p} }[z^n]\phi_p(z,v)
\end{equation*}
are the probability generating functions  of interest.

Then the trivariate generating function from the introduction  is
given by

\begin{equation*}   
\Phi(z,u,v)=\sum_{p\ge0}\phi_p(z,v)u^p\;.
\end{equation*}
We get, by summing up the recursion (\ref{recursion}),
\begin{equation}\label{pass_eq}   
\Phi'(z,u,v)=v(1+u)\Phi^2(z,u,v)+\frac{1-v}{(1-z)^2}
\end{equation}
with $\Phi(0,u,v)=1$.

{\sc Maple} is capable to solve this differential equation:
\begin{lemma}
\begin{equation}\Phi(z,u,v)=
{\frac {\Omega+1-2v+ 
(1-z )^{\Omega}(\Omega- 1+2v )}
{ \Big(\Omega+1-2v(1+u)+ 
(1-z )^{\Omega}(\Omega- 1+
2v(1+u) ) \Big) (1-z )}}
\end{equation}
with
\begin{equation*}
\Omega=\sqrt{1-4v (1+u ) (1-v )}\;.\qed
\end{equation*}

\end{lemma}



Consequently we get


\begin{equation}   
M_1(z,u)=
\frac{1+2u}{1-z(1+u)}-\frac{2u}{\left(1-z(1+u)\right)^2}-\frac{1}{1-z}
+\frac{2u(1+u)}{\left(1-z(1+u)\right)^2}\log\frac{1}{1-z}\;.
\end{equation}
We have
\begin{equation*}   
[z^n]\left(\frac{1+2u}{1-z(1+u)}-\frac{2u}{\left(1-z(1+u)\right)^2}-%%@
\frac{1}{1-z}\right)
=(1+2u)(1+u)^n-2(n+1)u(1+u)^n-1\;.
\end{equation*} 
Let us assume that $p\ge1$. 
Reading off the coefficient of $u^p$ in the last formula, we obtain
\begin{equation*}   
\binom{n}{p}-2n\binom{n}{p-1}\;.  
\end{equation*}
Now we turn to the logarithmic term. The factor of 
$\log\frac{1}{1-z}$ 
is
\begin{equation*}   
\frac{2u(1+u)}{\left(1-z(1+u)\right)^2}=
\frac{2u(1+u)}{(1-z)^2}\frac{1}{\big(1-\frac{uz}{1-z}\big)^2}\;,
\end{equation*}
and the coefficient of $u^p$ therein is
\begin{equation*}   
\frac{2pz^{p-1}}{(1-z)^{p+1}}+\frac{2(p-1)z^{p-2}}{(1-z)^{p}}\;.
\end{equation*}
We observe the general formula (see e.g \cite{GrKn82})
\begin{equation} \label{gen_form1}  
[z^n]\frac{1}{(1-z)^{m+1}}\log\frac{1}{1-z}=\binom{n+m}{n}\left(H_{n+m}-%%@
H_m\right) 
\end{equation}
and find so, searching for the coefficient of $z^n$,
\begin{equation*}   
2p\binom{n+1}{p} \left(H_{n+1}-H_{p}\right) +
2(p-1)\binom{n+1}{p-1} \left(H_{n+1}-H_{p-1}\right) \;.
\end{equation*}


We collect both contributions, divide by $\binom{n}{p} $ and get

\begin{theorem} For $p\ge1$ the average number $E_{n,p} $
 of passes to search
for $p$ random elements is given by

\begin{equation}   
E_{n,p}=\left(H_{n+1}-H_{p}\right)\frac{2p(n+1)^2}{(n+2-p)(n+1-p)}-
\frac {n(2p-1)+p}{n+2-p}\;.
\end{equation}
For $ p\ge0$ we have
$E_{n,0}=0$.\qed
\end{theorem}

This result  appeared already in \cite{Prodinger95}.

It is interesting to state the special cases $p=1$ (Hoare's {\sc Find}
algorithm or {\sc Quickselect}) 
and $p=n$ ({\sc Quicksort}) explicitly. 


\begin{ncor}
\begin{align*}
E_{n,1}&=2\left(1+\frac{1}{n}\right)H_n-3\,,\\
E_{n,n}&=n\,.
\end{align*}

\end{ncor}
By standard methods we obtain also the following asymptotic equivalents.

\begin{ncor}
    
     \begin{align}\begin{split}
        E_{n,p} & = 2p \log n + 2 \gamma p -2p - 2p H_{p} +1 + {\mathcal O}\left(
        \frac{\log n}{n}\right) \quad \mbox{{\rm for} $p$ {\rm fixed}} \, ,
         \\
        E_{n,p} & = n - \frac{1}{3}l + {\mathcal O}\left(\frac{\log n}{n}\right)
        \quad \mbox{{\rm for} $l=n-p$ {\rm fixed}} \, , \\
        E_{n,p} & = - \frac{2\rho(1-\rho+\log \rho)}{(1-\rho)^{2}}n + \frac{
         \rho(4 \rho \log \rho + 2 \log \rho -\rho^{2}-4\rho+5)}{(1-\rho
         )^{3}} + {\mathcal O}\left(\frac{\log n}{n}\right) \\
        & \quad \mbox{{\rm for} $p = \rho n$ {\rm and} $0 < \rho < 1$}. 
	\end{split}
     \end{align}   
  \end{ncor}  






\section{Variance of the  number of passes}

From the function $ \Phi(z,u,v)$ we find
\begin{align}
\begin{split}
M_2(z,u)=&-2{\frac {1+4u+2{u}^{2}}{1-z(1+u)}}
-2{\frac {u (-3+2u )}{ \left(1-z(1+u)\right)^{2}}}
+8{\frac {{u}^{2}}{ \left(1-z(1+u)\right)^{3}}}+2{\frac {1+u}{1-z}}\\
&-\left(\frac{16u^2(1+u)}{\left(1-z(1+u)\right)^{3}}+
\frac{4u(1-u)(1+u)}{\left(1-z(1+u)\right)^{2}}
\right)\log\frac{1}{1-z}\\
&+\left(\frac{8u^2(1+u)^2}{\left(1-z(1+u)\right)^{3}}+
\frac{4u(1+u)^2}{\left(1-z(1+u)\right)^{2}}
\right)\log^2\frac{1}{1-z}\;.
\end{split}
\end{align}
Now we assume that $ p\ge2$
 and read off the coefficient of $z^nu^p$ in the non--logarithmic term, and %%@
divide
by $\binom{n}{p}$,
which gives
\begin{equation*}   
2\frac{(p+1)(2p-1)n^2+(p^2+3p-3)n+p-2}{(n+2-p)(n+1-p)}\;.
\end{equation*}
Furthermore, we consider the term with $\log\frac{1}{1-z}$. The coefficient of $u^p$ 
in the factor of  $\log\frac{1}{1-z}$ is
\begin{equation*}   
-8p(p-1)\frac{z^{p-2}}{(1-z)^{p+1}}
-8(p-1)(p-2)\frac{z^{p-3}}{(1-z)^{p}}
-4p\frac{z^{p-1}}{(1-z)^{p+1}}
+4(p-2)\frac{z^{p-3}}{(1-z)^{p-1}}\;.
\end{equation*}
We are searching for the coefficient of $z^n $ in this times 
$\log\frac{1}{1-z}$,  use the general formula (\ref{gen_form1})
and obtain
\begin{equation*}   
\frac{{-4p(n+1)^2\big((2p-1)n+2p\big)(H_{n+1}-H_p)
-16(p-1)^2n^2-4(8p^2-17p+10)n-
4(4p^2-9p+6)}
}{(n+3-p)(n+2-p)(n+1-p)}\;.
\end{equation*}
For the term with the square of $\log\frac{1}{1-z}$
we get in a similar fashion
\begin{equation*}   
\frac{X}{(n+4-p)(n+3-p)(n+2-p)(n+1-p)}
\end{equation*}
with
\begin{align*}
X&=4p(n+2)(n+1)^2(pn+p+2)\Big(H^2_{n+1}-H^{(2)}_{n+1}+H^2_p+H^{(2)}_p\Big)\\
&-8(n+1)^2H_{n+1}\big({n^2p^2H_p+n(p(3p+2)H_p-(3p-2)(p-1))+2p(p+2)H_p-5p^2+8p-
4}\big)\\
&-8(n+1)^2H_p\Big((3p-2)(p-1)n+5p^2-8p+4\Big)\\
&+8(n+1)(p-2)\Big(n(3p-4)+4p-7\Big)\;.
\end{align*}
For that we have used the general formula
\begin{equation}\label{gen_form2}
[z^n]\frac{1}{(1-z)^{m+1}}\log^2\frac{1}{1-z}=\binom{n+m}{m}
\left((H_{n+m}-H_m)^2-(H^{(2)}_{n+m}-H^{(2)}_m)\right) \;.
\end{equation}

Dividing this by $\binom{n}{p}$ leads to the following theorem; for $p=1$
a similar but simpler computation, based on the formula
\begin{equation*}   
[u]M_2(z,u)=\frac{4z}{(1-z)^2}-
\frac{4}{(1-z)^2}\log\frac{1}{1-z}
+\frac{4}{(1-z)^2}\log^2\frac{1}{1-z}
\end{equation*} 
was used.

\begin{theorem} The variance of the number of passes when searching for a random
set of
$p\ge2$ elements with Hoare's {\sc Find} algorithm is given by

\begin{align}\begin{split}
V_{n,p}&=-\frac{4p(n+1)^2\Psi_1}{(n+4-p)(n+3-p)(n+2-p)^2(n+1-p)^2}\Big(H_{n+1}
	-H_p\Big)^2\\
&+\frac{2(n+1)^2\Psi_2}{(n+4-p)(n+3-p)(n+2-p)^2(n+1-p)}\Big(H_{n+1}
	-H_p\Big)\\
&-\frac{4p(n+2)(n+1)^2(pn+p+2)}{(n+4-p)(n+3-p)(n+2-p)(n+1-p)}
\Big(H^{(2)}_{n+1}	-H^{(2)}_p\Big)\\
&+\frac{2(n+1)^2\Psi_3}{(n+4-p)(n+3-p)(n+2-p)^2}
\end{split}\end{align}
with
\begin{align}\begin{split}
\Psi_1&=(3p-2)n^3-2(p^2-9p+5)n^2-(p^3+5p^2-33p+16)n-p^3-5p^2+20p-8\;,\\
\Psi_2&=pn^3+(11p^2-13p+8)n^2-(9p^3-54p^2+62p-32)n-3p^4-p^3+38p^2-56p+32\;,\\
\Psi_3&=(2p-1)n^2-2(5p^2-15p+8)n+8p^3-45p^2+72p-32\;.
\end{split}
\end{align}
For $p=1$, the formula reads 
\begin{equation}
V_{n,1}=-4\frac{n+1}{n^2}H^2_{n+1}+\frac{2(n+4)(n+1)}{n^2}H_{n+1}
-4\frac{n+1}{n}H^{(2)}_{n+1}+\frac{2(2n^2-n-2)}{n^2}\;;
\end{equation}
for $p=0$ we have $V_{n,0}=0$.  \qed
\end{theorem}

Observe that for $p=n$ ({\sc Quicksort}) this formula simplifies to $V_{n,n}=0$, as it
should. 

\begin{ncor}
     
     \begin{align}\begin{split}
        V_{n,p} & = 2p\log n + 4p^{2}H_{p}^{(2)} - 2pH_{p} + 2p\gamma -
        \frac{2}{3}p^{2}\pi^{2} + {\mathcal O}\left( \frac{\log n}{n}\right)
        \quad \mbox{{\rm for} $p$ {\rm fixed}} \, ,  \\
        V_{n,p} & = \frac{2}{9}l + {\mathcal O}\left(\frac{1}{n}\right)
        \quad \mbox{{\rm for} $l=n-p$ {\rm fixed}} \, ,  \\
        V_{n,p} & = \left(- \frac{4\rho^{2}(\rho+3)\log^{2} \rho}{(1-\rho
         )^{5}} - \frac{2\rho(3\rho^{2}+12\rho+1)\log \rho}{(1-\rho)^{4}} -
         \frac{16\rho^{2}}{(1-\rho)^{3}}\right) n + {\mathcal O}\left(1\right)
          \\
        & \quad \mbox{{\rm for} $p = \rho n$ {\rm and} $0 < \rho < 1$}. 
	\end{split}     \end{align}   
  \end{ncor}  
  














  
\section{Comparisons}

If we have a tree with $n$ nodes, there are costs of $n-1$ comparisons, 
and then the additional costs, resulting from the subtrees.
Typically, this leads, apart from other things, to a substitution
$z\mapsto zv$. Otherwise, we distinguish again whether or not the root
is one of elements being sought.  

The fundamental differential equation is thus
\begin{equation*}
\Phi'(z,u,v)=(1+u)\Phi^2(zv,u,v)+\frac{1}{(1-z)^2}
-\frac{1}{(1-zv)^2}\;, 
\end{equation*}
with $\Phi(0,u,v)=1$. 
Now, we cannot solve that, but we can differentiate
it with respect to $v$ (followed by $v:=1$) and solve the resulting
differential equation for $M_1(z,u)$.
(In the next section we will differentiate it twice, plug in the already
known   $M_1(z,u)$ and solve the equation for $M_2(z,u)$.)

\begin{align}\begin{split}
M_1(z,u)&=-\frac{2(1+u)(1+3u)}{(1-z(1+u))^2}\log\frac{1}{1-z}+
\frac{2}{(1-z(1+u))^2}\log\frac{1}{1-z(1+u)}\\
&+\frac{2(1+2u)}{u(1-z)}-\frac{1}{(1-z)^2}
-\frac{2(1+3u+3u^2)}{u(1-z(1+u))}+\frac{3(1+2u)}{(1-z(1+u))^2}\;.
\end{split}
\end{align}
From this, we read off the coefficients much in the same style as before,
divide  by $ \binom{n}{p}$ and obtain the expectations (known already
from \cite{Prodinger95}).
\begin{theorem} For $p\ge1$ the average number $E_{n,p} $
 of comparisons to search
for $p$ random elements is given by

\begin{align}\begin{split}
E_{n,p}
%&
=-\frac{2p(n+1)(4n-p+5)}{(n+2-p)(n+1-p)}H_{n+1}
+\frac{2(n+1)^2(n+2p+2)}{(n+2-p)(n+1-p)}H_{p}
%&\\
+\frac{n^2+(5p-1)n+3p}{n+2-p}\;. 
\end{split}
\end{align}
For $p=0$, we have $E_{n,0}=0$. \qed  
\end{theorem}

Again, we note the special cases $p=1$ and $p=n$.
\begin{ncor}
 \begin{align}\begin{split}
E_{n,1}&=3n-8\left(1+\frac{1}{n}\right)H_n+13\,,
\\ E_{n,n}&=2(n+1)H_n-4n\,.
\end{split}\end{align}
\end{ncor}




\begin{ncor}
    
     \begin{align}\begin{split}
        E_{n,p} & = (2H_{p}+1) n - 8p \log n + 2(4p+1)H_{p} + 3(2p-1) -8p
        \gamma + {\mathcal O}\left(\frac{\log n}{n}\right) \quad \mbox{{\rm for}
           $p$ {\rm fixed}} \, , \\
        E_{n,p} & = 2n \log n + 2(\gamma +2) n + 2 \log n +1 +2\gamma + {\mathcal
         O}\left(\frac{\log n}{n}\right) \quad \mbox{{\rm for} $l=n-p$ {\rm
          fixed}} \, , \\
        E_{n,p} & = 2n \log n + \frac{(4\rho +2)\log \rho +(2\rho^{2}-4\rho+2
         )\gamma -5\rho^{2}+4\rho+1}{(1-\rho)^{2}} n + 2 \log n + {\mathcal O}(1)
        \\
        & \quad \mbox{{\rm for} $p = \rho n$ {\rm and} $0 < \rho < 1$}. \end{split}
     \end{align}   
  \end{ncor}  


\section{Variance of the  number of comparisons}

As indicated in the last section, we can set up a differential equation for
$M_2(z,u)$, viz. 

\begin{align}\begin{split}
M'_2&(z,u)=
2{\frac { (1+u )}{1-z(1+u)}}M_2(z,u)
+8{\frac { (3u+1 )^{2} (1+u )^{3} }{ (1-z(1+u) )^{4}}}\log^2 \frac{1}{1-z}
\\&+8{\frac { (1+u ) }{ (1-z(1+u) )^{4}}}\log^2 \frac1{1-z(1+u)} 
-16{\frac { (3u+1 ) (1+u )^{2}}{ (1-z(1+u) )^{4}}}\log \frac{1}{1-%%@
z}\log\frac1{1-z(1+u)}\\
&-8{\frac { {(3u+1 ) (1+u )^{2} (2{z}^{2}{u}^{2}-9z{u}^{2}+6{u}^{2}
+5{z}^{2}u+9u-14z
u+3-6z+3{z}^{2} )z}}{ (1-z(1+u) )^{4} 
(1-z )^{2}}}\log \frac{1}{1-z}\\
&+8{\frac { (1+u ) (2{z}^{2}{u}^{2}-9z{u}^{2}+6{u}^{2}+5{z}^{2}u+9u-14zu+3-%%@
6z+3{z}^{2}
 )z}{ (1-z(1+u) )^{4} (1-z )^{2}
}}\log \frac{1}{1-z(1+u)}\\
&+\frac{2z^{2}u\,\Psi}
{ (1-z )^{4} (1-z(1+u) )^{4}}
\end{split}
\end{align}	
with

{\scriptsize
$  
\Psi=  53-164z+165u-316z^{3}u^{2}-242
z^{3}u+223u^{2}+144u^{3}-68z^{3}+5z^{4}-438zu^
{3}+174z^{2}+592z^{2}u+766z^{2}u^{2}-700zu^{2}
+19{z}^{4}u+27z^{4}u^{2}+17z^{4}u^{3}-534zu+105u^{4}z^
{2}+36u^{4}+4z^{4}u^{4}-36z^{3}u^{4}+453z^{2}u^{3}-178z^{3}u^{3}-108u^{4}z 
$\par}
\noindent
and $M_2(0,u)=0$.

Now this time {\sc Maple} does not do it automatically, since it cannot handle
\begin{equation*}   
\int_0^z\frac{\log^2(1-t)}{(1-t(1+u))^2}dt\;.
\end{equation*}
However, by integration by parts this integral can be evaluated, and consequently
we get the following solution.
\begin{lemma}
\begin{align}\begin{split}
M_2(z,u)&=24{\frac { (1+u )^{3}}{ (1-z(1+u) )^{2}}}
\int_0^z
\frac{1}{1-t(1+u)}\log\frac{1}{1-t}\,dt\\
&+8{\frac { (3u+1 ) (1+u )^{2} (-zu+3u+2-z ) }{ (1-z(1+u) )^{3}}}
\log^2\frac1 {1-z} \\
&+4{\frac { 1+z+zu }{ (1-z(1+u) )^{3}}}
\log^2\frac1 {1-z(1+u)}\\
&-16{\frac { (1+u ) (-zu+3u+2-z )}{ (1-z(1+u) )^{3}}}
\log\frac1 {1-z}  \log\frac1 {1-z(1+u)}\\
&+4{\frac {(1+u )\,\Psi_1 
}{u (1-z ) (1-z(1+u) )^{3}}}\log\frac{1}{1-z} \\
&-8{\frac { {8{z}^{2}{u}^{3}+9{z}^{2}u+{z}^{2}+16{z}^{2}{u}^{2}-20{u}^{2}z-9
{u}^{3}z-2z-14zu+5u+3{u}^{2}+1 }}{u (1-z ) (1-z(1+u) )^{3}}}\log\frac{1}{1-z(1+u)}\\
&+\frac{2}{3}{\frac {z\,\Psi_2}
{ (1-z )^{3} (1-z(1+u) )^{3}}}
\end{split}
\end{align}
with\newline
{\scriptsize$\Psi_1=
 10{u}^{4}{z}^{2}-16{u}^{4}z+31{z}^{2}{u}^{3}-19{u}^{3}z-20{u}^{3}-
7{u}^{2}+35{z}^{2}{u}^{2}-30
{u}^{2}z+8u-24zu+16{z}^{2}u+2{z}^{2}-4z+2 
$\par}


\noindent and

\noindent
{\scriptsize
$\Psi_2=
12-330{u}^{3}z+39{z}^{4}{u}^{3}-12{u}^{4}z+346{z}^{2}{u}^{3}-173{u}^{3}
{z}^{3}+42{z}^{4}{u}^{2}+15{z}^{4}u-519{u}^{2}z
+478{z}^{2}{u}^{2}-199{u}^{2}{z}^{3}
-36z-237zu+36{z}^{2}+90u+219{z}^{2}u-87u{z}^{3}
-12{z}^{3}+12{z}^{4}{u}^{4}-
49{u}^{4}{z}^{3}+48{u}^{4}{z}^{2}+198{u}^{2}+120{u}^{3} 
$. \qed\par}
 
\end{lemma}

We observe that 




\begin{multline*}   
(1+u)\int_0^z\frac{1}{1-t(1+u)}\log\frac{1}{1-t}\,dt=\\
=\log (1-z(1+u))\log (u)
+{\dilog}\Big({\frac {1+u}{u}}\Big) 
 -{\dilog}\Big({\frac {1-z+u-zu}{u}}\Big) 
-\log (1+u)\log (1-z(1+u))\;,
\end{multline*}										
which is more ``closed form'' but less useful, since
for the coefficients the integrand is as good as the integral
itself, since we can simply look for $1/n$ times the coefficient
of $z^{n-1}u^p$. 

We remark that Maple's dilog function is related to the more common
polylog function 
\begin{equation*}   
\bl_2(z)=\sum_{n\ge1}\frac{z^n}{n^2}
\end{equation*}
via $\dilog(1-z)=\bl_2(z)$ (compare \cite{Lewin91}).



The relevant formula for $p\ge1$ is this


	

\begin{equation*}   
\frac{1}{n}[z^{n-1}u^p]\frac{1}{1-z(1+u)}\log\frac{1}{1-z}=
\frac{1}{n}\binom{n-1}{p-1}\Big(H_{n-1}-H_{p-1}\Big)\;.
\end{equation*}

For $p=0$ it is slightly different; 
\begin{equation*}   
\frac{1}{n}[z^{n-1}u^0]\frac{1}{1-z(1+u)}\log\frac{1}{1-z}=
\frac{H_{n-1}}{n}\;.
\end{equation*}

On the other hand,
\begin{equation*}   
[z^{n}u^p]\frac{(1+u)^3}{(1-z(1+u))^2}=(n+1)\binom{n+3}{p} \;.
\end{equation*}

The convolution of these two quantities can be performed by
(the by now) standard tools.

There is only one sum, 
     \begin{equation}
      \lambda_{n,p} = \frac{1}{\binom{n}{p}} \sum_{k=1}^{n} \frac{1}{k^{2}}
      \binom{n-k}{p} = \frac{1}{\binom{n}{p}}
[z^{n}] \frac{z^{p}}{(1-z)^{p+1}} \bl_{2} (z) \, ,
   \end{equation}
that has a ``new'' shape; we will relate it to more common quantities
a bit later.



Observe that an analogous quantity has a well known evaluation:
     \begin{equation}
      \frac{1}{\binom{n}{p}} \sum_{k=1}^{n} \frac{1}{k}
      \binom{n-k}{p} = \frac{1}{\binom{n}{p}}
[z^{n}] \frac{z^{p}}{(1-z)^{p+1}}\log \frac{1}{1-z}=H_n-H_p\;.
   \end{equation}

After a lengthy routine calculation we arrive at the following theorem.

\begin{theorem} For $p\ge2$ the variance $V_{n,p} $
 of the number of comparisons to search
for $p$ random elements is given by



			


\begin{align}\begin{split}
         V_{n,p} & = -\frac{24(n+1)^{2}(n+2)}{(n+1-p)(n+2-p)} \lambda_{n+2,p}
         + \frac{4(n+1)^{2}p \, \Psi_{1}}
{(n+2-p)^{\underline{2}}\,(n+4-p)^{ \underline{4}}}
 \Big(H_{n+1}-H_p\Big)^{2}
  \\
	&+\frac{2(n+1)\Psi_2}{(n+4-p)^{ \underline{4}}\, (n+2-p)} 
        \Big(H_{n+1}-H_p\Big)
+\frac{4(n+1)^2\Psi_3}{(n +4-p)^{ \underline{4}}}
\Big(H^{(2)}_{n+1}-H^{(2)}_p\Big)\\
&-2(n+1)H_p-4(n+1)^2H^{(2)}_p
+\frac{(n+1)\Psi_4}
{3(p+1)^{2}(p+2)(n+2-p)\,(n+4-p)^{ \underline{4}}}
\end{split}
\end{align}
with



\begin{align}\begin{split}
\Psi_1=&-4{n}^{4}+ (-27p-13 ){n}^{3}+ (30{p}^{2}-183p+
13 ){n}^{2}\\
&+ ({p}^{3}+108{p}^{2}-379p+70 )n-2{p
}^{3}+108{p}^{2}-250p+48\,,
\\
\Psi_2=& (54p-28 ){n}^{4}+ (25{p}^{2}+317p-172 ){n
}^{3}+ (-67{p}^{3}+198{p}^{2}+655p-368 ){n}^{2}\\
&+ (-13{p}^{4}-107{p}^{3}+252{p}^{2}+618p-320 )n+{p}^
{5}-20{p}^{4}-23{p}^{3}+62{p}^{2}+232p-96\,,
\\
\Psi_3=&6{n}^{3}+ (-16{p}^{2}-8p+54 ){n}^{2}\\
&+ (8{p}^{3
}-63{p}^{2}-65p+156 )n- (p-1 ) ({p}^{3}-13
{p}^{2}+36p+144 )\,,
\\
\Psi_4=&
 (21{p}^{3}+80{p}^{2}+81p-2 ){n}^{6}+ (-105{p}
^{4}-76{p}^{3}+815{p}^{2}+1258p+40 ){n}^{5}\\
&+ (210{p
}^{5}-562{p}^{4}-2173{p}^{3}+2718{p}^{2}+8125p+886 ){n}^
{4}\\
&+ (-210{p}^{6}+1036{p}^{5}-223{p}^{4}-9232{p}^{3}+2283
{p}^{2}+25662p+4096 ){n}^{3}\\
&+ (105{p}^{7}-500{p}^{6
}+2062{p}^{5}+1352{p}^{4}-18253{p}^{3}-4600{p}^{2}+43086p+
7972 ){n}^{2}\\
&+ (-21{p}^{8}+40{p}^{7}-512{p}^{6}+3390
{p}^{5}+3029{p}^{4}-19638{p}^{3}-11176{p}^{2}+37736p+7600
 )n\\
&-18{p}^{8}-50
{p}^{7}-348{p}^{6}+2232{p}^{5}+2298{p}^{4}-8886{p}^{3}-6540
{p}^{2}+13616p+2880 \,.
\end{split}
\end{align}
For $p=1$ we get
 
\begin{equation}
 V_{n,1}  = - \frac{16(n+1)(n+4)}{n^{2}} H_{n}^{2} + \frac{12(9n+17
          )}{n} H_{n} - \frac{48(n+1)}{n} H_{n}^{(2)} + n^{2} -10n-47 \,;
\end{equation}
and for $p=0$ we have $V_{n,0}=0$.  \qed
\end{theorem}
Observe that for $p=n$ the formula simplifies to
\begin{equation}   
V_{n,n}=-2(n+1) H_{n} -4(n+1)^{2}H_{n}^{(2)} + (7n+13)n \, .
\end{equation}


We can rewrite the quantity $\lambda_{n,p}$ as follows:
\begin{proposition}
\begin{equation}
\lambda_{n,p}=-\frac{1}{2}\Big[H_n^2-H_n^{(2)}
-H_{n-p}^{2}-H_{n-p}^{(2)}
\Big]
+\sum_{j=1}^{p-1}\frac{H_j}{j+n+1-p}\;.
\end{equation}
\end{proposition}

{\sc Proof.}
We write
\begin{equation*}   
\binom{n-k}{p}=\frac{n-k}{p}\binom{n-1-k}{p-1}
\end{equation*}
and get consequently the recursion
\begin{equation*}   
\lambda_{n,p}=\lambda_{n-1,p-1}-\frac{1}{n}\Big(H_{n-1}-H_{p-1}\Big)\;.
\end{equation*}
Unwinding this we get
\begin{equation*}   
\lambda_{n,p}=H_{n-p}^{(2)}-\sum_{k=n-p-1}^n\frac{1}{k}\Big(H_{k-1}-H_{k-1-n+p}\Big)\;.
\end{equation*}
Since
\begin{equation*}   
\sum_{k=1}^n\frac{H_{k-1}}{k}=\frac{1}{2}\Big(H_{n}^2-H_{n}^{(2)}\Big)\,,
\end{equation*}
the result readily follows.   \qed

In order to handle  the sum
$\sum_{j=1}^{p-1} \frac{H_{j}}{n-p+1+j}$ asymptotically for
either  $p$ or $l=n-p$ fixed or for
a fixed ratio $ \rho =
  \frac{p}{n}$ with $0 < \rho < 1$ as $n \to \infty$ we state a few relations
that are easy to prove (but not so easy to find) by generating functions
and/or can be found in \cite{HoarVar}.

\begin{proposition}

  \begin{subequations}
  \begin{align}
     \sum_{j=1}^{p-1} \frac{H_{j}}{n-p+1+j} & = H_{n} H_{p} - \sum_{j=1}^{p}
      \frac{H_{n-p+j}}{j} \, , \label{glg10a}\\
     \sum_{j=1}^{p-1} \frac{H_{j}}{n-p+1+j} & = \sum_{j=1}^{p}
     \frac{H_{n-j}}{j} - \frac{1}{n+1-p} (H_{n}-H_{p}-H_{n+1-p}) - H_{p}H_{n
      +1-p} + H_{n} H_{n+1-p} \notag \\
     & \quad {} - \frac{1}{2} (H_{n}^{2}-H_{n}^{(2)}) -
     \frac{1}{2} (H_{n+1-p}^{2}+H_{n+1-p}^{(2)}) \, , \label{glg10b} \\
	\begin{split}
     \sum_{j=1}^{p-1} \frac{H_{j}}{n-p+1+j} & = - \sum_{j=p+1}^{n}
     \frac{H_{j-p}}{j} -\frac{1}{2} (H_{p-1}^{2}+H_{p-1}^{(2)})+H_{n}H_{p-1}+
     \frac{H_{n-p}}{p}  \\
     & \quad {} - \frac{1}{n+1-p} (H_{n}-H_{p}-H_{n+1-p}) - H_{p}H_{n
      +1-p} + H_{n} H_{n+1-p}  \\
     & \quad {} - \frac{1}{2} (H_{n+1-p}^{2}+H_{n+1-p}^{(2)})
     \, , \label{glg10c}\qed
	\end{split}
	  \end{align}      
  \end{subequations}
 
\end{proposition} 
For fixed $p$ we can use the definition and find
  \begin{equation}
     \sum_{j=1}^{p-1} \frac{H_{j}}{n-p+1+j} 
 = \frac{p(H_{p}-1)}{n} + {\mathcal O}\left(\frac{1}{n^{2}}\right) \enspace
     \text{for} \; n \to \infty \, .
  \end{equation}
    For fixed $l=n-p$ we compute
  \begin{align}
     \sum_{j=p+1}^{n} \frac{H_{j-p}}{j} & = \sum_{j=1}^{l} \frac{H_{j}}{n
      +j-l} = \sum_{j=1}^{l} \frac{H_{j}}{n}\left(1+{\mathcal O}\Big(\frac{1}{n}
     \Big)\right) = \frac{(l+1)H_{l}-l}{n} + {\mathcal O}\left(\frac{1}{n^{2}}
     \right) \, ,
  \end{align}
  and use \eqref{glg10c} to find
  \begin{align}\begin{split}
     \sum_{j=1}^{p-1} \frac{H_{j}}{n-p+1+j} & = \frac{1}{2} \log^{2} n +
     \gamma \log n - \frac{\pi^{2}}{12} + \frac{H_{l+1}}{l+1} - \frac{1}{2}
     H_{l +1}^{2} + \frac{\gamma^{2}}{2} - \frac{1}{2} H_{l+1}^{(2)} +
      \frac{\log n}{2n} +  \frac{\gamma}{2n} \\
     & \quad {}  - \frac{l H_{l}}{n} - \frac{l}{(l+1)n} + 
     \frac{1}{2n} + \frac{l H_{l +1}}{n} + \frac{l}{n} + {\mathcal O}\left(\frac{
      \log n}{n^{2}}\right)  \enspace \text{for} \; n \to \infty \, .
	\end{split}
  \end{align}
  
  For a fixed ratio $\rho =
  \frac{p}{n}$ with $0 < \rho < n$ we use the expansion
  \begin{equation}
     \sum_{j=1}^{p} \frac{H_{n-j}}{j} = \log^{2} n + (2\gamma +\log \rho)
     \log n + \gamma^{2} + \gamma \log \rho - {\rm L}_2(\rho) + o(1)
  \end{equation}
from \cite{HoarVar}.
  With this and equation \eqref{glg10b} we get 
  \begin{align}\begin{split}
     \sum_{j=1}^{p-1} \frac{H_{j}}{n-p+1+j} & = - \log(1-\rho) \log n -
     \frac{1}{2} \log^{2}(1-\rho) - \gamma \log(1-\rho) - \log \rho \log (1-
     \rho)  \\
     & \quad {} - {\rm L}_2(\rho) + o(1) \enspace \text{for} \; n \to
     \infty \, .
	\end{split}
  \end{align}   
 Combining these formul{\ae} with the standard expansions for harmonic
numbers we get the following lemma.















  \begin{lemma}
     The quantity $\lambda_{n,p}$ has the following asymptotic equivalents:
     \begin{align}\begin{split}
        \lambda_{n,p} & = \frac{\pi^{2}}{6} + {\mathcal O}\left(\frac{\log n}{n}
        \right) \quad \mbox{{\rm for} $p$ {\rm fixed}} \, ,  \\
        \lambda_{n,p} & = \frac{l}{n} + {\mathcal O}\left(\frac{1}{n^{2}}\right)
        \quad \mbox{{\rm for} $l=n-p$ {\rm fix}} \, ,  \\
        \lambda_{n,p} & = \bl_{2}(1-\rho) + o(1) \quad \mbox{{\rm for} $p =
         \rho n$ {\rm and} $0 < \rho < 1$}. \end{split}
     \end{align}   
  \end{lemma}  
  
With this we get the following corollary.
  \begin{ncor}
     The variance $V_{n,p}$ of the number of comparisons
is asymptotically given by
     \begin{align}\begin{split}
        V_{n,p} & = \left(\frac{21p^{3}+80p^{2}+81p-2}{3(p+1)^{2}(p
         +2)} - 4H_{p}^{(2)}\right) n^{2} + {\mathcal O}(n) \quad \mbox{{\rm for}
           $p$ {\rm fixed}} \, , \\
        V_{n,p} & = \left( \frac{7l^{4}+70l^{3}+245l^{2}+368l+168}{(l+4)^{
          \underline{4}}} - \frac{2}{3}\pi^{2} \right) n^{2} + {\mathcal O}(n
        \log n) \quad \mbox{{\rm for} $l=n-p$ {\rm fixed}} \, ,  \\
        V_{n,p} & = \left( 7 - \frac{2}{3}\pi^{2} \right) n^{2} + {\mathcal O}(n
        \log n) \quad \mbox{{\rm for} $p = \rho n$ {\rm and} $0 < \rho < 1
         $}. \end{split}
     \end{align}   
  \end{ncor}  

{\bf Remark.} The instance `$p$ fixed'  of the above corollary appears in
\cite{MaSm96}.  





\section{Median of three partition -- passes}

As it says, one takes a random sample of 3 elements and uses the median as
the pivot element. See \cite{Knuth73, GrKn82} for that in the context of
{\sc Quicksort} and \cite{KiMaPr97, MarPro96} in the context of {\sc Quickselect}.

The only thing that changes are the {\sl splitting probabilities.}
Instead of $\frac{1}{n}$ they are in this instance
\begin{equation*}   
\frac{(k-1)(n-k)}{\binom{n}{3}}\,.
\end{equation*}
Now ${\binom{n}{3}}$ moves as a factor to the left hand side and produces
$\frac{1}{6}$ times a third derivative. In this way we find the following
differential equation of interest:



   \begin{align}\begin{split}
      & \frac{1}{6} \frac{\partial^{3}}{\partial z^{3}} \Phi(z,u,v) = v (1+u)
      \left( \frac{\partial}{\partial z} \Phi(z,u,v)\right)^{2} + \frac{1-v}{
       (1-z)^{4}} \, ,  \\
      & \Phi(0,u,v) = 1 \, , \enspace \left. \frac{\partial}{\partial z} \Phi
      (z,u,v)\right|_{z=0} = 1+uv \, , \enspace \left. \frac{\partial^{2}}{
       \partial z^{2}} \Phi(z,u,v)\right|_{z=0} = 2(1+2uv+u^{2}v) \, .
	\end{split}
   \end{align}   
   It is natural to consider the function

   \begin{equation*}
      \Psi(z,u,v) = \frac{\partial}{\partial z} \Phi(z,u,v) \, .
   \end{equation*}   
 For the evaluation of the expectated values we define  

   \begin{equation*}
      G(z,u) = \left. \frac{\partial}{\partial v} \Psi(z,u,v) \right|_{v=1}
      \, ;
   \end{equation*}
   to get it, we have to solve the following differential equation
   \begin{align}\begin{split}
      & \frac{1}{6} \frac{\partial^{2}}{\partial z^{2}} G(z,u) = \frac{2(1+u
       )^{2}}{(1-z(1+u))^{2}} G(z,u) + \frac{(1+u)^{3}}{(1-z(1+u))^{4}} -
      \frac{1}{(1-z)^{4}} \, ,  \\
      & G(0,u) = u \, , \enspace \left. \frac{\partial}{\partial z} G(z,u)
      \right|_{z=0} = 4u + 2u^{2} \, .
	\end{split}
   \end{align}
  Therefore we obtain

   \begin{align}\begin{split}
     G(z,u) & = \frac{12}{7} \frac{({u}+1)^{2} \, p_{1}(z,u)}{(1-z(1+{u})
      )^{3}\,{u}^{6}} \log\frac{1}{1-{z}} \\
     &  + \frac{60}{7} 
     \frac{({u}+1)^{2}\,(1-z(1+u))^{4}}{{u}^{6}} \log
	\frac{1}{1-z(1+{u})} - \frac{1}{7} \frac{p_{2}(z,u)}{(1-z(1+u))^{3}\,(1-z)^{2}
      \,{u}^{5}} \, ,
	\end{split}
   \end{align}
   with
   
{\scriptsize
$     p_{1}(z,u)  = 5{z}^{7}{u}^{7} + 35{z}^{7}{u}^{6} + 105{z}^{7}
     {u}^{5} + 175{z}^{7}{u}^{4} + 175{z}^{7}{u}^{3} + 105{z}^{7}
     {u}^{2} + 35{z}^{7}{u} + 5{z}^{7}  - 35{z}^{6}{u}^{6} - 210{z}^{6}{u}^{5} - 525{z}^{6}
     {u}^{4} - 700{z}^{6}{u}^{3} - 525{z}^{6}{u}^{2} - 210{z}^{6}
     {u} - 35{z}^{6} + 105{z}^{5}{u}^{5} + 525{z}^{5}{u}^{4} + 1050
     {z}^{5}{u}^{3} + 1050{z}^{5}{u}^{2} + 525{z}^{5}{u} + 105
     {z}^{5}  - 175{z}^{4}{u}^{4} - 700{z}^{4}{u}^{3} - 1050
     {z}^{4}{u}^{2} - 700{z}^{4}{u} - 175{z}^{4} + 175{z}^{3}
     {u}^{3}  + 525{z}^{3}{u}^{2} + 525{z}^{3}{u} + 175{z}^{3} -
     105{z}^{2}{u}^{2} - 210{z}^{2}{u} - 105{z}^{2} + 35{z}{u}
     + 35{z} + 2{u}^{7} - 5$,\par}

{\scriptsize
$     p_{2}(z,u)  = 2{z}^{9}{u}^{13} + 13{z}^{9}{u}^{12} + 37
     {z}^{9}{u}^{11} + 58{z}^{9}{u}^{10} + 62{z}^{9}{u}^{9} + 202
     {z}^{9}{u}^{8} + 998{z}^{9}{u}^{7}  + 2872{z}^{9}{u}^{6} + 5018{z}^{9}{u}^{5} + 5637
     {z}^{9}{u}^{4} + 4125{z}^{9}{u}^{3} + 1910{z}^{9}{u}^{2} +
     510{z}^{9}{u} + 60{z}^{9} - 4{z}^{8}{u}^{13} - 40{z}^{8}{u}^{12} -
     151{z}^{8}{u}^{11} - 298{z}^{8}{u}^{10} - 348{z}^{8}{u}^{9}
     - 554{z}^{8}{u}^{8} - 2720{z}^{8}{u}^{7} - 9846{z}^{8}{u}^{6} - 20998
     {z}^{8}{u}^{5} - 27878{z}^{8}{u}^{4} - 23545{z}^{8}{u}^{3} 
 - 12360{z}^{8}{u}^{2} - 3690{z}^{8}{u} - 480{z}^{8}
     + 2{z}^{7}{u}^{13} + 41{z}^{7}{u}^{12} + 233{z}^{7}{u}^{11}
 + 611{z}^{7}{u}^{10} + 867{z}^{7}{u}^{9} + 847
     {z}^{7}{u}^{8} + 2611{z}^{7}{u}^{7} + 12483{z}^{7}{u}^{6} 
 + 34481{z}^{7}{u}^{5} + 56212{z}^{7}{u}^{4} + 56240
     {z}^{7}{u}^{3} + 34110{z}^{7}{u}^{2} + 11550{z}^{7}{u} 
 + 1680{z}^{7} - 14{z}^{6}{u}^{12} - 161{z}^{6}
     {u}^{11} - 630{z}^{6}{u}^{10} - 1183{z}^{6}{u}^{9} - 1170
     {z}^{6}{u}^{8} - 1259{z}^{6}{u}^{7} - 6966{z}^{6}{u}^{6} - 27635
     {z}^{6}{u}^{5} - 58808{z}^{6}{u}^{4} - 72400{z}^{6}{u}^{3}  - 52060{z}^{6}{u}^{2} - 20370{z}^{6}{u} - 3360{z}^{6}
     + 42{z}^{5}{u}^{11} + 329{z}^{5}{u}^{10} + 917{z}^{5}{u}^{9}
    + 1195{z}^{5}{u}^{8} + 745{z}^{5}{u}^{7} + 1557
     {z}^{5}{u}^{6} + 10729{z}^{5}{u}^{5} + 33377{z}^{5}{u}^{4} 
+ 53725{z}^{5}{u}^{3} + 47550{z}^{5}{u}^{2} + 22050
     {z}^{5}{u} + 4200{z}^{5} - 70{z}^{4}{u}^{10} - 385{z}^{4}
     {u}^{9}- 740{z}^{4}{u}^{8} - 605{z}^{4}{u}^{7} - 180{z}^{4}
     {u}^{6} - 1595{z}^{4}{u}^{5} - 9610{z}^{4}{u}^{4} - 22625
     {z}^{4}{u}^{3} - 26160{z}^{4}{u}^{2} - 14910{z}^{4}{u} - 3360
     {z}^{4} + 70{z}^{3}{u}^{9} + 267{z}^{3}{u}^{8} + 324{z}^{3}
     {u}^{7}  + 127{z}^{3}{u}^{6} + 1070{z}^{3}{u}^{4} + 4870
     {z}^{3}{u}^{3} + 8210{z}^{3}{u}^{2} + 6090{z}^{3}{u} + 1680
     {z}^{3}  - 78{z}^{2}{u}^{8} - 149{z}^{2}{u}^{7} - 71{z}^{2}
     {u}^{6} - 390{z}^{2}{u}^{3} - 1260{z}^{2}{u}^{2} - 1350
     {z}^{2}{u} - 480{z}^{2}  + 24{z}{u}^{8} + 55{z}{u}^{7} + 31{z}{u}^{6} + 60
     {z}{u}^{2} + 120{z}{u} + 60{z} - 7{u}^{6}$.\par}

 \smallskip

Reading off the coefficients we find   

   \begin{theorem}
      The expected value $E_{n,p}$ of the number of passes in 
{\sc Multiple      Quickselect} with  median-of-three partition is given by
   \begin{align}\begin{split}
         & E_{n,p} = \frac{12}{7} \frac{({n}+1)^{2}\,{p}}{({n}-{p}+1) \,
          ({n}-{p}+2)} \Big(H_{n}-H_p\Big)  \\
         & \qquad \quad {} - \frac{1}{7} \frac{r(n,p)}{n^{\underline{6}} \,
          (p+6)^{ \underline{6}} \, (n+1-p) \, (n+2-p)} \, , \enspace \mbox{{
           \rm for}} \; n \ge 6 \enspace \mbox{{\rm and}} \; 1 \le p \le n
         \, , \end{split}
	\\ \begin{split}
         & E_{1,1} = 1 \, , \enspace E_{2,1} = 1 \, , \enspace E_{2,2} = 1 \,
         , \enspace E_{3,1} = \frac{5}{3} \, , \enspace E_{3,2} = \frac{7}{3}
         \, , \enspace E_{3,3} = 3 \, , \\
         & E_{4,1} = \frac{7}{4} \, , \enspace E_{4,2} = \frac{7}{3} \, ,
         \enspace E_{4,3} = \frac{11}{4} \, , \enspace E_{4,4} = 3 \, ,
       \\
         & E_{5,1} = \frac{51}{25} \, , \enspace E_{5,2} = \frac{141}{50} \,
         , \enspace E_{5,3} = \frac{17}{5} \, , \enspace E_{5,4} =
         \frac{96}{25} \, , \enspace E_{5,5} = \frac{21}{5} \, ,\end{split}
   \end{align}
   { with}

{\scriptsize
$       r(n,p)  = 12{n}^{8}{p}^{7} + 247{n}^{8}{p}^{6} + 1995
       {n}^{8}{p}^{5} + 7945{n}^{8}{p}^{4} + 15813{n}^{8}{p}^{3}
       + 13048{n}^{8}{p}^{2} 
         - 180{n}^{8}{p} - 5040{n}^{8} - 12{n}^{7}{p}^{8} -
       422{n}^{7}{p}^{7} - 5598{n}^{7}{p}^{6} - 37058{n}^{7}
       {p}^{5} 
         - 131838{n}^{7}{p}^{4} - 244328{n}^{7}{p}^{3} -
       191592{n}^{7}{p}^{2} + 14688{n}^{7}{p} + 60480{n}^{7} 
         + 175{n}^{6}{p}^{8} + 4536{n}^{6}{p}^{7} + 48328
       {n}^{6}{p}^{6} + 271362{n}^{6}{p}^{5} + 850885{n}^{6}
       {p}^{4} 
         + 1429134{n}^{6}{p}^{3} + 1000692{n}^{6}{p}^{2} -
       97272{n}^{6}{p} - 272160{n}^{6} - 945{n}^{5}{p}^{8} 
         - 21560{n}^{5}{p}^{7} - 200550{n}^{5}{p}^{6} -
       977060{n}^{5}{p}^{5} - 2648205{n}^{5}{p}^{4} 
         - 3784340{n}^{5}{p}^{3} - 2220540{n}^{5}{p}^{2} +
       236880{n}^{5}{p} + 544320{n}^{5} + 2275{n}^{4}{p}^{8} 
         + 48048{n}^{4}{p}^{7} + 403333{n}^{4}{p}^{6} +
       1708875{n}^{4}{p}^{5} + 3752980{n}^{4}{p}^{4} 
         + 3919377{n}^{4}{p}^{3} + 1317372{n}^{4}{p}^{2} -
       477540{n}^{4}{p} - 347760{n}^{4} - 2163{n}^{3}{p}^{8} 
         - 42098{n}^{3}{p}^{7} - 309372{n}^{3}{p}^{6} -
       991802{n}^{3}{p}^{5} - 1085637{n}^{3}{p}^{4} 
         + 989548{n}^{3}{p}^{3} + 2813412{n}^{3}{p}^{2} +
       1168272{n}^{3}{p} - 362880{n}^{3} + 70{n}^{2}{p}^{8} 
         - 2196{n}^{2}{p}^{7} - 73908{n}^{2}{p}^{6} - 601272
       {n}^{2}{p}^{5} - 2321130{n}^{2}{p}^{4} - 4860324{n}^{2}
       {p}^{3} 
         - 5002312{n}^{2}{p}^{2} - 1360368{n}^{2}{p} + 624960
       {n}^{2} + 600{n}{p}^{8} + 15120{n}{p}^{7} 
         + 127440{n}{p}^{6} + 574560{n}{p}^{5} + 1625400{n}
       {p}^{4} + 2756880{n}{p}^{3} 
         + 2229600{n}{p}^{2} + 342720{n}{p} - 241920{n} +
       1440{p}^{7} + 10080{p}^{6} + 10080{p}^{5} 
         - 50400{p}^{4} - 80640{p}^{3} + 40320{p}^{2} + 69120
       {p}$.\par}                \qed
      \end{theorem}
Again we note the special cases.
\begin{ncor}
  \begin{align}  \begin{split}
     E_{n,1} & = \frac{12}{7} \frac{n+1}{n} H_{n} - \frac{131n-2}{49 n} \, ,
     \\
     E_{n,n} & = \frac{6}{7} n - \frac{1}{7} \, .
\end{split}
	 	\end{align}
  \end{ncor}
Related formul{\ae} can be found in \cite{GrKn82, Knuth73, KiMaPr97}.




\begin{ncor}
     \begin{align}
        E_{n,p} & = \frac{12}{7} p \log n - \frac{12}{7} p H_{p} +
        \frac{12}{7} p \gamma - {\frac{12p^{7}+247p^{6}+1995p^{5}
          +7945p^{4}+15813p^{3}+13048p^{2}-180p-5040}{{7 \, (p+6)^{
           \underline{6}}}}  }\\
        & \enspace {} + {\mathcal O}\left(\frac{\log n}{n}\right) \quad \mbox{{\rm
          for} $p$ {\rm fixed}} \, ,  \notag\\
\begin{split}
        E_{n,p} & = \frac{6}{7} n - \frac{2}{7} l - \frac{1}{7} + {\mathcal O}
        \left(\frac{\log n}{n}\right) \enspace \mbox{{\rm for} $l=n-p$ {\rm
          fixed}} \, ,\\
E_{n,p} & =\frac{12}{7} \frac{\rho(\rho-1-\log \rho)}{(1-\rho)^{2}}
        n + {\mathcal O}(1) \enspace \mbox{{\rm for fixed}} \; \rho =
        \frac{p}{n} \; \mbox{{\rm with}} \; 0 < \rho < 1 \, .
	\end{split}
     \end{align}   
  \end{ncor}  

\section{Median of three -- comparisons}


In this instance the differential equation is
   \begin{align}\begin{split}
      & \frac{1}{6} \frac{\partial^{3}}{\partial z^{3}} \Phi(z,u,v) = (1+u)
      \left( \frac{\partial}{\partial z} \Phi(zv,u,v)\right)^{2} + \frac{1}{
       (1-z)^{4}} - \frac{v^{2}}{(1-zv)^{4}} \, , \\
      & \Phi(0,u,v) = 1 \, , \enspace \left. \frac{\partial}{\partial z} \Phi
      (z,u,v)\right|_{z=0} = 1+u \, , \enspace \left. \frac{\partial^{2}}{
       \partial z^{2}} \Phi(z,u,v)\right|_{z=0} = 2(1+2uv+u^{2}v) \, .
	\end{split}
   \end{align}   
   With
   
   \begin{equation*}
      \Psi(z,u,v) = \frac{\partial}{\partial z} \Phi(z,u,v) \, 
   \end{equation*}   
and   
\begin{equation*}
      G(z,u) = \left. \frac{\partial}{\partial v} \Psi(z,u,v) \right|_{v=1}
         \end{equation*}
   we get
   
   \begin{align}\begin{split}
      & \frac{1}{6} \frac{\partial^{2}}{\partial z^{2}} G(z,u) = \frac{2(1+u
       )^{2}}{(1-z(1+u))^{2}} G(z,u) + \frac{2(1+u)^{3}(1+z(1+u))}{(1-z(1+u)
       )^{5}} - \frac{2(1+z)}{(1-z)^{5}} \, , \\
      & G(0,u) = 0 \, , \enspace \left. \frac{\partial}{\partial z} G(z,u)
      \right|_{z=0} = 4u + 2u^{2} \, .
	\end{split}
   \end{align}
and furthermore
   \begin{align} \begin{split}
      G(z,u) & = \frac {24}{7} \frac {(1+u)^{2} \, p_{1}(z,u)}{ (1-z(1+{u})
       )^{3} \,{u}^{7}} \log\frac{1}{1-{z}} - \frac{24}{7}
      \frac{(1+{u}) \, p_{2}(z,u)}{(1-z(1+{u}))^{3}\,{u}^{7}} \log
      \frac{1}{1-z(1+{u})} \\ 
      & \quad {} - \frac{2}{49} \frac{{z} \, g_{3} (z,u)} {(1-z(1+u))^{3}\,
       (1-z)^{3} \,{u}^{6}} \, ,
	\end{split}
   \end{align}
   with

{\scriptsize
$      p_{1}(z,u)  = 10 {z}^{7}{u}^{8} +
      85 {z}^{7}{u}^{7} + 315{z}^{ 7}{u}^{6} + 665{z}^{7}{u}^{5}
      + 875 {z}^{7}{u}^{4} + 735 {z}^{7}{u}^{3} + 385{z}^{7}
      {u}^{2}  + 115{z}^{7}{u} + 15{z}^{7} - 70{z}^{6}
      {u} ^{7} - 525 {z}^{6}{u}^{6} - 1680{z}^{6}{u}^{5} - 2975
      {z} ^{6}{u}^{4}  - 3150{z}^{6}{u}^{3} - 1995
      {z}^{6}{u}^{2} - 700 {z}^{6}{u} - 105{z}^{6} + 210{z}^{5}
      {u}^{6} + 1365 {z}^{5} {u}^{5} + 3675{z}^{5}
      {u}^{4} + 5250{z}^{5}{u}^{3} + 4200{z}^{5}{u}^{2} + 1785
      {z}^{5}{u} + 315{z}^{5} - 350 {z}^{4}{u}^{5} -
      1925{z}^{4}{u}^{4} - 4200{z}^{4} {u}^{3} - 4550{z}^{4}
      {u}^{2} - 2450{z}^{4}{u} - 525{z}^{4} + 350 {z}^{3}{u}^{4}
     + 1575{z}^{3}{u}^{3} + 2625 {z}^{3}{u}^{2} + 1925
      {z}^{3}{u} + 525{z}^{3} - 210{z}^{2} {u}^{3} - 735 {z}^{2}
      {u}^{2} - 840{z}^{2}{u} - 315 {z}^{2} + 70{z}
      {u}^{2 } + 175{z}{u} + 105{z} - 3{u}^{8} - {u}^{7} - 10{u}
      - 15$,\par}

{\scriptsize
$      p_{2}(z,u)  = 10{z}^{7}{u}^{9} + 95{z}^{7}{u}^{8} + 400
      {z}^{7}{u}^{7} + 980{z}^{7}{u}^{6} + 1540{z}^{7}{u}^{5} +
      1610{z}^{7}{u}^{4} + 1120{z}^{7}{u}^{3} 
 + 500{z}^{7}{u}^{2} + 130{z}^{7}{u} + 15{z}^{7} -
      70{z}^{6}{u}^{8} - 595{z}^{6}{u}^{7} - 2205{z}^{6}{u}^{6} -
      4655{z}^{6}{u}^{5} - 6125{z}^{6}{u}^{4} - 5145{z}^{6}{u}^{3} - 2695
      {z}^{6}{u}^{2} - 805{z}^{6}{u} - 105{z}^{6} + 210{z}^{5}
      {u}^{7} + 1575{z}^{5}{u}^{6} + 5040{z}^{5}{u}^{5} + 8925
      {z}^{5}{u}^{4} + 9450{z}^{5}{u}^{3} + 5985{z}^{5}{u}^{2}
      + 2100{z}^{5}{u} + 315{z}^{5} - 350{z}^{4}{u}^{6} -
      2275{z}^{4}{u}^{5} - 6125{z}^{4}{u}^{4} - 8750{z}^{4}
      {u}^{3} - 7000{z}^{4}{u}^{2} - 2975{z}^{4}{u} - 525{z}^{4}
      + 350{z}^{3}{u}^{5} + 1925{z}^{3}{u}^{4} + 4200{z}^{3}
      {u}^{3}  + 4550{z}^{3}{u}^{2} + 2450{z}^{3}{u} + 525{z}^{3}
      - 210{z}^{2}{u}^{4} - 945{z}^{2}{u}^{3} - 1575{z}^{2}
      {u}^{2} - 1155{z}^{2}{u} - 315{z}^{2} + 70{z}{u}^{3} + 245
      {z}{u}^{2} + 280{z}{u} + 105{z} - {u}^{7} - 10{u}^{2} - 25{u} - 15$,\par} 

{\scriptsize
$      p_{3}(z,u)  = 2{z}^{9}{u}^{14} + 16{z}^{9}{u}^{13} + 49
      {z}^{9}{u}^{12} + 91{z}^{9}{u}^{11} + 14{z}^{9}{u}^{10} -
      2450{z}^{9}{u}^{9} - 17374{z}^{9}{u}^{8} 
 - 60926{z}^{9}{u}^{7} - 130534{z}^{9}{u}^{6} - 184296
      {z}^{9}{u}^{5} - 176127{z}^{9}{u}^{4} - 113365{z}^{9}
      {u}^{3}  - 47250{z}^{9}{u}^{2} - 11550{z}^{9}{u} - 1260
      {z}^{9} - 6{z}^{8}{u}^{14} - 62{z}^{8}{u}^{13} - 245{z}^{8}
      {u}^{12}  - 518{z}^{8}{u}^{11} - 434{z}^{8}{u}^{10} + 6804
      {z}^{8}{u}^{9} + 60998{z}^{8}{u}^{8} + 253940{z}^{8}{u}^{7}
       + 631002{z}^{8}{u}^{6} + 1015546{z}^{8}{u}^{5} +
      1091195{z}^{8}{u}^{4} + 780850{z}^{8}{u}^{3} 
 + 358470{z}^{8}{u}^{2} + 95760{z}^{8}{u} + 11340
      {z}^{8} + 6{z}^{7}{u}^{14} + 90{z}^{7}{u}^{13} + 483{z}^{7}
      {u}^{12} + 1260{z}^{7}{u}^{11} + 1701{z}^{7}{u}^{10} - 5439
      {z}^{7}{u}^{9} - 78855{z}^{7}{u}^{8} - 415647{z}^{7}{u}^{7}
       - 1244265{z}^{7}{u}^{6} - 2342319{z}^{7}{u}^{5} -
      2882880{z}^{7}{u}^{4} - 2326065{z}^{7}{u}^{3}
- 1189230{z}^{7}{u}^{2} - 350280{z}^{7}{u} - 45360
      {z}^{7} - 2{z}^{6}{u}^{14} - 58{z}^{6}{u}^{13} - 469{z}^{6}
      {u}^{12}  - 1652{z}^{6}{u}^{11} - 2989{z}^{6}{u}^{10} - 742
      {z}^{6}{u}^{9} + 43617{z}^{6}{u}^{8} + 332316{z}^{6}{u}^{7}
       + 1274453{z}^{6}{u}^{6} + 2914716{z}^{6}{u}^{5} +
      4216380{z}^{6}{u}^{4} + 3907820{z}^{6}{u}^{3} 
 + 2256450{z}^{6}{u}^{2} + 740880{z}^{6}{u} + 105840
      {z}^{6} + 14{z}^{5}{u}^{13} + 224{z}^{5}{u}^{12}
     + 1211{z}^{5}{u}^{11} + 2961{z}^{5}{u}^{10} + 3640
      {z}^{5}{u}^{9} - 7161{z}^{5}{u}^{8} - 128646{z}^{5}{u}^{7}
       - 709779{z}^{5}{u}^{6} - 2096234{z}^{5}{u}^{5} -
      3701635{z}^{5}{u}^{4} - 4043165{z}^{5}{u}^{3} 
- 2685690{z}^{5}{u}^{2} - 996660{z}^{5}{u} - 158760
      {z}^{5} - 42{z}^{4}{u}^{12} - 462{z}^{4}{u}^{11}
       - 1743{z}^{4}{u}^{10} - 2898{z}^{4}{u}^{9} - 2205
      {z}^{4}{u}^{8} + 18648{z}^{4}{u}^{7} + 201453{z}^{4}{u}^{6}
       + 860622{z}^{4}{u}^{5} + 1971627{z}^{4}{u}^{4} +
      2635290{z}^{4}{u}^{3} + 2065350{z}^{4}{u}^{2} 
+ 882000{z}^{4}{u} + 158760{z}^{4} + 70{z}^{3}
      {u}^{11} + 560{z}^{3}{u}^{10} + 1484{z}^{3}{u}^{9}
       + 1568{z}^{3}{u}^{8} + 574{z}^{3}{u}^{7} - 22330
      {z}^{3}{u}^{6} - 183015{z}^{3}{u}^{5} - 609210{z}^{3}
      {u}^{4}  - 1058575{z}^{3}{u}^{3} - 1015770{z}^{3}{u}^{2} -
      511560{z}^{3}{u} - 105840{z}^{3} - 70{z}^{2}{u}^{10}
       - 868{z}^{2}{u}^{9} - 1526{z}^{2}{u}^{8} - 728
      {z}^{2}{u}^{7} + 14980{z}^{2}{u}^{5} + 96110{z}^{2}{u}^{4}
      + 243040{z}^{2}{u}^{3} + 303030{z}^{2}{u}^{2} +
      186480{z}^{2}{u} + 45360{z}^{2} + 672{z}{u}^{9}
       + 1491{z}{u}^{8} + 819{z}{u}^{7} - 5460{z}{u}^{4}
      - 26670{z}{u}^{3} - 48300{z}{u}^{2} - 38430{z}{u}
      - 11340{z} - 252{u}^{9} - 553{u}^{8} - 350{u}^{7} +
      840{u}^{3} + 2940{u}^{2} + 3360{u} + 1260$.\par}

\smallskip

Reading off the coefficients we get   

     \begin{theorem}
  The expected value $E_{n,p}$ of the number of comparisons in 
{\sc Multiple      Quickselect} with  median-of-three partition is given by
      \begin{align}\begin{split}
         & E_{n,p} = - \frac{12}{7} \frac{({n}+1)\,(4{n}-{p}+5)\,{p}}
         {({n}-{p}+1)\,({n}-{p}+2)} H_{n} + \frac{12}{7} \frac{({n}+1)^{2}\,
         ({n}+2{p}+2)}{({n}-{p}+2)\,({n}-{p}+1)} H_{p}  \\
         & \qquad \quad {} + \frac{1}{49} \frac{r(n,p)}{n^{\underline{6}} \,
          (p+7)^{ \underline{7}} \, (n+1-p) \, (n+2-p)} \, , \enspace \mbox{{
           \rm for}} \; n \ge 6 \enspace \mbox{{\rm and}} \; 1 \le p \le n
         \, ,  \end{split} \\
         	\begin{split}
	& E_{1,1} = 0 \, , \enspace E_{2,1} = 1 \, , \enspace E_{2,2} = 1 \,
         , \enspace E_{3,1} = 2 \, , \enspace E_{3,2} = 2 \, , \enspace
         E_{3,3} = 2 \, ,  \\
         & E_{4,1} = \frac{7}{2} \, , \enspace E_{4,2} = \frac{23}{6} \, ,
         \enspace E_{4,3} = 4 \, , \enspace E_{4,4} = 4 \, ,\\
         & E_{5,1} = \frac{126}{25} \, , \enspace E_{5,2} = \frac{141}{25} \,
         , \enspace E_{5,3} = \frac{148}{25} \, , \enspace E_{5,4} = 6 \, ,
         \enspace E_{5,5} = 6 \, .
	\end{split}
      \end{align}
      {with}

{\scriptsize
$         r(n,p)  = 37{n}^{9}{p}^{7} + 1036{n}^{9}{p}^{6} + 11914
         {n}^{9}{p}^{5} + 72520{n}^{9}{p}^{4} + 250453{n}^{9}
         {p}^{3} + 485884{n}^{9}{p}^{2}  
           + 483516{n}^{9}{p} + 246960{n}^{9} + 178{n}^{8}
         {p}^{8} + 4423{n}^{8}{p}^{7} + 41608{n}^{8}{p}^{6}
                  + 168238{n}^{8}{p}^{5} + 105322{n}^{8}{p}^{4} -
         1459913{n}^{8}{p}^{3} - 5040948{n}^{8}{p}^{2}         
         - 6877548{n}^{8}{p} - 3210480{n}^{8} - 215{n}^{7}
         {p}^{9} - 8651{n}^{7}{p}^{8} - 139688{n}^{7}{p}^{7}          
           - 1178702{n}^{7}{p}^{6} - 5578475{n}^{7}{p}^{5} -
         14341019{n}^{7}{p}^{4} - 15631422{n}^{7}{p}^{3}          
           + 8099412{n}^{7}{p}^{2} + 31066920{n}^{7}{p} +
         16299360{n}^{7} + 3192{n}^{6}{p}^{9}  
           + 103600{n}^{6}{p}^{8} + 1417654{n}^{6}{p}^{7} +
         10600072{n}^{6}{p}^{6} + 46767364{n}^{6}{p}^{5}          
           + 121653280{n}^{6}{p}^{4} + 168818566{n}^{6}
         {p}^{3} + 84897288{n}^{6}{p}^{2} - 38913336{n}^{6}{p}
                     - 40007520{n}^{6} - 17780{n}^{5}{p}^{9} - 529760
         {n}^{5}{p}^{8} - 6609827{n}^{5}{p}^{7}  
           - 44872436{n}^{5}{p}^{6} - 179988074{n}^{5}{p}^{5}
         - 428908760{n}^{5}{p}^{4} - 581222523{n}^{5}{p}^{3}
                     - 387896964{n}^{5}{p}^{2} - 53621316{n}^{5}{p} +
         43711920{n}^{5} + 45570{n}^{4}{p}^{9}  
           + 1288672{n}^{4}{p}^{8} + 15030547{n}^{4}{p}^{7} +
         93440452{n}^{4}{p}^{6} + 331748032{n}^{4}{p}^{5}
                     + 679515928{n}^{4}{p}^{4} + 772514743{n}^{4}
         {p}^{3} + 431025588{n}^{4}{p}^{2}  
           + 83709108{n}^{4}{p} + 740880{n}^{4} - 51485
         {n}^{3}{p}^{9} - 1380029{n}^{3}{p}^{8}  
           - 14864922{n}^{3}{p}^{7} - 80529498{n}^{3}{p}^{6}
         - 228035325{n}^{3}{p}^{5} - 283648701{n}^{3}{p}^{4}
                     + 46816532{n}^{3}{p}^{3} + 407511188{n}^{3}{p}^{2}
         + 191861280{n}^{3}{p} - 48404160{n}^{3}  
           + 16758{n}^{2}{p}^{9} + 376590{n}^{2}{p}^{8} +
         2608656{n}^{2}{p}^{7} + 2675148{n}^{2}{p}^{6}
                     - 62468994{n}^{2}{p}^{5} - 381548370{n}^{2}{p}^{4}
         - 945477876{n}^{2}{p}^{3} - 1039134408{n}^{2}{p}^{2}
                     - 367655184{n}^{2}{p} + 42477120{n}^{2} + 3960{n}
         {p}^{9} + 169560{n}{p}^{8}  
           + 2311200{n}{p}^{7} + 18975600{n}{p}^{6} +
         99068760{n}{p}^{5} + 310910040{n}{p}^{4}  
           + 552004560{n}{p}^{3} + 497069280{n}{p}^{2} +
         161881920{n}{p} - 11854080{n}  
           + 20160{p}^{8} + 161280{p}^{7} + 282240{p}^{6} -
         564480{p}^{5} - 1834560{p}^{4}  
           - 564480{p}^{3} + 1532160{p}^{2} + 967680{p} 
      $.\qed\par}

  \end{theorem}

Again, we list the two prominent special cases.

\begin{ncor}
  \begin{align}  \begin{split}
     E_{n,1} & = \frac{245n^{2}+1111n-2}{98 n} - \frac{48}{7} \frac{n+1}{n}
     H_{n} \, , \\
     E_{n,n} & = \frac{12}{7} (n+1) H_{n} - \frac{173}{49} n + \frac{9}{49}
     \; .
	\end{split}
  \end{align}
  \end{ncor}
  

And here are the asymptotics.

\begin{ncor}
     \begin{align}
        E_{n,p} & = \left(\frac{12}{7} H_{p} + {\frac{37p^{7}
         +1036p^{6}+11914p^{5}+72520p^{4}+250453p^{3}+485884p^{2}+483516p
         +246960}{\displaystyle{49 \, (p+7)^{\underline{7}}}}} \right) n \\
        & \enspace {} + {\mathcal O}\left(\log n\right) \quad \mbox{{\rm
          for} $p$ {\rm fixed}} \, , \\
        E_{n,p} & = \frac{12}{7}n \log n + \frac{84 \gamma -173}{49} n +
        \frac{12}{7} \log n + \frac{51}{49} + \frac{12}{7} \gamma + {\mathcal O}
        \left(\frac{\log n}{n}\right) \enspace \mbox{{\rm for} $l=n-p$ {\rm
          fixed}} , , \notag\\
\begin{split}
E_{n,p} & = \frac{12}{7} n \log n  + \frac{168 \rho \log \rho + 84
         \log \rho + 84 \gamma \rho^{2} - 168 \gamma \rho + 84 \gamma - 215
         \rho^{2} + 178 \rho + 37}{49 (1-\rho)^{2}} n  \\
        & \quad {} + {\mathcal O} (\log n) \enspace \mbox{{\rm for fixed}} \;
        \rho = \frac{p}{n} \; \mbox{{\rm with}} \; 0 < \rho < 1 \, .
	\end{split}
     \end{align}   
  \end{ncor}  











\section{Binary trees}

In this section we briefly sketch -- for the reason of comparison --
the analogous questions for the instance of binary (Catalan) trees, 
enumerated by Catalan numbers
\begin{equation*}   
b_n=\frac{1}{n+1}\binom{2n}{n};
\end{equation*}
note that
\begin{equation*}   
B(z)=\sum_{n\ge0}b_nz^n=\frac{1-\sqrt{1-4z}}{2z}\;.
\end{equation*}
Then the equation for the number of passes is
\begin{equation}   
F(z,u,v)=zv(1+u)F^2(z,u,v)+v+(1-v)B(z)\;.
\end{equation}
The normalization factor is this time $\binom{n}{p}b_n$. 
This quadratic equation is of course readily solved; here, we only
compute the average. We get
\begin{equation}   
\frac{\partial F(z,u,v)}{\partial v}\bigg|_{v=1}=-B\big(z(1+u)\big)
+\frac{1}{2z}\frac{\sqrt{1-4z}-(1-4z)}{\sqrt{1-4z(1+u)}}\;.
\end{equation}
A standard evaluation of this function gives after division by
the normalization factor.
\begin{theorem} The average number of passes in the model of
binary trees is given by
\begin{equation}   
E_{n,p}=\frac{p(n+1)\binom{2p}{p}4^{n+1-p}}{2(n+1-p)\binom{2n}{n}}-
\frac{p(2n+1)}{n+1-p}\;.
\end{equation}
\end{theorem}


\begin{ncor}
     \begin{align}\begin{split}
        E_{n,p} & = \frac{2p\binom{2p}{p}}{4^p}\sqrt{\pi n}
	 + {\mathcal O}(1) \quad \mbox{{\rm
          for} $p$ {\rm fixed}} \, , \\
        E_{n,p} & = n + {\mathcal O}
        (1) \enspace \mbox{{\rm for} $l=n-p$ {\rm
          fixed}} \, , \\
	E_{n,p} & = \frac{2\sqrt{\rho}}{1+\sqrt{\rho}}{n}+{\mathcal O}(1)
	\quad \mbox{{\rm for} $p = \rho n$ {\rm and} $0 < \rho < 1$}\,.
	\end{split}
     \end{align}   
  \end{ncor}  

In the instance of the comparisons we get
\begin{equation}   
F(z,u,v)=z(1+u)F^2(zv,u,v)+v^{-1}+B(z)-v^{-1}B(zv)\;.
\end{equation}

The equation for the expectations (obtained by differentation
w.r.t. $v$ and $v=1$) has the solution
\begin{equation}   
G(z,u) = \frac{4}{Y+1} + \frac{1}{Y^{2}} - \frac{4}{Y} + \frac{4}{Y(X+1
       )} - \frac{1}{XY} \, ,
\end{equation} 
with

\begin{equation*}   
X=\sqrt{1-4z}\quad\text{and}\quad Y=\sqrt{1-4z(1+u)}\;.
\end{equation*}
After some routine computations we get from that:

\begin{theorem} The average number of comparisons in the model of
binary trees is given by
\begin{equation}   
 E_{n,p} =  \frac{(n+1)4^{n}}{\binom{2n}{n}} - \frac{(n+1)(n+3p+1
       )4^{n-p}}{n+1-p} \frac{\binom{2p}{p}}{\binom{2n}{n}} + \frac{2p(2n+1
       )}{n+1-p} \quad \mbox{{\rm for}} \; 1 \le p \le n \, .
\end{equation}
\end{theorem}


\begin{ncor} 
   \begin{align}\begin{split}
        E_{n,p} & = \bigg(1-\frac{\binom{2p}{p}}{4^{p}}\bigg) \sqrt{\pi}
        \, n^{{3}/{2}}+ {\mathcal O}\left(\sqrt{n}\,\right) \enspace \mbox{{\rm
          for} $p$ {\rm fixed}} \, ,  \\
        E_{n,p} & = \sqrt{\pi} \, n^{{3}/{2}} - 3n + {\mathcal O}\left(\sqrt{n}\,
        \right) \enspace \mbox{{\rm for} $l=n-p$ {\rm fixed}} \, ,  \\
        E_{n,p} & = \sqrt{\pi} \, n^{{3}/{2}} -
	\frac{1+\sqrt\rho+4\rho}{(1+\sqrt\rho\,)
	\sqrt{\rho}} \, n + {\mathcal O} \left(\sqrt{n}\,
         \right) \enspace \mbox{{\rm for fixed}} \; \rho = \frac{p}{n} \;
         \mbox{{ \rm with}} \; 0 < \rho < 1 \, .
\end{split} 
 \end{align}   


\end{ncor}  




 \begin{ackno} We thank 
Philippe Flajolet who insisted that such an approach should be feasible.
As the paper shows, he was right (as usual).
 \end{ackno}


   \bibliographystyle{plain}
\bibliography{pro_bib}
   
\end{document}

