\documentclass[11pt,reqno]{amsart}%{article}
\usepackage{amsfonts,amsmath,amssymb}
%\usepackage{epsfig}
\usepackage{graphicx}

\topmargin 0 pt                        
\textheight 46\baselineskip     
\advance\textheight by \topskip
%\setlength{\parindent}{0pt}            
\setlength{\parskip}{2pt plus 2pt minus 1pt}     
\setlength{\textwidth}{155mm}         
\setlength{\oddsidemargin}{5.6mm}     
\setlength{\evensidemargin}{5.6mm}   

\allowdisplaybreaks

\def\al{\alpha}

\newtheorem{theorem}{Theorem}
\newtheorem{theor}{Theorem}
\renewcommand{\thetheor}{\!\!}

\newtheorem{lemma}{Lemma}

\newtheorem{prop}{Proposition}
% \numberwithin{equation}{section}

\def\P{{\mathbb {P}}}
\def\E{{\mathbb {E}}}
\def\V{{\mathbb {V}}}
\def\t{\vartheta}\def\tt{\bar{\vartheta}}
\def\v{\textsf{value}}
\def\mm{\widehat m}
\def\ma{\widehat a}
\def\Card{\mathit{Card}}
% other useful commands
\newcommand{\Leaf}{\qedsymbol}
%\renewcommand{\baselinestretch}{1.5}

\title[On some parameters in Heap ordered trees]
{On some parameters in Heap ordered trees}

\author[K.~Morris]{Kate Morris}
\address{Kate Morris\\
The John Knopfmacher Centre for Applicable Analysis and Number Theory\\
 School of Mathematics\\
University of the Witwatersrand, P.~O. Wits\\ 
2050 Johannesburg, South Africa}
\email{kate@maths.wits.ac.za}

