
\documentstyle[oldlfont,a4ams,righttag,ctagsplt,emlines2,11pt]{amsart}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\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=10pt

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

\newtheorem{df}{Definition}[section]
\newtheorem{ex}{Example}
\renewcommand{\theex}{}
\def\comp#1#2{C_{#1,#2}}
\def\compp#1#2{{\cal C}_{#1,#2}(v)}
\def\mom#1#2{D_{#1,#2}}
\def\dilog{\operatorname{dilog}}
\def\var{\operatorname{Var}}
%def\rho{\varrho}
\def\ca{{\cal{C}}}
\def\hot{heap ordered tree}
\def\wh{\widehat{H}}
\def\stir#1#2{\left[#1\atop#2\right]}


\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[The level of nodes in heap ordered trees]{The level of nodes in heap ordered trees}
\author[Helmut~Prodinger]
{Helmut Prodinger}
\address{  Institut f\"ur Algebra und Diskrete Mathematik\\
Technical University of Vienna\\
Wiedner Hauptstrasse 8--10\\ A-1040 Vienna, Austria.}
\email{Helmut.Prodinger@@tuwien.ac.at\vskip0pt
{\it WWW-address{\rm :\ }}\texttt{http://info.tuwien.ac.at/theoinf/proding.htm}
}



\date{\today}
\begin{abstract} 
A  heap ordered tree with $n$ nodes (``size $n$'')
is a  planted plane tree
together with a bijection from the nodes to the set $\{1,\dots,n\}$
which is  monotonically increasing
 when going from the root to the leaves.
We consider the level of the node $j$ in a (random)
heap ordered tree  of size $n\ge j$. 
This distribution does not
depend on $n$. Precise expressions are derived for the expectation, the variance, and the
probability distribution.
\end{abstract} 

\maketitle



\section{Heap ordered trees}

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


\begin{figure}[h]
%\input{hott1.pic}
%
%
%
%
%TexCad Options
%\grade{\on}
%\emlines{\on}
%\beziermacro{\off}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{5}
%\zoom{0.40}
\special{em:linewidth 0.4pt}
\unitlength 0.40mm
\linethickness{0.4pt}
\begin{picture}(322.89,36.00)
\put(74.00,31.00){\circle{10.00}}
\put(74.00,11.00){\circle{10.00}}
\put(59.00,11.00){\circle{10.00}}
\put(89.00,11.00){\circle{10.00}}
\emline{74.00}{26.00}{1}{74.00}{16.00}{2}
\emline{61.00}{15.67}{3}{71.67}{26.33}{4}
\emline{86.67}{15.67}{5}{76.00}{26.33}{6}
\put(74.00,31.00){\makebox(0,0)[cc]{1}}
\put(58.78,11.22){\makebox(0,0)[cc]{2}}
\put(73.89,11.22){\makebox(0,0)[cc]{3}}
\put(89.00,11.22){\makebox(0,0)[cc]{4}}
\put(119.78,31.00){\circle{10.00}}
\put(165.56,31.00){\circle{10.00}}
\put(211.33,31.00){\circle{10.00}}
\put(257.11,31.00){\circle{10.00}}
\put(302.89,31.00){\circle{10.00}}
\put(119.78,11.00){\circle{10.00}}
\put(165.56,11.00){\circle{10.00}}
\put(211.33,11.00){\circle{10.00}}
\put(257.11,11.00){\circle{10.00}}
\put(302.89,11.00){\circle{10.00}}
\put(104.78,11.00){\circle{10.00}}
\put(150.56,11.00){\circle{10.00}}
\put(196.33,11.00){\circle{10.00}}
\put(242.11,11.00){\circle{10.00}}
\put(287.89,11.00){\circle{10.00}}
\put(134.78,11.00){\circle{10.00}}
\put(180.56,11.00){\circle{10.00}}
\put(226.33,11.00){\circle{10.00}}
\put(272.11,11.00){\circle{10.00}}
\put(317.89,11.00){\circle{10.00}}
\emline{119.78}{26.00}{7}{119.78}{16.00}{8}
\emline{165.56}{26.00}{9}{165.56}{16.00}{10}
\emline{211.33}{26.00}{11}{211.33}{16.00}{12}
\emline{257.11}{26.00}{13}{257.11}{16.00}{14}
\emline{302.89}{26.00}{15}{302.89}{16.00}{16}
\emline{106.78}{15.67}{17}{117.45}{26.33}{18}
\emline{152.56}{15.67}{19}{163.23}{26.33}{20}
\emline{198.33}{15.67}{21}{209.00}{26.33}{22}
\emline{244.11}{15.67}{23}{254.78}{26.33}{24}
\emline{289.89}{15.67}{25}{300.56}{26.33}{26}
\emline{132.45}{15.67}{27}{121.78}{26.33}{28}
\emline{178.23}{15.67}{29}{167.56}{26.33}{30}
\emline{224.00}{15.67}{31}{213.33}{26.33}{32}
\emline{269.78}{15.67}{33}{259.11}{26.33}{34}
\emline{315.56}{15.67}{35}{304.89}{26.33}{36}
\put(119.78,31.00){\makebox(0,0)[cc]{1}}
\put(165.56,31.00){\makebox(0,0)[cc]{1}}
\put(211.33,31.00){\makebox(0,0)[cc]{1}}
\put(257.11,31.00){\makebox(0,0)[cc]{1}}
\put(302.89,31.00){\makebox(0,0)[cc]{1}}
\put(104.56,11.22){\makebox(0,0)[cc]{2}}
\put(150.33,11.22){\makebox(0,0)[cc]{3}}
\put(196.11,11.22){\makebox(0,0)[cc]{3}}
\put(241.89,11.22){\makebox(0,0)[cc]{4}}
\put(287.67,11.22){\makebox(0,0)[cc]{4}}
\put(119.67,11.22){\makebox(0,0)[cc]{4}}
\put(165.44,11.22){\makebox(0,0)[cc]{2}}
\put(211.22,11.22){\makebox(0,0)[cc]{4}}
\put(257.00,11.22){\makebox(0,0)[cc]{2}}
\put(302.78,11.22){\makebox(0,0)[cc]{3}}
\put(134.78,11.22){\makebox(0,0)[cc]{3}}
\put(180.56,11.22){\makebox(0,0)[cc]{4}}
\put(226.33,11.22){\makebox(0,0)[cc]{2}}
\put(272.11,11.22){\makebox(0,0)[cc]{3}}
\put(317.89,11.22){\makebox(0,0)[cc]{2}}
\end{picture}
\end{figure}


\begin{figure}[h]
%\input{hott2.pic}
%%
%
%
%
%TexCad Options
%\grade{\on}
%\emlines{\on}
%\beziermacro{\off}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{5}
%\zoom{0.40}
\special{em:linewidth 0.4pt}
\unitlength 0.40mm
\linethickness{0.4pt}
\begin{picture}(354.00,78.00)
\put(50.67,73.00){\circle{10.00}}
\put(40.67,53.00){\circle{10.00}}
\put(40.67,33.00){\circle{10.00}}
\put(60.67,53.00){\circle{10.00}}
\emline{58.67}{57.67}{1}{53.00}{68.33}{2}
\emline{48.33}{68.67}{3}{42.33}{57.67}{4}
\emline{40.67}{48.00}{5}{40.67}{38.00}{6}
\put(280.33,53.33){\circle{10.00}}
\put(290.33,33.33){\circle{10.00}}
\put(270.33,33.33){\circle{10.00}}
\emline{272.33}{38.00}{7}{278.00}{48.67}{8}
\emline{282.67}{49.00}{9}{288.67}{38.00}{10}
\put(280.00,73.00){\circle{10.00}}
\emline{280.00}{68.00}{11}{280.00}{58.00}{12}
\put(349.00,73.00){\circle{10.00}}
\put(349.00,53.00){\circle{10.00}}
\emline{349.00}{68.00}{13}{349.00}{58.00}{14}
\put(349.00,53.00){\circle{10.00}}
\put(349.00,33.00){\circle{10.00}}
\emline{349.00}{48.00}{15}{349.00}{38.00}{16}
\put(349.00,53.00){\circle{10.00}}
\put(349.00,33.00){\circle{10.00}}
\emline{349.00}{48.00}{17}{349.00}{38.00}{18}
\put(349.00,33.00){\circle{10.00}}
\put(349.00,13.00){\circle{10.00}}
\emline{349.00}{28.00}{19}{349.00}{18.00}{20}
\put(349.00,73.00){\makebox(0,0)[cc]{1}}
\put(280.00,73.00){\makebox(0,0)[cc]{1}}
\put(50.67,73.00){\makebox(0,0)[cc]{1}}
\put(40.67,52.67){\makebox(0,0)[cc]{2}}
\put(60.67,52.67){\makebox(0,0)[cc]{4}}
\put(40.67,32.67){\makebox(0,0)[cc]{3}}
\put(89.34,73.00){\circle{10.00}}
\put(128.00,73.00){\circle{10.00}}
\put(79.34,53.00){\circle{10.00}}
\put(118.00,53.00){\circle{10.00}}
\put(79.34,33.00){\circle{10.00}}
\put(118.00,33.00){\circle{10.00}}
\put(99.34,53.00){\circle{10.00}}
\put(138.00,53.00){\circle{10.00}}
\emline{97.34}{57.67}{21}{91.67}{68.33}{22}
\emline{136.00}{57.67}{23}{130.33}{68.33}{24}
\emline{87.00}{68.67}{25}{81.00}{57.67}{26}
\emline{125.66}{68.67}{27}{119.66}{57.67}{28}
\emline{79.34}{48.00}{29}{79.34}{38.00}{30}
\emline{118.00}{48.00}{31}{118.00}{38.00}{32}
\put(89.34,73.00){\makebox(0,0)[cc]{1}}
\put(128.00,73.00){\makebox(0,0)[cc]{1}}
\put(79.33,52.67){\makebox(0,0)[cc]{2}}
\put(118.00,52.67){\makebox(0,0)[cc]{3}}
\put(99.33,52.67){\makebox(0,0)[cc]{3}}
\put(138.00,52.67){\makebox(0,0)[cc]{2}}
\put(79.33,32.67){\makebox(0,0)[cc]{4}}
\put(118.00,32.67){\makebox(0,0)[cc]{4}}
\put(244.33,72.52){\circle{9.79}}
\put(254.33,53.48){\circle{9.79}}
\put(254.33,34.43){\circle{9.79}}
\put(234.33,53.48){\circle{9.79}}
\emline{236.33}{57.92}{33}{242.00}{68.08}{34}
\emline{246.67}{68.40}{35}{252.67}{57.92}{36}
\emline{254.33}{48.71}{37}{254.33}{39.19}{38}
\put(244.33,72.52){\makebox(0,0)[cc]{1}}
\put(254.33,53.16){\makebox(0,0)[cc]{3}}
\put(234.33,53.16){\makebox(0,0)[cc]{2}}
\put(254.33,34.11){\makebox(0,0)[cc]{4}}
\put(205.66,72.52){\circle{9.79}}
\put(167.00,72.52){\circle{9.79}}
\put(215.66,53.48){\circle{9.79}}
\put(177.00,53.48){\circle{9.79}}
\put(215.66,34.43){\circle{9.79}}
\put(177.00,34.43){\circle{9.79}}
\put(195.66,53.48){\circle{9.79}}
\put(157.00,53.48){\circle{9.79}}
\emline{197.66}{57.92}{39}{203.33}{68.08}{40}
\emline{159.00}{57.92}{41}{164.67}{68.08}{42}
\emline{208.00}{68.40}{43}{214.00}{57.92}{44}
\emline{169.34}{68.40}{45}{175.34}{57.92}{46}
\emline{215.66}{48.71}{47}{215.66}{39.19}{48}
\emline{177.00}{48.71}{49}{177.00}{39.19}{50}
\put(205.66,72.52){\makebox(0,0)[cc]{1}}
\put(167.00,72.52){\makebox(0,0)[cc]{1}}
\put(215.67,53.16){\makebox(0,0)[cc]{2}}
\put(177.00,53.16){\makebox(0,0)[cc]{2}}
\put(195.67,53.16){\makebox(0,0)[cc]{3}}
\put(157.00,53.16){\makebox(0,0)[cc]{4}}
\put(215.67,34.11){\makebox(0,0)[cc]{4}}
\put(177.00,34.11){\makebox(0,0)[cc]{3}}
\put(280.33,53.33){\makebox(0,0)[cc]{2}}
\put(290.33,33.33){\makebox(0,0)[cc]{4}}
\put(270.33,33.33){\makebox(0,0)[cc]{3}}
\put(316.16,53.33){\circle{10.00}}
\put(326.16,33.33){\circle{10.00}}
\put(306.16,33.33){\circle{10.00}}
\emline{308.16}{38.00}{51}{313.83}{48.67}{52}
\emline{318.50}{49.00}{53}{324.50}{38.00}{54}
\put(315.83,73.00){\circle{10.00}}
\emline{315.83}{68.00}{55}{315.83}{58.00}{56}
\put(315.83,73.00){\makebox(0,0)[cc]{1}}
\put(316.17,53.33){\makebox(0,0)[cc]{2}}
\put(326.17,33.33){\makebox(0,0)[cc]{3}}
\put(306.17,33.33){\makebox(0,0)[cc]{4}}
\put(348.67,53.00){\makebox(0,0)[cc]{2}}
\put(348.67,33.00){\makebox(0,0)[cc]{3}}
\put(348.67,13.00){\makebox(0,0)[cc]{4}}
\end{picture}
\caption{All 15 heap ordered trees with 4 nodes}
\end{figure}

In this note, we want to concentrate on the level of the node $j$ in a (random)
{\sl heap ordered tree\/}  of size $n\ge j$. This extends some of the results in  
\cite{Prodinger96a} and \cite{ChenNi94} where the average over $j$ 
(the {\sl  depth  of a  random node\/})
 was considered. It will turn out, that surprisingly, this distribution does not
depend on $n$. Precise expressions are derived for the expectation, the variance, and the
probability distribution. A general reference for heap ordered trees and, more generally,
{\sl increasing\/} trees is \cite{BeFlSa92}.
\medskip  

The enumeration of the numbers $a_n$ of  heap ordered trees of size $n$
is easy and appears already in \cite{ProUrb83}.
The recursion is
\begin{equation}\label{rec1}   
a_{n+1}=\sum_{m\ge1}\sum_{h_1+\dots+h_m=n}
\binom{n}{h_1,\dots,h_m} \, a_{h_1}\dots a_{h_m}\quad\hbox{for}\ {n\ge1}, \ \ a_1=1~;
\end{equation} 
hence the exponential generating function $A(z):=\sum_{n\ge0}a_n\frac
{z^n}{n!}$ fulfills the differential equation
$$
A'(z)=\frac1{1-A(z)}\qquad\hbox{with}\quad A(0)=0~,
$$
with the solution
$$
A(z)=1-\sqrt{1-2z\,}~,
$$
so that
$$
a_n=n!\,2^{1-n}\,\ca_n=1\cdot3\cdot5\dots(2n-3)~,
$$
with a (shifted) {\sl Catalan number}
$\ca_n=\frac1n\binom{2n-2}{n-1}$.
\smallskip


Now let us consider
the average level of node $j$ in a heap ordered tree  of size $n$.  
For that purpose we need a different recursion than (\ref{rec1}).
We want to fix the subtree which contains $j$ 
and say that it is the first subtree. However, $j$  can be in any of the $m$ subtrees.
So we introduce a factor $m$.  (Of course, we assume $j\ge2$.)
But then, we cannot choose $h_1$ numbers out of 
$\{2,\dots, n+1\}$, since we know already that $j$ is there!   

Therefore our alternative recursion is  

\begin{equation}\label{rec2}   
a_{n+1}=\sum_{m\ge1}\sum_{h_1+\dots+h_m=n}
m\, \binom{n-1}{h_1-1,h_2,\dots,h_m} \,
 a_{h_1}\dots a_{h_m}\quad\hbox{for}\ {n\ge1}, \ \ a_1=1~.
\end{equation} 
Let us test via generating functions that this is indeed correct.
We multiply (\ref{rec2}) by $\frac{z^{n-1}}{(n-1)!}$  and sum up. The right hand side becomes
\begin{equation*}   
\frac{d}{du}\frac{u\, A'(z)}{1-u\, A(z)}\bigg|_{u=1}=\frac{1}{(1-2z)^{3/2}}~.
\end{equation*}
The left hand side is $A{''}(z)$, which equals the same quantity.

Now we want the probability that $j$ lies in a subtree of size $k$. This is
\begin{equation*}   
\sum_{m\ge1}\sum_{h_2+\dots+h_m=n-k}
m\, \binom{n-1}{k-1}\, \binom{n-k}{h_2,\dots,h_m} \, \frac{a_{k}a_{h_2}\dots a_{h_m}}{a_{n+1}}
\end{equation*}   
We compute the factor of $\binom{n-1}{k-1}\frac{a_k}{a_{n+1}}$ 
in this expression by multiplying this
factor by $\frac{z^{n-k}}{(n-k)!}$ and summing up. The result is amazingly simple:
\begin{equation*}   
\frac{d}{du}\frac{u}{1-u\, A(z)}\bigg|_{u=1}=\frac{1}{1-2z}~,
\end{equation*}
whence our sought probability that $j$ lies in a subtree of size $k$ turns out to be
\begin{equation*}   
\binom{n-1}{k-1}\,\frac{a_k}{a_{n+1}}\, 2^{n-k}\, (n-k)!~.
\end{equation*}
Again, it is an easy check that the sum on $k$ of this quantity is 1.

Now, let $D_{n,j}$ be the average level of node $j$.
To avoid misinterpretations, we say that the root (= the node `1') is
on level 0. Using the last probability, we can set up a recursion for  $D_{n,j}$.
However, we must take care of the fact that in its subtree, `$j$' does not mean `$j$'  any 
further. The numbers in the subtree are to be replaced by $1,2,\dots$, according to their
relative order. Let us compute the probability that $j$ will be $i$   after this procedure,
or, what is the same, that $j$ is the $i$th largest number in its subtree. It is
\begin{equation*}   
\frac{\binom{j-2}{i-1}\binom{n+1-j}{k-i} }{\binom{n-1}{k-1} }~,
\end{equation*} 
since $i-1$ numbers have to be chosen from $\{2,3,\dots,j-1\}$ and
$k-i$ numbers from \linebreak $\{j+1,\dots, n+1\}$.

Therefore we finally found our recursion:
\begin{equation}   \label{rec3}   
D_{n+1,j}=1+\sum_{k=1}^{n}
\binom{n-1}{k-1}\,\frac{a_k}{a_{n+1}}\, 2^{n-k}\, (n-k)!
\sum_{i=1}^k
\frac{\binom{j-2}{i-1}\binom{n+1-j}{k-i} }{\binom{n-1}{k-1} }\, D_{k,i}~.
\end{equation} 
This recursion is valid for $n+1\ge j\ge2$. Additionally, we have, since `1' is always
on level 0, that $D_{n,1}=0$  for all $n\ge1$. 

The solution of this recursion is found by inspection\footnote{We used {\sc Maple} to `see' it.}
 (!), and it transpires that
\begin{equation*}
D_{n,j}=H_{2j-2}-\tfrac{1}{2}H_{j-1}\, , \quad\text{independently of $n$}\ \ (n\ge j) ~.
\end{equation*}
\smallskip

Since we have such a simple result, we should {\sl explain\/} it and {\sl prove\/} it.
The independency on $n$ means that the nodes larger than $j$ don't change anything.
We might say that a random tree of $n$ nodes 
(each heap ordered tree  is equally likely) remains `random'
if we cut off the nodes larger than $j$. This is in fact not too hard to see. First, it
is enough to show that randomness is preserved if we erase node $n$. Or, since
\begin{equation*}   
\frac{a_{n+1}}{a_n}=2n-1~,
\end{equation*} 
we might alternatively show that from each tree with $n$ nodes, we get $2n-1$ new trees
by inserting the new node $n+1$. We can attach this new node on every node, but the 
relative order in the plane is important, so if a certain node has $i$ outgoing branches,
it gives us $i+1$ possibilities, namely to the left of all, between first and second edge, etc.
Denoting by $d(k)$     the number of outgoing branches, we have altogether
\begin{equation*}   
\sum_{k=1}^n\Big(1+d(k)\Big)=n+\text{number of edges}=2n-1~,
\end{equation*}
as desired. 

\begin{figure}[h]
%\input{hott3.pic}
%
%
%TexCad Options
%\grade{\on}
%\emlines{\on}
%\beziermacro{\off}
%\reduce{\on}
%\snapping{\off}
%\quality{2.00}
%\graddiff{0.01}
%\snapasp{5}
%\zoom{0.40}
\special{em:linewidth 0.8pt}
\unitlength 0.40mm
\linethickness{0.8pt}
\begin{picture}(273.33,78.00)
\put(83.00,73.00){\circle{10.00}}
\put(83.00,53.00){\circle{10.00}}
\emline{83.00}{68.00}{1}{83.00}{58.00}{2}
\put(83.00,53.00){\circle{10.00}}
\put(83.00,33.00){\circle{10.00}}
\emline{83.00}{48.00}{3}{83.00}{38.00}{4}
\put(83.00,53.00){\circle{10.00}}
\put(83.00,33.00){\circle{10.00}}
\emline{83.00}{48.00}{5}{83.00}{38.00}{6}
\put(83.00,33.00){\circle{10.00}}
\put(83.00,73.00){\makebox(0,0)[cc]{1}}
\put(82.67,53.00){\makebox(0,0)[cc]{2}}
\put(82.67,33.00){\makebox(0,0)[cc]{3}}
\put(120.00,73.00){\circle{10.00}}
\put(157.00,73.00){\circle{10.00}}
\put(194.00,73.00){\circle{10.00}}
\put(231.00,73.00){\circle{10.00}}
\put(268.00,73.00){\circle{10.00}}
\put(120.00,53.00){\circle{10.00}}
\put(157.00,53.00){\circle{10.00}}
\put(194.00,53.00){\circle{10.00}}
\put(268.00,53.00){\circle{10.00}}
\emline{120.00}{68.00}{7}{120.00}{58.00}{8}
\emline{157.00}{68.00}{9}{157.00}{58.00}{10}
\emline{194.00}{68.00}{11}{194.00}{58.00}{12}
\emline{231.00}{68.00}{13}{231.00}{58.00}{14}
\emline{268.00}{68.00}{15}{268.00}{58.00}{16}
\put(120.00,53.00){\circle{10.00}}
\put(157.00,53.00){\circle{10.00}}
\put(194.00,53.00){\circle{10.00}}
\put(268.00,53.00){\circle{10.00}}
\put(120.00,33.00){\circle{10.00}}
\put(157.00,33.00){\circle{10.00}}
\put(194.00,32.00){\circle{10.00}}
\put(231.00,33.00){\circle{10.00}}
\put(268.00,33.00){\circle{10.00}}
\emline{120.00}{48.00}{17}{120.00}{38.00}{18}
\emline{157.00}{48.00}{19}{157.00}{38.00}{20}
\emline{231.00}{48.00}{21}{231.00}{38.00}{22}
\emline{268.00}{48.00}{23}{268.00}{38.00}{24}
\put(120.00,53.00){\circle{10.00}}
\put(157.00,53.00){\circle{10.00}}
\put(194.00,53.00){\circle{10.00}}
\put(231.00,53.00){\circle{10.00}}
\put(268.00,53.00){\circle{10.00}}
\put(120.00,33.00){\circle{10.00}}
\put(157.00,33.00){\circle{10.00}}
\put(194.00,32.00){\circle{10.00}}
\put(231.00,33.00){\circle{10.00}}
\put(268.00,33.00){\circle{10.00}}
\emline{120.00}{48.00}{25}{120.00}{38.00}{26}
\emline{157.00}{48.00}{27}{157.00}{38.00}{28}
\emline{231.00}{48.00}{29}{231.00}{38.00}{30}
\emline{268.00}{48.00}{31}{268.00}{38.00}{32}
\put(120.00,33.00){\circle{10.00}}
\put(157.00,33.00){\circle{10.00}}
\put(194.00,32.00){\circle{10.00}}
\put(231.00,33.00){\circle{10.00}}
\put(268.00,33.00){\circle{10.00}}
\put(120.00,73.00){\makebox(0,0)[cc]{1}}
\put(157.00,73.00){\makebox(0,0)[cc]{1}}
\put(194.00,73.00){\makebox(0,0)[cc]{1}}
\put(231.00,73.00){\makebox(0,0)[cc]{1}}
\put(268.00,73.00){\makebox(0,0)[cc]{1}}
\put(119.67,53.00){\makebox(0,0)[cc]{2}}
\put(156.67,53.00){\makebox(0,0)[cc]{2}}
\put(193.67,53.00){\makebox(0,0)[cc]{2}}
\put(230.67,53.00){\makebox(0,0)[cc]{2}}
\put(267.67,53.00){\makebox(0,0)[cc]{2}}
\put(119.67,33.00){\makebox(0,0)[cc]{3}}
\put(156.67,33.00){\makebox(0,0)[cc]{3}}
\put(193.67,32.00){\makebox(0,0)[cc]{3}}
\put(230.67,33.00){\makebox(0,0)[cc]{3}}
\put(267.67,33.00){\makebox(0,0)[cc]{3}}
\put(268.33,12.67){\circle{10.00}}
\put(268.33,12.67){\makebox(0,0)[cc]{4}}
\put(103.67,52.67){\circle{10.00}}
\put(103.67,52.67){\makebox(0,0)[cc]{4}}
\put(172.33,52.67){\circle{10.00}}
\put(172.33,52.67){\makebox(0,0)[cc]{4}}
\put(178.33,32.67){\circle{10.00}}
\put(178.33,32.67){\makebox(0,0)[cc]{4}}
\put(246.33,32.67){\circle{10.00}}
\put(246.33,32.67){\makebox(0,0)[cc]{4}}
\emline{116.14}{69.57}{33}{107.10}{56.67}{34}
\emline{181.33}{36.67}{35}{191.00}{49.00}{36}
\emline{268.00}{28.00}{37}{268.00}{17.67}{38}
\emline{235.00}{50.00}{39}{245.00}{37.67}{40}
\emline{160.67}{70.00}{41}{170.33}{57.33}{42}
\emline{194.00}{48.00}{43}{194.00}{37.00}{44}
\end{picture}
\caption{A heap ordered tree with 3 nodes and the 5 trees obtained by inserting a fourth node}
\end{figure}

To solve the recursion, we set $n=j-1$ and write $D_j=D_{j,j}$   for simplicity.
Then (\ref{rec3}) turns into
\begin{equation}\label{rec3a}   
D_j=1+\sum_{k=1}^{j-1}\frac{a_k}{a_j}\, 2^{j-1-k}\,(j-1-k)!\,\binom{j-2}{k-1}\, D_k~. 
\end{equation}
With
\begin{equation*}   
E_j:=\frac{a_jD_j}{2^j(j-1)!}~,
\end{equation*}
we get
\begin{equation*}   
2(j-1)E_j=\frac{2^{1-j}a_j}{(j-2)!}+\sum_{k=1}^{j-1}E_k~,
\end{equation*}
or, by taking differences of two consecutive equations,
\begin{equation*}   
2jE_{j+1}=(2j-1)E_j+\frac{a_j}{2^j(j-1)!}~,
\end{equation*}
which means that
\begin{equation*}   
D_{j+1}=D_j+\frac{1}{2j-1}~.
\end{equation*}
Unrolling this recursion, we get
\begin{equation*}   
D_j=1+\tfrac{1}{3}+\dots+\tfrac{1}{2j-3}=H_{2j-2}-\tfrac{1}{2}H_{j-1}~,
\end{equation*}
and that was to be demonstrated.
\medskip

We can get an easy corollary: Since
\begin{equation*}   
\sum_{j=1}^n\sum_{i=1}^{j-1}\frac{1}{2i-1}=\sum_{i=1}^n\frac{n-i}{2i-1}
=\sum_{i=1}^n\frac{(n-\tfrac12)-(i-\tfrac12)}{2i-1}
=\left(n-\frac{1}{2}\right)(H_{2n}-\tfrac{1}{2}H_n)-\dfrac{n}{2}~,
\end{equation*}
we get, by dividing this by $n$, the average depth $d_n$  of a random node 
\begin{equation*}   
d_n=\left(1-\frac{1}{2n}\right)(H_{2n}-\tfrac{1}{2}H_n)-\dfrac{1}{2}~,
\end{equation*}
a result from \cite{Prodinger96a} and \cite{ChenNi94}.

\medskip

Now we want to compute the variance. Very much in the style of
(\ref{rec3}) we can set up a recursion for the probability
generating functions $F_{n,j}(x)$;
\begin{equation*}   
F_{n+1,j}(x)=x\, \sum_{k=1}^{n}
\binom{n-1}{k-1}\,\frac{a_k}{a_{n+1}}\, 2^{n-k}\, (n-k)!
\sum_{i=1}^k
\frac{\binom{j-2}{i-1}\binom{n+1-j}{k-i} }{\binom{n-1}{k-1} }\, F_{k,i}(x)~.
\end{equation*} 
As before, we freely drop the index $n$, by replacing $n$  by $j-1$.
\begin{equation}   \label{rec4}   
F_{j}(x)=x\, \sum_{k=1}^{j-1}
\frac{a_k}{a_{j}}\, 2^{j-1-k}\, (j-1-k)!\,\binom{j-2}{k-1}\, 
 F_{k}(x)~.
\end{equation} 
With the short hand notation
\begin{equation*}
E_j=\frac{a_j F_j(x)}{2^j(j-1)!}~,
\end{equation*}
 we find
\begin{equation*}
2(j-1)E_{j+1}=x\sum_{k=1}^{j-1}E_j~,
\end{equation*}
whence
\begin{equation*}
2jE_{j+1}-2(j-1)E_j=xE_j~,
\end{equation*}
or
\begin{equation*}
E_j=\frac{2j-4+x}{2j-2}E_{j-1}=\frac1{2^{j-1}(j-1)!}\prod_{i=1}^{j-1}{(2i-2+x)}~.
\end{equation*}
Therefore
\begin{equation}\label{probgf}
F_j(x)=\prod_{i=1}^{j-1}\frac{2i-2+x}{2i-1}~.
\end{equation}
When we have the probability generating function in a factored form where each
factor constitutes a probability generating function itself, it
is particularly easy to get the variance, see \cite{Knuth68}.
\begin{equation*}
V_j:=\var \left\{F_j(x)\right\}=\sum_{i=1}^{j-1}\var\left\{\frac{2i-2+x}{2i-1}\right\}=
\sum_{i=1}^{j-1}\left[\frac{1}{2i-1}-\frac{1}{(2i-1)^2}\right]~.
\end{equation*}
The reader might have noticed that in this paper a modified notion
of harmonic numbers (of first and second order) would be more appropriate.
If we define
\begin{equation*}
\wh_n=\sum_{k=1}^n\frac{1}{2k-1}\qquad\text{and}\qquad
\wh_n^{(2)}=\sum_{k=1}^n\frac{1}{(2k-1)^2}~,
\end{equation*}
then we have
\begin{equation*}
V_j=\wh_{j-1}-\wh_{j-1}^{(2)}~;
\end{equation*}
in terms of harmonic numbers this equals
\begin{equation*}
V_j=H_{2j-2}-\tfrac12H_{j-1}-H_{2j-2}^{(2)}+\tfrac14
H_{j-1}^{(2)}~.
\end{equation*} 
From (\ref{probgf}) it is even possible to get an explicit expression 
for the coefficient of $x^k$, which is the probability that node $j$
is at level $k$.              We write
\begin{equation*}
F_j(x)=\frac{x(x+2)\dots (x+2(j-1))}{a_j}
=\frac{(-2)^{j-1}}{a_j}\left(-\frac x2\right)^{\underline{j-1}}
=\frac{2^{j-1}}{a_j}\sum_{k=0}^{j-1}\stir{j-1}k\frac{x^k}{2^k}~,
\end{equation*}   
and therefore
\begin{equation*}
[x^k]F_j(x)
=\frac{2^{j-1}}{a_j}\stir{j-1}k\frac{1}{2^k}~.
\end{equation*}   
Here, we used the notion of Stirling's cycle numbers $\stir nk$,
compare \cite{GrKnPa89}. 




For the readers convenience we 
collect our main findings as follows.
\medskip
\begin{theorem}
The average and the variance of the level (depth) of the  node
with label $j$
in a heap ordered tree  of at least $j$  nodes is given by
\begin{align*}
D_j&=\wh_{j-1}~,\\
V_j&=\wh_{j-1}-\wh_{j-1}^{(2)}~.
\end{align*}
The
probability that node $j$ has level $k$  is given by
\begin{equation*}
\frac{2^{j-1-k}}{a_j}\stir{j-1}k~.
\end{equation*}
\end{theorem}



\section{Binary trees}

For the sake of completeness and comparison we briefly sketch the corresponding
considerations for the instance of binary trees. However, {\it mutatis mutandis,}
these are well known and old results, going back to Lynch, Hibbard, Knuth and others, 
see \cite{Hibbard62, Lynch65, Knuth73, Mahmoud92}. 

The recursion for the increasing binary trees is
\begin{equation*}   
a_{n+1}=\sum_{k=0}^n\binom{n}{k}a_ka_{n-k} 
\end{equation*}
with the obvious solution $a_n=n!$. The probability that $j$  lies in a subtree of
size $k$ is
\begin{equation*}   
2\binom{n-1}{k-1}\frac{k!(n-k)!} {(n+1)!}=\frac{2k}{n(n+1)}~.
\end{equation*}
The recursion for the probability generating functions is
\begin{equation*}   
F_{n+1,j}(x)=x\sum_{k=1}^n\frac{2k}{n(n+1)}\sum_{i=1}^k\frac{\binom{j-2}{i-1}\binom{n+1-j}
{k-i}  }{\binom{n-1}{k-1} }F_{k,i}(x)~,
\end{equation*}
and the specialization to $n=j-1$ is
\begin{equation*}   
F_{j}(x)=\frac{2x}{j(j-1)}\sum_{k=1}^{j-1}k\,F_{k}(x)~,
\end{equation*}
 from which we derive
\begin{equation*}   
(j+1)F_{j+1}(x)=(j-1+2x)F_j(x)
\end{equation*}
and thus
\begin{equation*}   
F_j(x)=\prod_{i=2}^j\frac{i+2(x-1)}{i}~.
\end{equation*}
Therefore the expectation is
\begin{equation*}   
D_j=\sum_{i=2}^j\frac{2}{i}=2(H_j-1)~,
\end{equation*}
and the variance is
\begin{equation*}   
V_j=\sum_{i=2}^j\left(\frac2i-\frac{4}{i^2}\right)=2H_j-4H_j^{(2)}+2~.
\end{equation*}
Furthermore, the probability generating function $F_j(x)$ can be written as
\begin{equation*}   
F_j(x)=\frac{1}{j!}(-1)^{j-1}(-2x)^{\underline{j-1}}
=\frac{1}{j!}\sum_{k=0}^{j-1}\stir{j-1}{k}(2x)^k~,
\end{equation*}
whence we find for the probability that the node $j$ lies on level $k$ the quantity
\begin{equation*}   
\frac{2^k}{j!}\stir{j-1}{k}~.
\end{equation*} 




\bibliographystyle{plain} 
\begin{thebibliography}{10}

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

\bibitem{ChenNi94}
W.-C. Chen and W.-C. Ni.
\newblock On the average altitude of heap--ordered trees.
\newblock {\em International Journal of Foundations of Computer Science},
  15:99--109, 1994.

\bibitem{GrKnPa89}
R.~L. Graham, D.~E. Knuth, and O.~Patashnik.
\newblock {\em Concrete Mathematics}.
\newblock Addison Wesley, 1989.

\bibitem{Hibbard62}
T.~N. Hibbard.
\newblock Some combinatorial properties of certain trees with applications to
  searching and sorting.
\newblock {\em Journal of the ACM}, 9(1):13--28, January 1962.

\bibitem{Knuth68}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 1: Fundamental
  Algorithms.
\newblock Addison-Wesley, 1968.
\newblock Second edition, 1973.

\bibitem{Knuth73}
D.~E. Knuth.
\newblock {\em The Art of Computer Programming}, volume 3: Sorting and
  Searching.
\newblock Addison-Wesley, 1973.

\bibitem{Lynch65}
W.~C. Lynch.
\newblock More combinatorial problems on certain trees.
\newblock {\em Computer Journal}, 7:299--302, 1965.

\bibitem{Mahmoud92}
H.~M. Mahmoud.
\newblock {\em Evolution of Random Search Trees}.
\newblock John Wiley, New York, 1992.

\bibitem{Prodinger96a}
H.~Prodinger.
\newblock Depth and path length of heap ordered trees.
\newblock {\em International Journal of Foundations of Computer Science}, 1996
  (to appear).

\bibitem{ProUrb83}
H.~Prodinger and F.J. Urbanek.
\newblock On monotone functions of tree structures.
\newblock {\em Discrete Applied Mathematics}, 5:223--239, 1983.

\end{thebibliography}

%\bibliography{pro_bib}







\end{document}












