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

[Marko Riedel <mriedel@xxxxxxxxxxxxx>]

Greetings.

I have computed the DE for the second factorial moment of the expected
distance from the identity permutation. I was not able to solve it
with MAXIMA (the URL is http://www.ma.utexas.edu/maxima.html),
although I tried for quite some time.

I am sending what I have.

Best regards,

Marko Riedel

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


\documentclass{article}

\usepackage{latexsym,amsfonts,amssymb,amsmath,amstext,amsthm}

\begin{document}

\newcommand{\half}{\frac1{2}}
\newcommand{\thrd}{\frac1{3}}
\newcommand{\qurt}{\frac1{4}}
\newcommand{\ffth}{\frac1{5}}
\newcommand{\sxth}{\frac1{6}}
\newcommand{\octa}{\frac1{8}}
\newcommand{\dode}{\frac1{12}}

\newcommand{\EVAL}[2]{\left. #1 \right|_{#2}} 

\newcommand{\PAR} [1]{\left(#1\right)}
\newcommand{\MAND}  {\quad \text{and   }  \quad}
\newcommand{\MFOR}  {\quad \text{for   }  \quad}
\newcommand{\MWHERE}{\quad \text{where }  \quad}

\newcommand{\DZ} {\frac{\partial}{\partial z}}
\newcommand{\DV} {\frac{\partial}{\partial v}}
\newcommand{\DVV}{\frac{\partial}{\partial v^2}}

\title{Quickselect and the distance to the identity permutation}

\author{Marko Riedel}
\maketitle

\section{Recurrence relation}

Consider the following question. What amount of disorder is left in a
permutation after one of its elements has been selected with
quickselect?

This can be rephrased as follows. Compute the "grand average" for the
expected distance to the identity permutation of a permutation after
one of its elements has been selected with quickselect, where $1,
2,\ldots n$ are the elements being permuted and the distance is
given by

\[ \sum_{m=1}^n \PAR{ m - p_m }^p,\]

$p>1$ and $p$ even.

Let $r_n(v)$ be the exponential generating function of the distance to
the identity permutation of a random permutation of size $n$. We have
$r_n(1) = 1$ and

\[ r_n'(1)  = 
   \frac{2}{n} \sum_{k=1}^{n - 1}  k^p \: (n - k) \MAND
   r_n''(1) = 
   \frac{2}{n} \sum_{k=1}^{n - 1}  k^p \: (k^p - 1) \: (n - k)
.\]

Recall that
\begin{eqnarray*}
\sum_{k = 1}^n k^2 & = &
\thrd n^3 + \half n^2 + \sxth n                       \\
\sum_{k = 1}^n k^3 & = &
\qurt n^4 + \half n^3 + \qurt n^2                     \\
\sum_{k = 1}^n k^4 & = &
\ffth n^5 + \half n^4 + \thrd n^3 - \frac1{30} n      \\
\sum_{k = 1}^n k^5 & = &
\sxth n^6 + \half n^5 + \frac{5}{12} n^4 - \dode n^2.
\end{eqnarray*}

This yields
\begin{eqnarray*}
   r_n'(1) & = & 
   \frac{2}{n} \: n \:
   \PAR { \thrd (n-1)^3 + \half (n-1)^2 + \sxth (n-1)   } \\
           & - & 
   \frac{2}{n} \:
   \PAR { \qurt (n-1)^4 + \half (n-1)^3 + \qurt (n-1)^2 }
\end{eqnarray*}
for $k=2$ and
\begin{eqnarray*}
   r_{n,4}'(1) & = & 
   \frac{2}{n} \: n \:
   \PAR { \ffth (n-1)^5 + \half (n-1)^4 
                        + \thrd (n-1)^3 - \frac1{30} (n-1) } \\
           & - & 
   \frac{2}{n} \:
   \PAR { \sxth (n-1)^6 + \half (n-1)^5 
                        + \frac{5}{12} (n-1)^4 - \dode (n-1)^2}
\end{eqnarray*}
for $k=4.$

Hence
\begin{eqnarray*}
   r_n'(1) 
   & = & \sxth      \: n \PAR { n^2 - 1 } 
   \MAND \\
   r_{n, 4}'(1) 
   & = & \frac1{30} \: n \PAR { n^2 - 1 } \PAR{ 2 n^2 - 3 }.
\end{eqnarray*}

Compute $r_n''(1)$ for $k=2$, as follows:
\begin{eqnarray*}
   r_n''(1) & = &
   \frac{2}{n} \sum_{k=1}^{n - 1} 
   \PAR{ n k^4 - k^5 - n k^2 + k^3 } \\ & = &
   r_{n, 4}'(1) - r_n'(1) =
   \frac1{15} (n - 2) (n - 1) n (n + 1) (n + 2).
\end{eqnarray*}


Let $q_{n, j}(v)$ be the exponential generating function of the number
of inversions after the element $j$, where $1 \le j \le n$ has been
selected from a random permutation of size $n$. The base cases are:
$n=1$ and $q_{1, 1}(v) = 1/1 = 1$ and $n=2$ and $q_{2, 1}(v) = q_{2,
2}(v) = 2/2 = 1.$ We let $r_0(v) = q_{0, j}(v) = 1.$ Let $p$ denote
the pivot, where $1 \le p \le n$. The recurrence for $q_{n, j}(v)$ is
as follows.
\begin{eqnarray*}
 q_{n, j}(v)  & = &
  \frac1{n} 
  \sum_{p=1}^{j-1} r_{p-1}(v) q_{n-p, j-p}(v) \\
   & + & \frac1{n} r_{j-1}(v) r_{n-j}(v)    \\
   & + & \frac1{n} \sum_{p=j+1}^n q_{p-1, j}(v) r_{n-p}(v).
\end{eqnarray*}

We are interested in the asymptotics of
\[ \frac{q_n'(1)}{n}
   \MWHERE
   q_n(v) = \sum_{j=1}^n q_{n, j}(v).\]

\newpage

\section{Trivariate generating function}

Let
\[ R(z, v) = \sum_{n \ge 1} r_n(v) z^n  \]
and
\[ F(z, u, v) = \sum q_{n,j}(v) u^j z^n.\]
Recall that $r_n(1) = 1, r_n'(1) = \sxth n \PAR { n^2 - 1 },
             r_n''(1) = \frac1{15} n (n^2 - 1) (n^ - 4)$ and
$q_{n, l}(1) = 1$ and hence
\begin{eqnarray*}
 F(z, u, 1) & = & \sum_{n \ge 1} \sum_{j=1}^n u^j z^n =
   \sum_{n \ge 1} z^n
   \PAR{ -1 + \frac{1 - u^{n+1}}{1 - u}} \\
   & = & - \frac{z}{1 - z} 
         + \frac{1}{1 - u} \frac{z}{1 - z} 
         - \frac{u}{1 - u} \frac{z u}{1 - z u} \\
   & = &   \frac{z u}{(1 - z)(1 - z u)},
\end{eqnarray*}
\[ R(z, 1) = \frac1{1 - z},\]
\[
 \PAR{ \DV R(z, v) }(z, 1) =
 \sxth z^3 \PAR{ \frac1{1-z} }''' +
 \half z^2 \PAR{ \frac1{1-z} }''
 = \frac{z^2}{(1 - z)^4},\]
and
\[
 \PAR{ \DVV R(z, v) }(z, 1) =
 \frac1{15} \: z^3 \: \PAR{\frac1{1-z} }^{(5)} =
 \frac{ 8 z^3 }{(1 - z)^6}.\]

We have
\begin{eqnarray*}
 n q_{n, j}(v) u^j z^{n-1}  & = &
   u \sum_{p=1}^{j-1} r_{p-1}(v) u^{p-1} z^{p-1} 
                    q_{n-p, j-p}(v) u^{j-p} z^{n-p}  \\
   & + & u r_{j-1}(v) u^{j-1} z^{j-1} r_{n-j}(v) z^{n-j}  \\
   & + & 
   \sum_{p=j+1}^n q_{p-1, j}(v) u^j z^{p-1} r_{n-p}(v) z^{n-p}
\end{eqnarray*}
and hence
\[\DZ F(z,u,v) = 
  u R(zu,v) F(z,u,v) + u R(zu,v) R(z,v) + R(z,v) F(z,u,v).\]
Differentiate with respect to $v$ to obtain
\begin{eqnarray*}
\DV \DZ F(z,u,v) & = &
  u \DV R(zu,v) F(z,u,v) + u R(zu,v) \DV F(z,u,v) \\ & + &
  u \DV R(zu,v) R(z,v) + u R(zu,v) \DV R(z,v) \\ & + &
  \DV R(z,v) F(z,u,v) + R(z,v) \DV F(z,u,v).
\end{eqnarray*}
Let 
\[ G(z, u)   = \EVAL{ \PAR{ \DV  F(z,u,v) }}{v=1} \MAND 
   G_1(z, u) = \EVAL{ \PAR{ \DVV F(z,u,v) }}{v=1}\]
and set $v=1$ so that
\begin{eqnarray*}
\DZ G(z, u) & = &
  u  \frac{z^2 u^2}{(1 - z u)^4}  
     \frac{z u}{(1 - z)(1 - z u)}
+ u \frac1{1 - z u} G(z, u) \\ & + &
  u \frac{z^2 u^2}{(1 - z u)^4}
    \frac1{1 - z}
+ u \frac1{1 - z u} \frac{z^2}{(1 - z)^4} \\ & + &
    \frac{z^2}{(1 - z)^4} \frac{z u}{(1 - z)(1 - z u)}
+ \frac1{1 - z} G(z, u).
\end{eqnarray*}
or
\begin{eqnarray*}
& & \DZ G(z, u) =
\frac{1 + u - 2 z u}{(1 - z) (1 - z u)} G(z, u) \\
& & + \: u z^2
\frac{      u^4 z^4
       +    u^2 z^4
       -  4 u^3 z^3
       -  4 u^2 z^3
       + 12 u^2 z^2
       -  4 u^2 z
       -  4 u   z
       +    u^2
       +  1         
 }
{(1 - z)^5 (1 - z u)^5}
\end{eqnarray*}
Solve this to obtain
\[ G(z,u) =
- \thrd \: u z^3 \:
\frac {    u^3 z^3
      +    u^2 z^3
      -  6 u^2 z^2
      +  3 u^2 z
      +  3 u   z
      -    u^2
      -  1}
{(1 - z)^4 (1 - z u)^4}.
\]

\section{Second factorial moment}

Start with
\begin{eqnarray*}
\DVV \DZ F(z,u,v) & = &
  u \DVV R(zu,v)      F(z,u,v) + 
2 u \DV  R(zu,v) \DV  F(z,u,v) \\ & + &
  u      R(zu,v) \DVV F(z,u,v) \\ & + &
  u \DVV R(zu,v)      R(z,v)   +
2 u \DV  R(zu,v) \DV  R(z,v)   \\ & + &
  u      R(zu,v) \DVV R(z,v)   \\ & + &
    \DVV R(z,v)       F(z,u,v) +
2   \DV  R(z,v)  \DV  F(z,u,v) \\ & + &
         R(z,v)  \DVV F(z,u,v).
\end{eqnarray*}
and hence

\begin{eqnarray*}
\DZ G_1(z,u) & = &
  u \frac{ 8 z^3 u^3 }{(1 - z u)^6} \frac{z u}{(1 - z)(1 - z u)} +
2 u \frac{z^2 u^2}{(1 - z u)^4} G(z, u) \\ & + &
  u \frac1{1 - z u} G_1(z, u) \\ & + &
  u \frac{ 8 z^3 u^3 }{(1 - z u)^6} \frac1{1 - z}  +
2 u \frac{z^2 u^2}{(1 - z u)^4} \frac{z^2}{(1 - z)^4}  \\ & + &
  u \frac1{1 - z u} \frac{ 8 z^3 }{(1 - z)^6}  \\ & + &
    \frac{ 8 z^3 }{(1 - z)^6}  \frac{z u}{(1 - z)(1 - z u)} +
2   \frac{z^2}{(1 - z)^4}  G(z, u) \\ & + &
    \frac1{1 - z} G_1(z, u).
\end{eqnarray*}

References. Basic generating functions.

\end{document}