\author[A.~Panholzer]{Alois Panholzer}
\address{Alois Panholzer\\
Institut f{\"u}r Algebra und Computermathematik\\
TU Wien\\
Wiedner Hauptstr. 8-10\\
1040 Wien, Austria}
\email{Alois.Panholzer@tuwien.ac.at} 
\thanks{ Part of this work was done during the second author's visit to the
John Knopfmacher 
Centre for Applicable Analysis and Number Theory at the University of the
Witwatersrand, Johannesburg, South Africa}

\author[H.~Prodinger]{Helmut Prodinger}
\address{Helmut Prodinger\\
The John Knopfmacher Centre for Applicable Analysis and Number Theory\\
 School of Mathematics\\
University of the Witwatersrand, P.~O. Wits\\ 
2050 Johannesburg, South Africa}
\email{helmut@maths.wits.ac.za}


\date{\today}

\begin{document}
\begin{abstract}
Heap ordered trees are planted plane trees, labelled in such a way that
the labels always increase from the root to a leaf. We study two
parameters, assuming that $p$  of the $n$ nodes are selected at random:
the size of the ancestor tree of these nodes and the smallest subtree generated
by these nodes. We compute expectation, variance, and  also the Gaussian
limit distribution, the latter as an  application of Hwang's quasi power
theorem. 
\end{abstract}

\maketitle

\section{Introduction}
A {\it heap ordered tree} with $n$ nodes (``size $n$'') can be described as a 
{\it planted plane tree} together with a bijection from the nodes to the set 
$\{1,\ldots,n\}$ which is {\it monotonically increasing} when going from the 
root to the leaves. 

\begin{figure}[!h]
\includegraphics[height=8cm]{4nodehots.eps}
\caption{All $15$ heap ordered trees with $4$ nodes.}
\end{figure}

Some recent research papers \cite{Pro96, Pro97} deal with statistics of the
height of the nodes in heap ordered trees.  Now, the height of a given node is 
defined as the number of nodes lying on the unique path from the root to this 
node.  In this paper we consider a simple generalization of the height:
for $p$ given nodes in a heap ordered tree $T$ we consider the size
of the ancestor tree of these selected nodes. To be more precise, the 
ancestor tree is the subtree of $T$ which is spanned by the root and the $p$ 
chosen nodes and hence it is defined as the tree containing all
ascendants of the $p$ given nodes.

Spanning tree size and the Wiener index for binary search trees have
been computed in \cite{MaNe02} and
\cite{PanPro02}.  The {\em Wiener index\/} of a graph is the sum of all
distances between pairs of nodes in the graph. 
 A related parameter of
interest is the \emph{Steiner distance}.  The 
Steiner distance of a graph is the expected distance of two random nodes 
in the graph. So, the Steiner distance is a scaled down version of the 
Wiener index;  in a sense    they  behave roughly like path length versus
(insertion) depth. For expectations, the concepts are equivalent, but not
for higher moments and the limiting distribution. We consider a natural 
generalization: instead of selecting two random nodes and looking at the distance, 
we consider $p$ randomly chosen nodes and look at the size of the subtree
spanned by these nodes. A different generalization of the Steiner distance
can, for example, be found in \cite{DaOeSw96}. 

In this paper we aim to compute the expectation and variance for the
size of the ancestor trees and the Steiner distance in heap ordered
trees.  Also, we will consider the limiting distributions involved.
For the parameters we discuss the distributions turn out to be Gaussian and we will use 
Hwang's \emph{quasi power theorem}, see \cite{Hwang98}, to determine them.  
For the convenience of the reader we include this important
 theorem here.  
\begin{theor}{\rm \textrm{[H.~K. Hwang]}}
Let $\{\Omega_n\}_{n\geq 1}$ be a sequence of integral random variables.  
Suppose that the moment generating function satisfies the asymptotic expression
\begin{equation*}
M_n(s)=\E(e^{\Omega_n s})=\sum\limits_{m\geq 0}\P\{\Omega_n=m\}e^{ms}=e^{H_n(s)}(1+\mathcal{O}(\kappa_n^{-1}))\,,
\end{equation*}
the $\mathcal{O}$-term being uniform for $|s|\leq\tau$, $s\in \mathbb{C}$, $\tau>0$, where

 (i) $H_n=u(s)\phi(n)+v(s)$, with $u(s)$ and $v(s)$ analytic for $|s|\leq\tau$ 
and independent of $n$; $u''(0)\neq 0$,

 (ii) $\phi(n)\rightarrow \infty$,

 (iii) $\kappa_n\rightarrow \infty$.  

Under these assumptions the distribution of $\Omega_n$ is asymptotically Gaussian:
\begin{equation*}
\P\left\{\frac{\Omega_n-u'(0)\phi(n)}{\sqrt{u''(0)\phi(n)}}<x\right\}
=\Phi(x)+\mathcal{O}\bigg(\frac{1}{\kappa_n}+\frac{1}{\sqrt{\phi(n)}}\bigg)\,,
\end{equation*}
uniformly with respect to $x$, $x\in\mathbb{R}$.  Here $\Phi(x)$ denotes the 
distribution function of the standard normal distribution $\mathcal{N}(0,1)$.  
Moreover, the mean and variance of $\Omega_n$ satisfy
\begin{equation*}
\E(\Omega_n)=u'(0)\phi(n)+v'(0)+\mathcal{O}(\kappa_n^{-1}),\quad \V(\Omega_n)=u''(0)\phi(n)+v''(0)+
\mathcal{O}(\kappa_n^{-1})\,. \qed
\end{equation*}
\end{theor}
(We will use the letters $u$ and $v$ also in a different context in the paper, 
but there is no chance of confusion.)

For fixed $p$ and $n\to\infty$, the expected value of both, the ancestor
tree, and the Steiner distance, are asymptotic to $\frac p2\log n$, the
difference being in the smaller order terms. To apply the quasi power theorem, 
an inductive process (w.\;r.\;t. $p$) is used. Part of the difficulty is
that a certain trivariate generating function is only implicitly given, 
and sufficient information must be ``pumped out'' of this
implicit equation. 



\section{Size of the ancestor tree\label{sec1}}

For a given tree family let $X_{n,p}$ denote the random variable that counts 
the size of the ancestor tree
of $p$ randomly chosen nodes in a tree of size $n$ and
$T_{n}$ the number of trees of size $n$.

\begin{figure}[!h]
\includegraphics[height=5cm]{hots.eps}
\caption{A heap ordered tree of size $10$ with the two parameters under consideration;  nodes 
$7$ and $10$ are labelled.}
\end{figure}

A simple family of increasing trees (which includes heap 
ordered trees) is defined by labelled rooted trees in which labels along any 
branch from the root go in increasing order, see \cite{bfs}.  
For this type of problem, it is natural to consider exponential generating
functions. In this
case one gets, by introducing the generating functions
\begin{align*}
   T(z)  = \sum_{n \ge 0} \frac{T_{n}}{n!} z^{n} \qquad \text{and} \qquad  
G(z,u,v)  = \sum_{n \ge 0, p \ge 0, m \ge 0} \P\left\{X_{n,p}=m\right\} T_{n}
\binom{n}{p} \frac{z^{n}}{n!} u^{p} v^{m}\,
\end{align*}
the equations
\begin{align}
   T'(z)  = \varphi(T(z)) \qquad \text{and} \qquad  \frac{\partial}{\partial z}G(z,u,v) & = 
   v(1+u) \varphi(G(z,u,v)) + (1-v) \varphi(T(z)),
   \label{Gz}
\end{align}
with initial values $T(0)=0$ and $G(0,u,v)=0$.  
The first term in (\ref{Gz}) 
takes care of the instance where the root is labelled
 and the second term accounts for a non--labelled root.  
Here the \emph{degree generating function\/} 
$\varphi(t)=\sum_{n \ge 0} \varphi_{n} t^{n}$ satisfies  
$\varphi_{i} \ge 0$ for $i \ge 1$ and $\varphi_{0}>0$. This function
is responsible for the recursive generation of these trees.
However, here, we are only concerned with the case where each degree can
occur with weight one, i.\;e., with heap ordered trees.
We plan to treat the general case in a future publication.

Thus, we have $\varphi(t) = \frac{1}{1-t}$, and we obtain the differential equation
$T'(z) = \frac{1}{1-T(z)}$, $T(0)=0$, which gives the well-known formula 
\begin{equation*}
   T(z) = 1-\sqrt{1-2z}
\end{equation*}
for the exponential generating function $T(z)$.  By extracting coefficients we obtain the number of heap ordered trees,
\begin{equation*}
   T_{n} = \prod_{k=1}^{n-1} (2k-1) = \frac{(n-1)!}{2^{n-1}}\binom{2n-2}{n-1}.
\end{equation*}

The differential equation of interest for $G(z,u,v)$ in the case of heap ordered trees 
is thus 
\begin{equation*}
   \frac{\partial}{\partial z}G(z,u,v) = \frac{v(1+u)}{1-G(z,u,v)} + \frac{1-v}{\sqrt{1-2z}}, \quad G(0,u,v)=0,\quad G(z,u,1)=1-\sqrt{1-2z(1+u)}\,.
\end{equation*}

It turns out that it is advantageous to make the substitution
\begin{equation*}
H(z,u,v) = \frac{1-G(z,u,v)}{\sqrt{1-2z}}. 
\end{equation*}
Then the differential equation becomes
\begin{equation*}
   H(z,u,v) - \frac{v(1+u)}{H(z,u,v)} - 1 + v = (1-2z) \frac{\partial}{\partial z}H(z,u,v), \quad H(0,u,v)=1.
\end{equation*}
Using separation of variables we get the implicit solution
\begin{equation*}
   \frac{1}{2} \log\frac{1}{1-2z} = 
   \int_{x=1}^{H(z,u,v)} \frac{x dx}{x^{2}-(1-v)x - v(1+u)}\,,
\end{equation*}
and by integration we obtain
\begin{align}
   \log\frac{1}{1-2z} & = 
\log\left(1-\frac{(H(z,u,v)-1)(H(z,u,v)+v)}{v u}\right) \notag \\
& \quad \mbox{} -\frac{1-v}{\sqrt{4vu+(1+v)^{2}}} \log\left(1+\frac{2(H(z,u,v)-1)}{\sqrt{4vu+(1+v)^{2}}+2-(1-v)}\right) \label{eqn1} \\
& \quad \mbox{} +\frac{1-v}{\sqrt{4vu+(1+v)^{2}}} \log\left(1-\frac{2(H(z,u,v)-1)}{\sqrt{4vu+(1+v)^{2}}+(1-v)-2}\right). \notag
\end{align}
Now we replace $H(z,u,v)$ with $\frac{1-G(z,u,v)}{\sqrt{1-2z}}$ in (\ref{eqn1}) 
and differentiate with respect to $v$. In the resulting equation we let $v=1$ and solve 
for $\frac{\partial}{\partial v}G(z,u,v)\big\vert_{v=1}$. We obtain
\begin{equation}
\begin{split}
\frac{\partial}{\partial v}G(z,u,v)\Big\vert_{v=1}=&\frac{1}{2}\sqrt {1-2z}-\frac{1}{2}\sqrt {1-2z(1+u)}\\
&-\frac{1}{4}\frac {u\left(\log(2+u-4z(1+u)+2\sqrt {(1-2z(1+u))(1-2z)(1+u)}\right)}{\sqrt{(1+u)(1-2z(1+u))}}\\
&-\frac{1}{4}\frac{2u\log (1+\sqrt {1+u}\,)}{\sqrt {(1+u)(1-2z(1+u))}}\,.
\end{split}
\label{G}
\end{equation}
 From (\ref{G}) we can as well find
$\frac{\partial^2}{\partial z\partial v}G(z,u,v)\big\vert_{v=1}$ which will be 
used in Section 3 to compute the expectation for the Steiner distance, see (\ref{Fv}). 
We differentiate equation (\ref{eqn1}) to get
\begin{equation*}
\begin{split}
&\frac{\partial^2}{\partial z\partial v}G(z,u,v)\Big\vert_{v=1}\\
=&-\frac{1}{2\sqrt{1-2z}}-\frac{1+u}{2\sqrt{1-2z(1+u)}}\\
&+\bigg(4(1+u)-\frac{2(1+u)(1-2z)(1+u)+2(1-2z(1+u))(1+u)}{\sqrt{(1-2z(1+u))(1-2z)(1+u)}}\bigg)\\
&\times \frac{u}{4(2+u-4z(1+u))\sqrt{(1-2z(1+u))(1+u)}+8(1-2z(1+u))(1+u)\sqrt{1-2z}}\\
&-\bigg(\log\big(2+u-4z(1+u)+2\sqrt{(1-2z(1+u))(1-2z)(1+u)}\,\,\big)\\
&-\log(2+u+2\sqrt{1+u}\,)\bigg)\frac{u\sqrt{1+u}}{4(1-2z(1+u))^{3/2}}\,.
\end{split}
\end{equation*}


Next we consider the (formal) expansions
\begin{equation*}
G(z,u,v) = \sum_{p \ge 0} G_{p}(z,v) u^{p} \quad \text{resp.} \quad 
H(z,u,v) = \sum_{p \ge 0} H_{p}(z,v) u^{p}, 
\end{equation*}
where our aim is to describe the limiting behaviour
of $[z^{n}] G_{p}(z,v)$ uniformly in a neighbourhood of $v=1$ and then apply a central limit theorem
(Hwang's quasi power theorem)
to find the Gaussian limiting distribution of $X_{n,p}$ for fixed $p \ge 1$.

Obviously we have $G_{p}(z,v) = \sum_{n \ge 0, m \ge 0} \P\left\{X_{n,p}=m\right\} T_{n}
\binom{n}{p} \frac{z^{n}}{n!} v^{m}$ and $H_{p}(z,v) = - \frac{G_{p}(z,v)}{\sqrt{1-2z}}$
for $p \ge 1$ and $H_{0}(z,v)=\frac{1-G_{0}(z,v)}{\sqrt{1-2z}}$.
Since $\P\left\{X_{n,0}=m\right\}=\delta_{m,n}$, we get immediately 
$G_{0}(z,v)=T(z)=1-\sqrt{1-2z}$ and $H_{0}(z,v)=1$.

The required expansion for $p \ge 1$ is stated as the following lemma.
\begin{lemma}
   \label{lem1}
   The coefficients $H_{p}(z,v)$ have for $p \ge 1$ around their (only) dominant singularity $z=\frac{1}{2}$ 
   uniformly for $|v-1|\le \varepsilon$ and $\varepsilon > 0$ the expansion
   \begin{equation*}
      H_{p}(z,v) = h_{p}(v) \frac{1}{(1-2z)^{\frac{p(v+1)}{2}}} + 
      \mathcal{O}\left(\frac{\log(1-2z)}{(1-2z)^{\frac{(p-1)(v+1)}{2}}}\right).
   \end{equation*}
   The coefficient generating function $C(v,x) = \sum_{p \ge 1} h_{p}(v) x^{p}$ of the
   $h_{p}(v)$ is given implicitly by the equation
   \begin{equation*}
      \frac{C(v,x)(1+v+C(v,x))}{vx} = - \left(\frac{1+\frac{C(v,x)}{1+v}}
      {-\frac{1+v}{v}\frac{C(v,x)}{x}}\right)^{\frac{1-v}{1+v}}
   \end{equation*}
   and it holds for
   \begin{equation*}
      h_{p}(1) = [x^{p}] C(1,x) = -\frac{2}{4^{p} p} \binom{2(p-1)}{p-1},
   \end{equation*}
   where $C(1,x)=-1+\sqrt{1-x}$ and $C_{v}(1,x) = \frac{C(1,x)}{2} + \frac{x}{4} \frac{1}{1+C(1,x)}
   \log\left(\frac{1+\frac{C(1,x)}{2}}{-2\frac{C(1,x)}{x}}\right)$.
   Thus the expansion for the $G_{p}(z,v)$ for $p \ge 1$ is given by
   \begin{equation}
      G_{p}(z,v) = -h_{p}(v) \frac{1}{(1-2z)^{\frac{p(v+1)-1}{2}}} + 
      \mathcal{O}\left(\frac{\log(1-2z)}{(1-2z)^{\frac{(p-1)(v+1)-1}{2}}}\right).
      \label{Gp}
   \end{equation}
\end{lemma}
\begin{proof}
To obtain $H_{1}(z,v)$ and thus $G_{1}(z,v)$ we consider \eqref{eqn1} and compare coefficients
at $u^{0}$.
We get 
\begin{align*}
   & [u^{0}] \log\left(1-\frac{(H(z,u,v)-1)(H(z,u,v)+v)}{v u}\right) \\
   & = [u^{0}] \log\left(1-\frac{(H_{1}(z,v) u + \mathcal{O}(u^{2})) (1+v+\mathcal{O}(u))}{vu}\right)
   = \log\left(1-\frac{1+v}{v}H_{1}(z,v)\right), \\
   & [u^{0}] \frac{1-v}{\sqrt{4vu+(1+v)^{2}}} \log\left(1+\frac{2(H(z,u,v)-1)}{\sqrt{4vu+(1+v)^{2}}+2-(1-v)}\right) \\
   & = [u^{0}] \frac{1-v}{1+v} \frac{1}{\sqrt{1+\frac{4v}{(1+v)^{2}}u}} 
   \log\left(1+\frac{2(H_{1}(z,v)u+\mathcal{O}(u^{2}))}{(1+v)\sqrt{1+\frac{4v}{(1+v)^{2}}u}+1+v}\right) \\
   & = [u^{0}] \frac{1-v}{1+v} (1+\mathcal{O}(u)) \log(1+\mathcal{O}(u)) = 0, \\
   & [u^{0}] \frac{1-v}{\sqrt{4vu+(1+v)^{2}}} \log\left(1-\frac{2(H(z,u,v)-1)}{\sqrt{4vu+(1+v)^{2}}+(1-v)-2}\right) \\
   & = [u^{0}] \frac{1-v}{1+v} (1+\mathcal{O}(u)) 
   \log\left(1-\frac{2(H_{1}(z,v)u+\mathcal{O}(u^{2}))}{(1+v)\sqrt{1+\frac{4v}{(1+v)^{2}}u}-1-v}\right) \\
   & = [u^{0}] \frac{1-v}{1+v} (1+\mathcal{O}(u)) \log(1-\frac{1+v}{v}H_{1}(z,v)+\mathcal{O}(u))
   = \frac{1-v}{1+v} \log\left(1-\frac{1+v}{v}H_{1}(z,v)\right),
\end{align*}
and further
\begin{equation*}
   \log\left(\frac{1}{1-2z}\right) = \frac{2}{1+v}\log\left(1-\frac{1+v}{v}H_{1}(z,v)\right),
\end{equation*}
which gives 
\begin{equation*}
   H_{1}(z,v) = \frac{v}{1+v} \left(1-\frac{1}{(1-2z)^{\frac{v+1}{2}}}\right) \;\;
   \text{and} \;\;
   G_{1}(z,v) = \frac{\sqrt{1-2z} \, v}{1+v} \left(\frac{1}{(1-2z)^{\frac{v+1}{2}}}-1\right).
\end{equation*}
Therefore the asymptotic expansion given above holds for $p=1$ (although the bound for the 
remainder term is not tight here) with $h_{1}(v) = -\frac{v}{1+v}$ and thus the stated formula
for $h_{p}(1)$ is also valid for $p=1$.

Now we assume that the lemma for $H_{l}(z,v)$ resp. $G_{l}(z,v)$ is true for all $1 \le l \le p$ 
and we will show that it then also holds for $p+1$. To prove the result for $H_{p+1}(z,v)$,
we will consider the coefficients of $u^{p}$ in the equation \eqref{eqn1}.

For the first term in \eqref{eqn1}, we use the expansion
\begin{equation*}
   \log\left(1-\frac{(H(z,u,v)-1)(H(z,u,v)+v)}{v u}\right) =
   \log\left(1-\frac{1+v}{v} H_{1}(z,v)\right) + \log\left(1-\widetilde{H}(z,u,v)\right),
\end{equation*}
with
\begin{equation*}
\begin{split}
   \widetilde{H}(z,u,v)& = \sum_{l \ge 1} \widetilde{H}_{l}(z,v) u^{l}\\& =
   \frac{1}{1-\frac{1+v}{v}H_{1}(z,v)} \left(\frac{(H(z,u,v)-1)(H(z,u,v)+v)}{v u}
   -\frac{1+v}{v}H_{1}(z,v)\right).
   \end{split}
\end{equation*}
We get then
\begin{align*}
   & [u^{p}] \log\left(1-\frac{(H(z,u,v)-1)(H(z,u,v)+v)}{v u}\right) =
   -\sum_{j=1}^{p} \frac{1}{j} \sum_{\substack{p_{1}+\dots+p_{j}=p\\ p_{i} \ge 1}}\
   \prod_{i=1}^{j} \widetilde{H}_{p_{i}}(z,v) \\
   & = - \frac{\frac{1+v}{v}H_{p+1}(z,v)}{1-\frac{1+v}{v}H_{1}(z,v)} 
   - \frac{\frac{1}{v}\sum_{k=1}^{p} H_{k}(z,v) H_{p+1-k}(z,v)}{1-\frac{1+v}{v}H_{1}(z,v)}
   - \sum_{j=2}^{p} \frac{1}{j} \sum_{\substack{p_{1}+\dots+p_{j}=p\\ p_{i} \ge 1}}\
   \prod_{i=1}^{j} \widetilde{H}_{p_{i}}(z,v),
\end{align*}
where
\begin{equation*}
   \widetilde{H}_{l}(z,v) = \frac{1}{1-\frac{1+v}{v}H_{1}(z,v)} \frac{1}{v}
   \left((1+v) H_{l+1}(z,v) + \sum_{k=1}^{l} H_{k}(z,v) H_{l+1-k}(z,v)\right).
\end{equation*}

Under the assumptions of the lemma we now obtain, for $1 \le l \le p-1$, 
around the dominant singularity $z=\frac{1}{2}$ in a neighbourhood of $v=1$, the uniform expansion
\begin{align*}
   \widetilde{H}_{l}(z,v) & = (1-2z)^{\frac{v+1}{2}} \left(\frac{\frac{1+v}{v}h_{l+1}(v)}
   {(1-2z)^{\frac{(l+1)(v+1)}{2}}}+\frac{\frac{1}{v}\sum_{k=1}^{l}h_{k}(v) h_{l+1-k}(v)}
   {(1-2z)^{\frac{(l+1)(v+1)}{2}}}+\mathcal{O}\left(\frac{\log(1-2z)}
   {(1-2z)^{\frac{l(v+1)}{2}}}\right)\right)\\
   & = \widetilde{h}_{l}(v) \frac{1}{(1-2z)^{\frac{l(v+1)}{2}}} 
   + \mathcal{O}\left(\frac{\log(1-2z)}{(1-2z)^{\frac{(l-1)(v+1)}{2}}}\right),
\end{align*}
where
\begin{align*}
   \widetilde{h}_{l}(v) = \frac{1}{v} \left((1+v)h_{l+1}(v) + \sum_{k=1}^{l} 
   h_{k}(v) h_{l+1-k}(v)\right).
\end{align*}

With the abbreviations
\begin{align*}
   & \widehat{H}(z,u,v) = \sum_{l \ge 1} \widehat{H}_{l}(z,v) u^{l} =
   \frac{2(H(z,u,v)-1)}{\sqrt{4vu+(1+v)^{2}}+2-(1-v)}, \\
   & \widehat{a}_{l}(v) = [u^{l}] \frac{1}{\sqrt{1+\frac{4v}{(1+v)^{2}}u}}, \quad
   \widehat{b}_{l}(v) = [u^{l}] \frac{2}{\sqrt{4vu+(1+v)^{2}}+2-(1-v)},
\end{align*}
we get for the coefficients of the second term in \eqref{eqn1} the expansion
\begin{align*}
   & [u^{p}] \frac{1-v}{\sqrt{4vu+(1+v)^{2}}} \log\left(1+\frac{2(H(z,u,v)-1)}{\sqrt{4vu+(1+v)^{2}}+2-(1-v)}\right) \\
   & = \frac{1-v}{1+v} \sum_{k=1}^{p} \widehat{a}_{p-k}(v) 
   \sum_{j=1}^{k} \frac{(-1)^{j+1}}{j} 
\sum_{\substack{k_{1}+\dots+k_{j}=k\\ k_{i} \ge 1}}\
   \prod_{i=1}^{j} \widehat{H}_{k_{i}}(z,v)\\
   & = \frac{1-v}{1+v} \sum_{j=1}^{p} \frac{(-1)^{j+1}}{j} 
\sum_{\substack{p_{1}+\dots+p_{j}=p\\ p_{i} \ge 1}}\
   \prod_{i=1}^{j} \widehat{H}_{p_{i}}(z,v) \\
   & \quad \mbox{} +
   \frac{1-v}{1+v} \sum_{k=1}^{p-1} \widehat{a}_{p-k}(v) 
   \sum_{j=1}^{k} \frac{(-1)^{j+1}}{j} \sum_{\substack{k_{1}+\dots+k_{j}=k\\ k_{i} \ge 1}}\
   \prod_{i=1}^{j} \widehat{H}_{k_{i}}(z,v),
\end{align*}
where
\begin{equation*}
   \widehat{H}_{l}(z,v) = \sum_{k=1}^{l} H_{k}(z,v) \widehat{b}_{l-k}(v).
\end{equation*}

Under the assumptions of the lemma we obtain, for $1 \le l \le p$, the uniform expansion
\begin{align*}
   \widehat{H}_{l}(z,v) & = \sum_{k=1}^{l} \left(\frac{h_{k}(v)}
   {(1-2z)^{\frac{k(v+1)}{2}}}+\mathcal{O}\left(\frac{\log(1-2z)}
   {(1-2z)^{\frac{(k-1)(v+1)}{2}}}\right)\right) \widehat{b}_{l-k}(v)\\
   & = \widehat{h}_{l}(v) \frac{1}{(1-2z)^{\frac{l(v+1)}{2}}} 
   + \mathcal{O}\left(\frac{\log(1-2z)}{(1-2z)^{\frac{(l-1)(v+1)}{2}}}\right),
\end{align*}
where
\begin{align*}
   \widehat{h}_{l}(v) = \frac{1}{1+v} h_{l}(v).
\end{align*}

Finally for the third term in \eqref{eqn1} we use the expansion
\begin{align*}
   & \frac{1-v}{\sqrt{4vu+(1+v)^{2}}} \log\left(1-\frac{2(H(z,u,v)-1)}{\sqrt{4vu+(1+v)^{2}}+(1-v)-2}\right) \\
   & = \frac{1-v}{\sqrt{4vu+(1+v)^{2}}} \log\left(1-\frac{1+v}{v} H_{1}(z,v)\right) 
   + \frac{1-v}{\sqrt{4vu+(1+v)^{2}}} \log\left(1-\overline{H}(z,u,v)\right),
\end{align*}
with
\begin{align*}
   \overline{H}(z,u,v) &= \sum_{l \ge 1} \overline{H}_{l}(z,v) u^{l} \\&=
   \frac{1}{1-\frac{1+v}{v}H_{1}(z,v)} \left(\frac{2(H(z,u,v)-1)}{\sqrt{4vu+(1+v)^{2}}+(1-v)-2}
   -\frac{1+v}{v}H_{1}(z,v)\right).
\end{align*}
Further we use the abbreviations
\begin{equation*}
   \overline{a}_{l}(v) = [u^{l}] \frac{1}{\sqrt{1+\frac{4v}{(1+v)^{2}}u}}, \quad
   \overline{b}_{l}(v) = [u^{l}] \frac{2u}{\sqrt{4vu+(1+v)^{2}}+(1-v)-2}.
\end{equation*}

We get the expansion
\begin{align*}
   & [u^{p}] \frac{1-v}{\sqrt{4vu+(1+v)^{2}}} \log\left(1-\frac{2(H(z,u,v)-1)}{\sqrt{4vu+(1+v)^{2}}+(1-v)-2}\right) \\
   & = \frac{1-v}{1+v} \overline{a}_{p}(v) \log\left(1-\frac{1+v}{v} H_{1}(z,v)\right) 
   - \frac{1-v}{1+v} \sum_{k=1}^{p} \overline{a}_{p-k}(v) 
   \sum_{j=1}^{k} \frac{(-1)^{j+1}}{j} 
\sum_{\substack{k_{1}+\dots+k_{j}=k\\ k_{i} \ge 1}}\
   \prod_{i=1}^{j} \overline{H}_{k_{i}}(z,v)\\
   & = \frac{1-v}{1+v} \overline{a}_{p}(v) \log\left(1-\frac{1+v}{v} H_{1}(z,v)\right) 
   - \frac{1-v}{1+v} \frac{\frac{1+v}{v} H_{p+1}(z,v)}{1-\frac{1+v}{v}H_{1}(z,v)}
   - \frac{1-v}{1+v} \frac{\sum_{k=0}^{p-1}H_{k+1}(z,v) \overline{b}_{p-k}(v)}{1-\frac{1+v}{v}H_{1}(z,v)} \\
   & \quad \mbox{} - \frac{1-v}{1+v} \sum_{j=2}^{p} \frac{1}{j} 
\sum_{\substack{p_{1}+\dots+p_{j}=p\\ p_{i} \ge 1}}\
   \prod_{i=1}^{j} \overline{H}_{p_{i}}(z,v) 
   - \frac{1-v}{1+v} \sum_{k=1}^{p-1} \overline{a}_{p-k}(v) 
   \sum_{j=1}^{k} \frac{1}{j} \sum_{\substack{k_{1}+\dots+k_{j}=k\\ k_{i} \ge 1}}\
   \prod_{i=1}^{j} \overline{H}_{k_{i}}(z,v),
\end{align*}
where
\begin{equation*}
   \overline{H}_{l}(z,v) = \frac{1}{1-\frac{1+v}{v}H_{1}(z,v)} 
   \sum_{k=0}^{l} H_{k+1}(z,v) \overline{b}_{l-k}(v).
\end{equation*}

Now, under the assumptions of the lemma, we obtain, for $1 \le l \le p-1$, the uniform expansion
\begin{align*}
   \overline{H}_{l}(z,v) & = (1-2z)^{\frac{v+1}{2}} \sum_{k=0}^{l} \left(\frac{h_{k+1}(v)}
   {(1-2z)^{\frac{(k+1)(v+1)}{2}}}+\mathcal{O}\left(\frac{\log(1-2z)}
   {(1-2z)^{\frac{k(v+1)}{2}}}\right)\right) \overline{b}_{l-k}(v)\\
   & = \overline{h}_{l}(v) \frac{1}{(1-2z)^{\frac{l(v+1)}{2}}} 
   + \mathcal{O}\left(\frac{\log(1-2z)}{(1-2z)^{\frac{(l-1)(v+1)}{2}}}\right),
\end{align*}
where
\begin{align*}
   \overline{h}_{l}(v) = \frac{1+v}{v} h_{l+1}(v).
\end{align*}

Comparing coefficients leads to the following equation for $H_{p+1}(z,v)$:
\begin{align*}
   & \frac{2}{v} \frac{1}{1-\frac{1+v}{v}H_{1}(z,v)} H_{p+1}(z,v) = \\*
   & \quad - \frac{\frac{1}{v}\sum_{k=1}^{p} H_{k}(z,v) H_{p+1-k}(z,v)}{1-\frac{1+v}{v}H_{1}(z,v)}
   - \sum_{j=2}^{p} \frac{1}{j} 
\sum_{\substack{p_{1}+\dots+p_{j}=p\\ p_{i} \ge 1}}\
   \prod_{i=1}^{j} \widetilde{H}_{p_{i}}(z,v) \\
   & \quad \mbox{} - \frac{1-v}{1+v} \sum_{j=1}^{p} \frac{(-1)^{j+1}}{j} 
\sum_{\substack{p_{1}+\dots+p_{j}=p\\ p_{i} \ge 1}}\
   \prod_{i=1}^{j} \widehat{H}_{p_{i}}(z,v) \\
   & \quad \mbox{} - \frac{1-v}{1+v} \sum_{k=1}^{p-1} \widehat{a}_{p-k}(v) 
   \sum_{j=1}^{k} \frac{(-1)^{j+1}}{j} \sum_{\substack{k_{1}+\dots+k_{j}=k\\ k_{i} \ge 1}}\
   \prod_{i=1}^{j} \widehat{H}_{k_{i}}(z,v) \\
   & \quad \mbox{} + \frac{1-v}{1+v} \overline{a}_{p}(v) \log\left(1-\frac{1+v}{v} H_{1}(z,v)\right) 
   - \frac{1-v}{1+v} \frac{\sum_{k=0}^{p-1}H_{k+1}(z,v) \overline{b}_{p-k}(v)}{1-\frac{1+v}{v}H_{1}(z,v)} \\
   & \quad \mbox{} - \frac{1-v}{1+v} \sum_{j=2}^{p} \frac{1}{j} 
\sum_{\substack{p_{1}+\dots+p_{j}=p\\ p_{i} \ge 1}}\
   \prod_{i=1}^{j} \overline{H}_{p_{i}}(z,v) \\
   & \quad \mbox{} - \frac{1-v}{1+v} \sum_{k=1}^{p-1} \overline{a}_{p-k}(v) 
   \sum_{j=1}^{k} \frac{1}{j} \sum_{\substack{k_{1}+\dots+k_{j}=k\\ k_{i} \ge 1}}\
   \prod_{i=1}^{j} \overline{H}_{k_{i}}(z,v).
\end{align*}

The asymptotic expansion
\begin{equation}
   H_{p+1}(z,v) = h_{p+1}(v) \frac{1}{(1-2z)^{\frac{(p+1)(v+1)}{2}}} + 
   \mathcal{O}\left(\frac{\log(1-2z)}{(1-2z)^{\frac{p(v+1)}{2}}}\right),
\end{equation}
follows by inspection, where
\begin{equation}
   \begin{split}
   & h_{p+1}(v) = \frac{v}{2} \Bigg[ -\frac{1}{v} \sum_{k=1}^{p} h_{k}(v) h_{p+1-k}(v)
   - \sum_{j=2}^{p} \frac{1}{j} 
\sum_{\substack{p_{1}+\dots+p_{j}=p\\ p_{i} \ge 1}}\
   \prod_{i=1}^{j} \widetilde{h}_{p_{i}}(v)  \\
   &  \qquad \mbox{} - \frac{1-v}{1+v} 
   \sum_{j=1}^{p} \frac{(-1)^{j+1}}{j} \sum_{\substack{p_{1}+\dots+p_{j}=p\\ p_{i} \ge 1}}\
   \prod_{i=1}^{j} \widehat{h}_{p_{i}}(v) - \frac{1-v}{1+v} 
   \sum_{j=2}^{p} \frac{1}{j} \sum_{\substack{p_{1}+\dots+p_{j}=p\\ p_{i} \ge 1}}\
   \prod_{i=1}^{j} \overline{h}_{p_{i}}(v)
   \Bigg],
   \end{split} \label{eqn2}
\end{equation}
and this part of the lemma is proven.  
The expansion of $G_{p}(z,v)$ given in (\ref{Gp}) follows immediately. 
It should be remarked, that  this detailed description of
$H_{p+1}(z,v)$ shown inductively shows as well that 
the assumptions necessary for the
application of singularity analysis are satisfied. 
The logarithmic remainder term appears for $p=2$ due to
$\log\left(1-\frac{1+v}{v} H_{1}(z,v)\right)=-\frac{v+1}{2} \log(1-2z)$ and thus also
for $p \ge 2$.

To get an equation for the coefficient generating function 
$C(v,x) = \sum_{p \ge 1} h_{p}(v) x^{p}$ one could of course use equation \eqref{eqn2},
but it follows much easier directly from \eqref{eqn1}, when considering which 
terms give contributions to the main term of $H_{p}(z,v)$. Then one gets
\begin{align*}
   & \log\left(1-\frac{\frac{C(v,x)}{x}(1+v+C(v,x))-(v+1)h_{1}(v)}{v}\right) \\
   & \mbox{} - \frac{1-v}{1+v} \log\left(1+\frac{C(v,x)}{1+v}\right)
   + \frac{1-v}{1+v} \log\left(1-\frac{1+v}{v}\left(\frac{C(v,x)}{x}-h_{1}(v)\right)\right) = 0,
\end{align*}
or
\begin{equation}
   \frac{C(v,x)(1+v+C(v,x))}{vx} = - \left(\frac{1+\frac{C(v,x)}{1+v}}
   {-\frac{1+v}{v}\frac{C(v,x)}{x}}\right)^{\frac{1-v}{1+v}}.
   \label{Cvx}
\end{equation}

We easily obtain from (\ref{Cvx}) the equation $\frac{C(1,x) (2+C(1,x))}{x} = -1$, which gives
   \begin{equation*}
   C(1,x) = -1 + \sqrt{1-x}\quad \text{and}
   \end{equation*}
\begin{equation}
   h_{p}(1) = [x^{p}] C(1,x) = - \frac{2}{4^{p} p} \binom{2(p-1)}{p-1}, \quad \text{for}
   \; p \ge 1.
   \label{h}
\end{equation}
This completes the proof of the lemma.
\end{proof}

Using singularity analysis, we get immediately from the above lemma the following expansion,
which is uniform for $|v-1| \le \varepsilon$ and $\varepsilon > 0$,
\begin{align*}
    \sum_{m \ge 0} \P\left\{X_{n,p}=m\right\} v^{m} &= \frac{n!}{\binom{n}{p} T_{n}}
   [z^{n}] G_{p}(z,v)\\ 
   &=-\frac{p! h_{p}(v) 2 \sqrt{\pi}}{\Gamma\left(\frac{p(v+1)-1}{2}\right)} n^{\frac{p(v-1)}{2}}
   \Big(1+\mathcal{O}\Big(\frac{1}{n^{1-\varepsilon}}\Big)\Big) \\
   & = \exp \left[\frac{p(v-1)}{2} \log n + \log\Bigg(\frac{-2\sqrt{\pi} p! h_{p}(v)}
   {\Gamma\big(\frac{p(v+1)-1}{2}\big)}\Bigg)\right]
   \Big(1+\mathcal{O}\Big(\frac{1}{n^{1-\varepsilon}}\Big)\Big),
\end{align*}
where we used the asymptotic expansion for the number $T_{n}$ of heap ordered trees
\begin{equation*}
   T_{n} = \frac{n! 2^{n-1} n^{-\frac{3}{2}}}{\sqrt{\pi}} 
   \Big(1+\mathcal{O}\Big(\frac{1}{n}\Big)\Big).
\end{equation*}

With the notations of the quasi power theorem, we get
\begin{equation*}
   u(s) = \frac{p(e^{s}-1)}{2} \qquad \text{and} \qquad 
   v(s) = \log\Bigg(\frac{-2\sqrt{\pi} p! h_{p}(e^{s})}
{\Gamma\big(\frac{p(e^{s}+1)-1}{2}\big)}
\Bigg).
\end{equation*}

To apply the quasi power theorem, we need $v(s)$ to be analytic around $s=0$,
which is true, since $h_{p}(1) = -\frac{2}{4^{p} p} \binom{2(p-1)}{p-1} \neq 0$.

We have further
\begin{equation*}
   u'(s)=\frac{p}{2} e^{s}, \quad u''(s)=\frac{p}{2} e^{s}, \qquad \text{thus} \qquad
   u'(0)=\frac{p}{2}, \quad u''(0)=\frac{p}{2}.
\end{equation*}

Therefore we get the following theorem:
\begin{theorem}
   The distribution of the random variable $X_{n,p}$, which counts the size of the ancestor tree
   of $p$ randomly chosen nodes in a random heap ordered tree of size $n$
   is for $p \ge 1$ asymptotically Gaussian, where the convergence rate is of order
   $\mathcal{O}\left(\frac{1}{\sqrt{\log n}}\right)$:
   \begin{equation*}
      \P\Bigg\{\frac{X_{n,p}-\frac{p}{2} \log n}{\sqrt{\frac{p}{2}\log n}} < x\Bigg\}
      = \Phi(x) + \mathcal{O}\left(\frac{1}{\sqrt{\log n}}\right),
   \end{equation*}
   and the expectation $E_{n,p} = \E(X_{n,p})$ and the variance $V_{n,p} = \V(X_{n,p})$
   satisfy
   \begin{align*}
      E_{n,p} = \frac{p}{2} \log n + v'(0) + \mathcal{O}\left(\frac{1}{n^{1-\varepsilon}}\right), \\
      V_{n,p} = \frac{p}{2} \log n + v''(0) + \mathcal{O}\left(\frac{1}{n^{1-\varepsilon}}\right).
   \end{align*}\qed
\end{theorem}

%\bigskip

\textbf{Remark.} By inspection we can get the following expansions
\begin{equation*}
\begin{split}
[u^p]\frac{\partial}{\partial 
v}G(z,u,v)\Big\vert_{v=1}&=\sum\limits_{i=1}^p(-1)^{p+i}(p-1)^{\underline{i-1}}
\,\,\frac{(2i-2)!}{(i-1)!\,4^i}\,\frac{1}{(1-2z)^{i-1/2}}\;\log\frac{1}{1-2z}\\
&+\sum\limits_{i=0}^{p-1}b_i(p)\frac{1}{(1-2z)^{p-i-1/2}}.
\end{split}
\end{equation*}

The computation of the $b_i(p)$'s is cumbersome as they become increasingly 
involved.   However, we were able to obtain $b_1(p)$ and $b_2(p)$ explicitly:
\begin{equation*}
\begin{split}
b_1(p)&=2^{-2p-1}{2p\choose p}\left(H_{2p}-H_p\right)\,,\\
b_2(p)&=-H_{2p-1}\bigg(2^{2p-3}+\frac12{2p-2\choose p}+{2p-2\choose p-1}\bigg)
+\sum\limits_{k=0}^p(p+1-k){2p-2\choose k}H_{2p-1-k}\,.
\end{split}
\end{equation*}\qed

The constant $v'(0)$ in the expectation can also be computed.
One gets
\begin{equation*}
   v'(s) = \frac{h_{p}'(e^{s})e^s}{h_{p}(e^{s})} - \frac{p}{2} e^{s} \Psi\left(\frac{p(e^{s}+1)-1}{2}\right),
   \quad \text{thus} \quad v'(0) = \frac{h_{p}'(1)}{h_{p}(1)}
   - \frac{p}{2} \Psi\left(\frac{2p-1}{2}\right).
\end{equation*}

Here $\Psi(x)$ denotes the digamma function $\Psi(x)=(\log\Gamma(x))'$.  For 
properties of this function we refer the reader to \cite{as}.  There remains the calculation of $h_{p}'(1) = [x^{p}] C_{v}(1,x)$. 
One gets the equation
\begin{equation}
\begin{split}
   C_{v}(1,x) & = \frac{C(1,x)}{2} +  \frac{x}{4(1+C(1,x))}
   \log\left(\frac{1+\frac{C(1,x)}{2}}{-2\frac{C(1,x)}{x}}\right)\\
   & = \frac{\sqrt{1-x}-1}{2} + \frac{x}{4\sqrt{1-x}} \log\left(\frac{1+\frac{\sqrt{1-x}-1}{2}}
   {-2\frac{\sqrt{1-x}-1}{x}}\right).
\end{split}
\label{c_v}
\end{equation}
To extract coefficients, we consider
\begin{align*}
   [x^{p}] \log\left(\frac{1+\frac{\sqrt{1-x}-1}{2}}
   {-2\frac{\sqrt{1-x}-1}{x}}\right) & = 
   \frac{1}{p} [x^{p-1}] \left[\log\left(\frac{1+\frac{\sqrt{1-x}-1}{2}}
   {-2\frac{\sqrt{1-x}-1}{x}}\right)\right]' \\
   & = \frac{1}{p} [x^{p-1}] \left(-\frac{1}{x\sqrt{1-x}}+\frac{1}{x}\right) 
   = -\frac{1}{4^{p}p} \binom{2p}{p},
\end{align*}
and one finds with Lemma \ref{lem2} (below) 
\begin{equation}
\begin{split}
   h_{p}'(1)& = -\frac{1}{4^{p} p} \binom{2(p-1)}{p-1} 
   - \frac{1}{4^{p}} \sum_{j=1}^{p-1} \frac{1}{j} \binom{2j}{j} \binom{2(p-1-j)}{p-1-j}\\
&=-\frac{1}{4^{p} p} \binom{2(p-1)}{p-1}- \frac{2}{4^{p}}\binom{2(p-1)}{p-1}(H_{2p-2}-H_{p-1})\\
&=-\frac{1}{4^p}\binom{2(p-1)}{p-1}\bigg(\frac{1}{p}+2(H_{2p-2}-H_{p-1})\bigg).
\end{split}   
\label{h'}
\end{equation}
However, the way (\ref{c_v}) is expressed is ungainly and the substitution $x=\frac{4t}{(1+t)^2}$ is useful for the following computations
\begin{equation*}
\begin{split}
C_v(1,x)&=\frac{2t}{1-t^2}\log\bigg(\frac{1}{1+t}\bigg)-\frac{t}{1+t}\,,\\
C_{vv}(1,x)&=-\frac{2t(t^2+1)}{(1-t)^3(1+t)}\log^2\bigg(\frac{1}{1+t}\bigg)+\frac{2t}{(1-t)^2}\log\bigg(\frac{1}{1+t}\bigg)+\frac{t}{1-t^2}\,.
\end{split}
\end{equation*}

\begin{lemma}
\label{lem2}
\begin{equation*}
\begin{split}
 &(i)\,\sum\limits_{j\geq 1}\frac{1}{j}{2j\choose j}z^j=2\log\left(\frac{1-\sqrt{1-4z}}{2z}\right)\,,\\
&(ii)\,\sum_{j=1}^{p-1} \frac{1}{j} \binom{2j}{j} \binom{2(p-1-j)}{p-1-j}=\binom{2(p-1)}{p-1}(H_{2p-2}-H_{p-1})\,.
\end{split}
\end{equation*}
\end{lemma}
\begin{proof}
(i) It is easier to prove the equivalent result
\begin{equation*}
\begin{split}
\sum\limits_{j\geq 1}{2j\choose j}z^{j-1}&=2\frac{d}{dz}\left[\log\left(\frac{1-\sqrt{1-4z}}{2z}\right)\right]\\
&=\frac{4}{\sqrt{1-4z}(1-\sqrt{1-4z})}-\frac{2}{z}=\frac{1}{z}\left[\frac{1}{\sqrt{1-4z}}-1\right].
\end{split}
\end{equation*}
Now, it is well known that
\begin{equation*}
\sum\limits_{j\geq 0}{2j\choose j}z^j=\frac{1}{\sqrt{1-4z}},
\end{equation*}
and thus
\begin{equation*}
\sum\limits_{j\geq 1}{2j\choose j}z^{j-1}=\frac{1}{z}\left[\frac{1}{\sqrt{1-4z}}-1\right],
\end{equation*}
which proves the first part of the lemma.\\
\\
(ii) We use the substitution
\begin{equation*}
z=\frac{u}{(1+u)^2},\quad dz=\frac{1-u}{(1+u)^3}du,\quad \sqrt{1-4z}=\frac{1-u}{1+u},
\end{equation*}
to simplify the given summation as follows
\begin{align*}
\sum_{j=1}^{p-1} \frac{1}{j} \binom{2j}{j} \binom{2(p-1-j)}{p-1-j}
&=[z^{p-1}]\frac{1}{\sqrt{1-4z}}\log\left(\frac{1-\sqrt{1-4z}}{2z}\,\right)^2\\
&=\frac{1}{2\pi i}\oint \frac{(1+u)^{2p-2}}{u^{p}}2\log(1+u) du\\
&=[u^{p-1}]2(1+u)^{2p-2}\log(1+u)\\
&=(-1)^p[u^{p-1}]2(1-u)^{2p-2}\log\left(\frac{1}{1-u}\right)\\
&=2(-1)^p{-p\choose p-1}(H_{-p}-H_{-2p+1})\\
&=2{2p-2\choose p-1}(H_{2p-2}-H_{p-1})\,.
\end{align*}
\end{proof}

We can determine the constant term $v'(0)$ in the asymptotic expansion of the 
expectation $E_{n,p}$ given above:
\begin{align*}
   v'(0) & = \frac{1}{2} + p (H_{2p-2}-H_{p-1}) - \frac{p}{2} \Psi\Big(\frac{2p-1}{2}\Big) \\
   & = \frac{1}{2} + p(H_{2p-2}-H_{p-1}) - \frac{p}{2}\left(2H_{2p-2}-H_{p-1}+\Psi\Big(\frac{1}{2}\Big)\right)
   = -\frac{p}{2} H_{p} + \frac{p}{2} \gamma + p \log 2.
\end{align*}
Next we compute $v''(0)$ in the variance. We obtain
\begin{equation*}
\begin{split}
v''(s)&=\frac{h''_p(e^s)e^{2s}}{h_p(e^s)}+\frac{h'_p(e^s)e^s}{h_p(e^s)}-\frac{(h'_p(e^s))^2e^{2s}}{h_p^2(e^s)}\\
&-\frac{p}{2}e^s\Psi\bigg(\frac{p(e^s+1)-1}{2}\bigg)-\frac{p^2}{4}e^{2s}\Psi'\bigg(\frac{p(e^s+1)-1}{2}\bigg)\,,\\
v''(0)&=\frac{h''_p(1)}{h_p(1)}+\frac{h_p'(1)}{h_p(1)}-\frac{(h'_p(1))^2}{h_p^2(1)}-\frac{p}{2}\Psi\bigg(\frac{2p-1}{2}\bigg)-\frac{p^2}{4}\Psi'\bigg(\frac{2p-1}{2}\bigg)\,.
\end{split}
\end{equation*}
Firstly, we are required to calculate $h''_p(1)=[x^p]C_{vv}(1,x)$, namely
\begin{equation}
\begin{split}
&[x^p]\bigg(-\frac{2t(t^2+1)}{(1-t)^3(1+t)}\log^2\bigg(\frac{1}{1+t}\bigg)+\frac{2t}{(1-t)^2}\log\bigg(\frac{1}{1+t}\bigg)+\frac{t}{1-t^2}\bigg)\,.\\
\end{split}
\label{h''}
\end{equation}
We confine ourselves to considering the first few terms only.   From the 
series expansion of (\ref{h''}) we can produce the local expansion around the 
dominant singularity $x=1$ and use singularity analysis \cite{fo}:
\begin{equation}
\begin{split}
h''_p(1)&=[x^p]\bigg(-\frac{\log^2 2}{4}(1-x)^{-3/2}+\left(\frac12-\frac{\log 2}{4}\right)(1-x)^{-1/2}+\mathcal{O}(1)\bigg)\\
&= -\frac{\log^2 2}{4}{-3/2\choose p}+
\left(\frac12-\frac{\log 2}{4}\right){-1/2\choose p}+\mathcal{O}(1).
\end{split}
\label{h''}
\end{equation}
 From this it follows that
\begin{equation}
v''(0)=-\frac12\,p\log p+p\Big(\log 2-\frac54\Big)+\frac18\log 2+{\frac {15}{16}}-\frac14\,
\log^2 2+\mathcal{O}({p}^{-1})\,.
\label{va}
\end{equation}

%\newpage
\begin{figure}[!h]
\includegraphics[height=7cm]{ancestor.eps}
\caption{The probability distributions of the ancestor tree for $n=30$, $p=1,\dots,20$.}
\end{figure}


\section{The Steiner Distance}

An analogous approach works for the Steiner distance. Here  
$Y_{n,p}$ will denote the random variable that counts the Steiner distance
of $p$ randomly chosen nodes in a tree of size $n$ of a given tree family.

For increasing trees we get, by introducing the generating function
\begin{equation*}
   F(z,u,v) = \sum_{n \ge 0, p \ge 0, m \ge 0} \P\left\{Y_{n,p}=m\right\} T_{n}\,
   \binom{n}{p} \frac{z^{n}}{n!} u^{p} v^{m}
\end{equation*}
the equation
\begin{align}
   \frac{\partial}{\partial z}F(z,u,v) & = 
   \varphi'(T(z))F(z,u,v) + \frac{\partial}{\partial z}G(z,u,v) - v\varphi'(T(z))G(z,u,v)
   -(1-v)\varphi'(T(z))T(z),
   \label{Fz}
\end{align}
with initial value $F(0,u,v)=0$. The generating functions $T(z)$ and $G(z,u,v)$ are 
as defined in Section \ref{sec1}. The first two terms in (\ref{Fz})
arise when the root is labelled and the last two terms represent the
corrections arising when the root is not labelled.  

In this paper we only
look at $\varphi(t)=\frac{1}{1-t}$ which is the special case of heap ordered 
trees.  Therefore the Steiner distance requires the 
study of the differential equation
\begin{equation*}
\frac{\partial}{\partial z}F(z,u,v)
=\frac{\partial}{\partial z}G(z,u,v)+F(z,u,v)\frac{1}{1-2z}
-G(z,u,v)\frac{v}{1-2z}-\frac{1-v}{1-2z}(1-\sqrt{1-2z}\,).
\end{equation*}
This is a first order differential equation.  We solve for $F(z,u,v)$ and get
\begin{equation}
F(z,u,v)=\frac{1}{\sqrt{1-2z}}\int\limits_0^z\sqrt{1-2t}\left[\frac{\partial}{\partial t}G(t,u,v)-G(t,u,v)\frac{v}{1-2t}
-\frac{1-v}{1-\sqrt{1-2t}}\right] dt\,.
\label{eqn3}
\end{equation}


For the expectation we differentiate $F(z,u,v)$ with respect to $v$ and let $v=1$ to obtain
\begin{equation}
\begin{split}
\frac{\partial}{\partial v}F(z,u,v)\Big\vert_{v=1}=\frac{1}{\sqrt{1-2z}}\int\limits_0^z\sqrt{1-2t}\bigg[\frac{\partial ^2}{\partial v\partial t}G(t,u,v)\Big\vert_{v=1}-\frac{\partial}{\partial v}G(t,u,v)\Big\vert_{v=1}\frac{1}{1-2t}\\
-\frac{1-\sqrt{1-2t(1+u)}}{1-2t}+\frac{1}{1-\sqrt{1-2t}}\bigg] dt\,,
\end{split}
\label{Fv}
\end{equation}
since $G(z,u,v)\big\vert_{v=1}=1-\sqrt{1-2z(1+u)}$.  This integration is 
cumbersome, so instead of performing it we find the coefficients 
$u^p$ in (\ref{Fv}) and then we consider the dominant term 
\begin{equation}
\begin{split}
&[u^p]\frac{\partial}{\partial v}F(z,u,v)\Big\vert_{v=1}
=[u^p]\frac{1}{\sqrt{1-2z}}\int\limits_0^z\sqrt{1-2t}
\bigg[\frac{\partial ^2}{\partial v\partial t}G_p(t,v)\Big\vert_{v=1}
-\frac{\partial}{\partial v}G_p(t,v)\Big\vert_{v=1}\frac{1}{1-2t}\\
&\hspace*{6cm}-\frac{1-\sqrt{1-2t(1+u)}}{1-2t}+\frac{1}{1-\sqrt{1-2t}}\bigg] dt\\
&=\bigg(\frac{ph_p(1)\log(1-2z)}{(1-2z)^{p-1/2}}-\frac{h_p'(1)}{(1-2z)^{p-1/2}}
+\frac{h_p'(1)}{(1-2z)^{1/2}}\bigg)
+\mathcal{O}
\bigg(\frac{\log(1-2z)}{(1-2z)^{p-3/2}}\bigg)\\
&\hspace*{6cm}
-[u^p]\frac{1}{\sqrt{1-2z}}\int\limits_0^z \frac{1-\sqrt{1-2t(1+u)}}{\sqrt{1-2t}}dt\,,\\
\end{split}
\label{steiner}
\end{equation}
where $h_p(1)$ and $h'_p(1)$ were computed in (\ref{h}) and (\ref{h'}) respectively.  
It is not difficult to see that
\begin{equation*}
[u^p]\frac{1}{\sqrt{1-2z}}\int\limits_0^z \frac{1-\sqrt{1-2t(1+u)}}
{\sqrt{1-2t}}dt=\mathcal{O}\left(\frac{1}{(1-2z)^{p-1/2}}\right),
\end{equation*}
therefore the main contribution comes from 
${ph_p(1)\log(1-2z)}/{(1-2z)^{p-1/2}}$.  

We find the expected value of the Steiner distance, $\E(Y_{n,p})$, 
by dividing (\ref{steiner}) by our normalizing constant 
${\binom np}^{-1}\frac{n!}{1\cdot 3\cdots (2n-3)}$ 
and then reading off the coefficient of $z^n$ in the resulting equation. 
Firstly, looking at the dominant term in (\ref{steiner}) we see that
\begin{equation}
\begin{split}
E_{n,p}&=[z^n]\frac{{n\choose p}1\cdot3\cdots (2n-3)}{n!}\,\,\frac{ph_p(1)\log(1-2z)}{(1-2t)^{p-1/2}}\\
&=[z^n]\frac{{n\choose p}1\cdot3\cdots (2n-3)}{n!}\,\,\frac{-p\frac{2}{p4^p}{2(p-1)\choose p-1}\log(1-2z)}{(1-2z)^{p-1/2}}
\sim\frac{p}{2}\log n\,,
\end{split}
\label{expste}
\end{equation}
since we have the following
\begin{equation*}
\begin{split}
[z^n]\frac{1}{(1-2z)^{p-1/2}}\log(1-2z)
&=-2^n[z^n]\frac{1}{(1-z)^{p-1/2}}\log\frac{1}{1-z}\\
&=-2^n{n+p-3/2\choose n}(H_{n+p-3/2}-H_{p-3/2})\\
&\sim -2^n\frac{n^{p-3/2}}{\Gamma(p-\tfrac12)}\log n \,  \quad (n\rightarrow\infty,\, p \,\,\text{fixed})\,,
\end{split}
\end{equation*}
as well as $\frac{n!}{1\cdot3\cdots(2n-3)}\sim 2^{1-n}n^{3/2}\sqrt{\pi}$ and ${n\choose p}\sim \frac{n^p}{p!}$.

\bigskip

To obtain limiting theorems for the distribution of $Y_{n,p}$,
we want to apply the quasi power theorem again and will therefore require for $|v-1| \le \varepsilon$ 
a uniform expansion of $F_{p}(z,v)=[u^{p}] F(z,u,v)$ around the 
dominant singularity $z=\frac{1}{2}$. 
From equation \eqref{eqn3} we obtain immediately
\begin{equation}
   \label{eqn4}
   F_{p}(z,v) = \frac{1}{\sqrt{1-2z}} \int_{t=0}^{z} \sqrt{1-2t}
   \left(\frac{\partial}{\partial t}G_{p}(t,v) - \frac{v}{1-2t}G_{p}(t,v)\right) dt.
\end{equation}
We will now use the following more detailed expansion of $G_p(z,v)$ which follows from the proof of Lemma 1:
\begin{equation*}
   G_{p}(z,v) = -h_{p}(v) \frac{1}{(1-2z)^{\frac{p(v+1)-1}{2}}}
   + \sum_{\shortstack[c]{$\scriptstyle{1 \le k \le p-1,}$\\ $\scriptstyle{0\le j \le p-k}$}}
   \alpha_{p,k,j}(v) \frac{\log^{j}(1-2z)}{(1-2z)^{\frac{k(v+1)-1}{2}}}
   + \alpha_{p,0,0}(v) \sqrt{1-2z}.
\end{equation*}
This is also used to obtain the bound for the remainder term given below.

The integrand in \eqref{eqn4} is then given by
\begin{align*}
   & \sqrt{1-2t} \left(\frac{\partial}{\partial t}G_{p}(t,v) - \frac{v}{1-2t}G_{p}(t,v)\right)\\
   & = \sqrt{1-2t}\left(\frac{-h_{p}(v) (p(v+1)-1)}{(1-2t)^{\frac{p(v+1)+1}{2}}}
   +\frac{v h_{p}(v)}{(1-2t)^{\frac{p(v+1)+1}{2}}} + 
   \mathcal{O}\left(\frac{\log(1-2t)}{(1-2t)^{\frac{(p-1)(v+1)+1}{2}}}\right) \right)\\
   & = -\frac{h_{p}(v) (p-1)(v+1)}{(1-2t)^{\frac{p(v+1)}{2}}} 
   + \mathcal{O}\left(\frac{\log(1-2t)}{(1-2t)^{\frac{(p-1)(v+1)}{2}}}\right),
\end{align*}
and we get thus for $p \ge 2$ the expansion
\begin{equation*}
   F_{p}(z,v) = -\frac{h_{p}(v) (p-1) (v+1)}{p(v+1)-2} \frac{1}{(1-2z)^{\frac{p(v+1)-1}{2}}}
   + \mathcal{O}\left(\frac{\log(1-2z)}{(1-2z)^{\frac{(p-1)(v+1)-1}{2}}}\right).
\end{equation*}

Using singularity analysis to extract coefficients leads to
\begin{equation*}
   [z^{n}] F_{p}(z,v) = - \frac{h_{p}(v) (p-1) (v+1)}{p(v+1)-2} 
   \frac{2^{n} n^{\frac{p(v+1)-1}{2}-1}}{\Gamma(\frac{p(v+1)-1}{2})}
   \left(1+\mathcal{O}\left(\frac{1}{n^{1-\varepsilon}}\right)\right),
\end{equation*}
and furthermore
\begin{align*}
   \sum_{m \ge 0} \mathbb{P}(Y_{n,p}=m) v^{m} & = \frac{n!}{\binom{n}{p} T_{n}}
   [z^{n}] F_{p}(z,v) \\
   & = -\frac{2 \sqrt{\pi} p! (p-1) (v+1) h_{p}(v)}
   {\Gamma(\frac{p(v+1)-1}{2}) (p(v+1)-2)} n^{\frac{p(v-1)}{2}}
   \left(1+\mathcal{O}\left(\frac{1}{n^{1-\varepsilon}}\right)\right).
\end{align*}

With the notations used in the quasi power theorem we have
\begin{equation*}
   u(s) = \frac{p(e^{s}-1)}{2}, \qquad v(s) = 
   \log\left(\frac{-2\sqrt{\pi} p! (p-1) (e^{s}-1) h_{p}(e^{s})}
   {\Gamma(\frac{p(e^{s}+1)-1}{2}) (p(e^{s}+1)-2)}\right),
\end{equation*}
which gives
\begin{equation*}
   u'(0)=\frac{p}{2}, \quad u''(0)=\frac{p}{2}.
\end{equation*}
For $p \ge 2$,  $v(1) \neq 0$ since $h_{p}(1) < 0$ and thus the quasi power theorem is applicable. On the other hand, for $p=1$
one knows {\it a priori}, from the combinatorial description, that $\mathbb{P}\{Y_{n,1}=1\}=1$ for $n \ge 1$.

For the constant $v'(0)$ in the expectation $E_{n,p}=\mathbb{E}(Y_{n,p})$ we compute
\begin{align*}
   v'(s) & = \left[\log(e^{s}+1)+\log\big(h_{p}(e^{s})\big) - \log\big(p(e^{s}+1)-2\big) 
   - \log\Gamma\Big(\frac{p(e^{s}+1)-1}{2}\Big)\right]'\\
   & = \frac{e^{s}}{e^{s}+1} + \frac{h_{p}'(e^{s}) e^{s}}{h_{p}(e^{s})}
   - \frac{p e^{s}}{p(e^{s}+1)-2} - \frac{p e^{s}}{2}\Psi\Big(\frac{p(e^{s}+1)-1}{2}\Big),
\end{align*}
and further
\begin{equation*}
   v'(0) = \frac{h_{p}'(1)}{h_{p}(1)} - \frac{p}{2} \Psi\Big(\frac{2p-1}{2}\Big) 
- \frac{1}{2(p-1)}
   = -\frac{p}{2} H_{p} + \frac{p}{2} \gamma + p \log2 - \frac{1}{2(p-1)}.
\end{equation*}

We note that this gives us the expected value with a higher accuracy than 
(\ref{expste}) and it leads to the following theorem.
\begin{theorem}
   The distribution of the random variable $Y_{n,p}$, which counts the Steiner distance
   of $p$ randomly chosen nodes in a random heap ordered tree of size $n$
   is for $p \ge 2$ asymptotically Gaussian, where the convergence rate is of order
   $\mathcal{O}\big(\frac{1}{\sqrt{\log n}}\big)$:
   \begin{equation*}
      \P\Bigg\{\frac{Y_{n,p}-\frac{p}{2} \log n}
{\sqrt{\frac{p}{2}\log n}} < x\Bigg\}
      = \Phi(x) + \mathcal{O}\left(\frac{1}{\sqrt{\log n}}\right),
   \end{equation*}
   and the expectation $E_{n,p} = \E(Y_{n,p})$ and the variance $V_{n,p} = \V(X_{n,p})$
   satisfy
   \begin{align*}
      E_{n,p} & = \frac{p}{2} \log n -\frac{p}{2} H_{p} + \frac{p}{2} \gamma 
      + p \log2 - \frac{1}{2(p-1)}  + \mathcal{O}\left(\frac{1}{n^{1-\varepsilon}}\right), \\
      V_{n,p} & = \frac{p}{2} \log n + v''(0) + \mathcal{O}\left(\frac{1}{n^{1-\varepsilon}}\right).
   \end{align*}
\end{theorem}
\qed

For the proof, it remains to discuss the variance.  Since we have obtained the 
variance of the size of the ancestor tree in (\ref{va}), 
we can easily get the variance of the Steiner distance.
It follows that
\begin{equation*}
\begin{split}
v''(s)&=\frac{e^s}{e^s+1}-\frac{e^{2s}}{e^s+1}+\frac{h''_p(e^s)e^s}{h_p(e^s)}+\frac{h'_p(e^s)e^s}{h_p(e^s)}-\frac{(h'_p(e^s))^2e^{2s}}{h_p^2(e^s)}\\
&-\frac{pe^s}{p(e^s+1)-2}+\frac{p^2e^{2s}}{(p(e^s+1)-2)^2}\\
&-\frac{pe^s}{2}\Psi\bigg(\frac{p(e^s+1)-1}{2}\bigg)-\frac{p^2e^{2s}}{4}\Psi'\bigg(\frac{p(e^s+1)-1}{2}\bigg)\,,
\end{split}
\end{equation*}
where $h''_p(1)$ is given by (\ref{h''}) and furthermore,
\begin{equation*}
\begin{split}
v''(0)&=\frac34+\frac{h''_p(1)}{h_p(1)}+\frac{h'_p(1)}{h_p(1)}-\frac{(h'_p(1))^2}{h^2_p(1)}-\frac{p}{2(p-1)}+\frac{p^2}{4(p-1)^2}\\
&-\frac{p}{2}\Psi\bigg(\frac{2p-1}{2}\bigg)-\frac{p^2}{4}\Psi'\bigg(\frac{2p-1}{2}\bigg)\\
&=-\frac p2\log p+p\left(\log 2-\frac54\right)+\frac18\log 2+{\frac {23}{16}}-\frac14\,
\log^2 2+\mathcal{O}({p}^{-1})\,.
\end{split}
\end{equation*}

%\newpage
\begin{figure}[!h]
\includegraphics[height=7cm]{steiner.eps}
\caption{The probability distributions of the Steiner distance for $n=30$, 
$p=2,\dots,20$.}
\end{figure}






\bibliographystyle{plain} 


\begin{thebibliography}{10}
\bibitem{as}
M.~Abramowitz and I.A.~Stegun.  
\newblock Handbook of Mathematical Functions.  
\newblock Dover, 1972.

\bibitem{bfs}
F.~Bergeron, F.~Flajolet and B.~Salvy.  
\newblock Varieties of Increasing Trees.  
\newblock{\em Lecture Notes in Computer Science}, 581:24--48, 1992.

\bibitem{DaOeSw96}
P.~Dankelmann, O. R.~Oellermann and H. C.~Swart.  
\newblock The Average Steiner Distance of a Graph.  
\newblock{\em Journal of Graph Theory}, 22:15--22, 1996.

\bibitem{fo}
P.~Flajolet and A.~Odlyzko.  
\newblock Singularity Analysis of Generating Functions.  
\newblock{\em SIAM Journal of Discrete Mathematics}, 3:216--240, 1990.

\bibitem{Hwang98}
H.-K.~Hwang.
\newblock On Convergence Rates in the Central Limit Theorems for Combinatorial Structures.
\newblock {\em European Journal of Combinatorics}, 19:329--343, 1998.

\bibitem{MaNe02}
H.~Mahmoud and R.~Neininger.  
\newblock Distribution of Distances in Random Binary Search Trees.  
\newblock{\em The Annals of Applied Probability}, accepted for
publication, 2002.

\bibitem{Pan02}
A.~Panholzer.  
\newblock The distribution of the size of the ancestor tree and of the
induced spanning subtree for random trees, submitted, 2002.

\bibitem{PanPro02}
A.~Panholzer and H.~Prodinger.
\newblock Spanning tree size in random binary search trees,
submitted, 2002.

\bibitem{Pro96}
H.~Prodinger.  
\newblock Depth and Path Length of Heap Ordered Trees.  
\newblock{\em International Journal of Foundations of Computer Science}, 
7:293-299, 1996.

\bibitem{Pro97}
H.~Prodinger.  
\newblock The Level of Nodes in Heap Ordered Trees.  
\newblock{\em http://www.wits.ac.za/helmut/abstract/\\abs\underline{\ }126.htm}, 
 1996.

\bibitem{Nei02}
R.~Neininger.  
\newblock Wiener Index of Random Trees.  
\newblock{\em Combinatorics, Probability and Computing}, accepted for
publication, 2002.

\end{thebibliography}

\newpage



\end{document}





