%%%%%%%%% %%%%%%%%% Latex2e file for the Appendix to the paper %%%%%%%%% On the Number of Descendants and Ascendants in Random Search Trees %%%%%%%%% by C. Martinez, A. Panholzer, H. Prodinger %%%%%%%%% (10 pages) %%%%%%%%% %%%%%%%%% \documentclass[reqno]{amsart} \usepackage{epsfig} %%%% various specific macros \newcommand{\desc}[2]{D_{#1,#2}} \newcommand{\descrnd}[1]{D_{#1}} \newcommand{\asc}[2]{A_{#1,#2}} \newcommand{\ascrnd}[1]{A_{#1}} \newcommand{\descgf}{\mathsf{D}} \newcommand{\ascgf}{{\mathsf{A}_{z}}} \newcommand{\descrndgf}{\overline{\descgf}} \newcommand{\ascrndgf}{\overline{\ascgf}} \newcommand{\mdesc}[3]{d^{(#1)}_{#2,#3}} \newcommand{\masc}[3]{a^{(#1)}_{#2,#3}} \newcommand{\mdescrnd}[2]{d^{(#1)}_{#2}} \newcommand{\mascrnd}[2]{a^{(#1)}_{#2}} \newcommand{\mdescgf}[1]{\avgdescgf^{(#1)}} \newcommand{\mascgf}[1]{\avgascgf^{(#1)}} \newcommand{\mdescrndgf}[1]{\avgdescrndgf^{(#1)}} \newcommand{\mascrndgf}[1]{\avgascrndgf^{(#1)}} \newcommand{\avgdesc}[2]{d_{#1,#2}} \newcommand{\avgasc}[2]{a_{#1,#2}} \newcommand{\avgdescrnd}[1]{d_{#1}} \newcommand{\avgascrnd}[1]{a_{#1}} \newcommand{\avgdescgf}{\mathcal{D}} \newcommand{\avgascgf}{{\mathcal{A}_{z}}} \newcommand{\avgdescrndgf}{\overline{\avgdescgf}} \newcommand{\avgascrndgf}{\overline{\avgascgf}} \newcommand{\probdescrnd}[2]{p_{#1,#2}} \newcommand{\randomvar}[2]{X_{#1,#2}} \newcommand{\grandrandomvar}[1]{X_{#1}} \newcommand{\gf}{\mathsf{X}} \newcommand{\grandgf}{\overline{\gf}} \newcommand{\moment}[3]{x^{(#1)}_{#2,#3}} \newcommand{\grandmoment}[2]{x^{(#1)}_{#2}} \newcommand{\mgf}[1]{\avggf^{(#1)}} \newcommand{\grandmgf}[1]{\grandavggf^{(#1)}} \newcommand{\avg}[2]{x_{#1,#2}} \newcommand{\grandavg}[1]{x_{#1}} \newcommand{\avggf}{\mathcal{X}} \newcommand{\grandavggf}{\overline{\avggf}} \newcommand{\parz}{\frac{\partial}{\partial z}} \newcommand{\parv}{\frac{\partial^s}{\partial v^s}} \newcommand{\gfz}{{\mathsf{X}_{z}}} \newcommand{\qsmedgf}{\mathsf{C}_{z}} \newcommand{\qsmed}[2]{C_{#1,#2}} \newcommand{\ffact}[2]{#1^{\underline{#2}}} % falling factorial \newcommand{\rfact}[2]{#1^{\overline{#2}}} % raising factorial \renewcommand{\th}[1]{\ensuremath{#1^{\text{th}}}} \newcommand{\ldlm}{[} \newcommand{\rdlm}{]} \newcommand{\Res}[1]{\mathop{\textrm{Res}}\nolimits\left\ldlm#1\right\rdlm} % Residuo \newcommand{\Exp}[1]{\mathop{\mathbb{E}}\nolimits\left\ldlm#1\right\rdlm} % E(X) \newcommand{\Var}[1]{\mathop{\mathbb{V}}\nolimits\left\ldlm#1\right\rdlm} % Var(X) \newcommand{\Prob}[1]{\mathop{\mathbb{P}}\nolimits\left\ldlm#1\right\rdlm} % Prob \setlength{\textwidth}{6in} \setlength{\textheight}{9in} \setlength{\oddsidemargin}{0cm} %0.56cm \setlength{\evensidemargin}{0cm} %0.56 cm \makeatletter \def\ps@headings{\ps@empty \def\@evenhead{\normalfont\scriptsize \hfil \leftmark{}{}\hfil\llap{\thepage}}% \def\@oddhead{\normalfont\scriptsize \hfil \rightmark{}{}\hfil\llap{\thepage}}% \let\@mkboth\markboth} \makeatother \pagestyle{headings} \begin{document} \thispagestyle{empty} \title[{\sc the electronic journal of combinatorics 5 (1998), \#R20 (appendix) \hfill}]{} \author[]{} \maketitle \vspace*{-1in} \section*{Appendix to the article ``On the number of Descendants and Ascendants in Random Search Trees'' by C. Mart\'{\i}nez, A. Panholzer, and H. Prodinger} \appendix \section{Polynomials} % \label{app:polynomials} We collect here various polynomials in two and three variables that appear as factors or terms in the explicit form of some the generating functions studied in this paper. \subsection{The polynomials $A_i(z,u,v)$} \mbox{} \bigskip \pagestyle{myheadings} $\triangleright \qquad A_0(z,u,v) =\dfrac1{70} \Bigl(3410v^7u^6z^6+7356u^4v^4z+900v^8u^8z^7-1316u^9v^7z^5%\\ -1148u^9v^8z^6-880v^7u^8z^7-210u^9v^8z^4-5874v^7u^5z^5%\\ +4886v^7u^8z^4+4080v^4u^6z-2564v^8u^8z^6-4648v^5u^3z%\\ +140u^{10}v^8z^7+3822u^5v^8z^5-2378u^3v^3z-680u^9v^7z^7%\\ +7356v^4u^5z-120vu^2z-880v^7u^7z^7+1388v^7u^9z^6-490v^9u^5z%\\ +1042v^4u^2z+3484u^7v^7z^6+120u^5z^2+60zu^3-120z^2u^4-140u^6v^7%\\ -140u^4v^8+70u^5v^8+140u^6v^6+70v^2u^3-140u^5v^4-140v^6u^4%\\ +140u^5v^3-140u^4v^4-140v^4u^3-140v^2u^4+60uv^2z+10780v^7u^6z^2%\\ -130v^8u^8z^8-3920u^6v^8z^2+4080u^3v^4z-5874u^8v^7z^5-1378v^5u^2z%\\ -4648v^5u^6z-9220v^5u^5z-9220v^5u^4z+12362v^7u^5z^4+60v^7u^8z^8%\\ -80v^8u^9z^8+130u^9v^7z^8-45u^{10}v^8z^8+3410u^8v^7z^6+3822u^8v^8z^5%\\ -8606v^7u^7z^5-70v^9u^9z^4-84v^8u^{10}z^6+1512v^9u^7z^6+868v^9u^8z^6%\\ +6986v^8z^5u^6+1106u^9v^8z^5+868v^9u^6z^6-400v^9u^7z^7+900v^8u^7z^7%\\ -2564v^8u^6z^6-2590v^9u^7z^5+70v^9u^8z^8-3560v^8u^7z^6-826v^9u^8z^5%\\ -2590v^9u^6z^5-826v^9u^5z^5-2800v^9u^5z^3-400v^9u^8z^7-5v^9u^{10}z^8%\\ -100v^9u^9z^7+1806v^5u^6z^6-2370v^5u^5z^5-520u^3v^2z^2+210uv^6z^4%\\ -14104v^4u^5z^2+56u^{10}v^7z^5-220v^5z^7u^6-1612u^4v^2z^2+110v^3u^2z^2%\\ -1612u^6v^2z^2-1246v^6u^9z^6+8400u^6v^5z^4+140u^5v^7+140v^3u^3-140v^6u^3%\\ +140v^4u^2+70v^4u-140v^3u^2-140u^5v^5-140v^5u-140v^5u^3-140u^5v^6%\\ +140u^6v^4+140v^7u^3+560v^5u^4-140v^3u^6+70v^2u^5+60u^6z+140v^6u^2%\\ -140v^7u^2+70uv^6+70v^8u^3-140v^5u^7+70u^7v^4+42v^9u^9z^5-126v^8u^{10}z^5%\\ +14v^9u^{10}z^5+84v^9u^9z^6+30v^9u^9z^8-28v^9u^{10}z^6-4062v^3u^4z%\\ -4062v^3u^5z+7732u^5v^6z+770u^6v^8z+7732v^6u^4z+11760v^7u^5z^2%\\ -4620v^7u^5z-140v^9u^7z^2-4620v^7u^4z+6986v^8u^7z^5+1890v^8u^5z%\\ +1534v^2u^4z-8606v^7u^6z^5+1960v^9u^5z^2-2800v^9u^6z^3+9240v^8u^6z^3%\\ -1260v^8u^7z^2-15232u^6v^7z^3+12362v^7u^7z^4-3038v^8u^8z^4-7000v^8u^5z^2%\\ +2170v^9u^5z^4+3780v^9u^6z^4-7490v^8u^5z^4+70v^9u^6z-580u^2v^3z%\\ +360u^2v^2z-15232v^7u^5z^3-700v^9u^7z^3-180vzu^3+746v^2zu^3%\\ +122v^4zu-180v^3uz+9240v^8u^5z^3+980v^8u^8z^3+210v^9u^8z^4+2170v^9u^7z^4%\\ +13888v^7u^6z^4-7490v^8u^7z^4-10724v^8u^6z^4+840v^9u^6z^2-9464v^7u^7z^3%\\ -2520v^7u^6z+4252v^6u^6z-1148u^5v^8z^6+2800u^3v^7z^2+126v^7u^2z^5%\\ -3038u^4v^8z^4+1106u^4v^8z^5+826u^2v^6z-2520v^7u^3z+10v^8u^5z^8%\\ +500u^6v^8z^7-680v^7u^6z^7+140v^8u^5z^7+20v^9u^5z^7-28v^9u^4z^6-210uv^6z%\\ -1316v^7u^4z^5-100v^7u^5z^7+25v^7u^6z^8+112v^7u^4z^6-126v^8u^3z^5%\\ +56v^7u^3z^5+42v^9u^4z^5+14v^9u^3z^5-5v^9u^6z^8-84v^8u^4z^6-84v^7u^3z^6%\\ -210v^7u^2z^4-210v^8u^3z^4+56v^8u^3z^6-28v^8u^2z^5-45v^8u^6z^8%\\ +1388v^7u^5z^6-70v^9u^3z^4-180u^6vz-140u^2v^8z+70uv^7z+280u^2v^8z^2%\\ -70u^2v^7z+140z^4u^2v^8+126v^5uz+140v^7u^2z^3-2378u^6v^3z+448v^7u^3z^4%\\ +746u^6v^2z-300u^5vz+4886v^7u^4z^4-100v^9u^6z^7+84v^9u^5z^6+140v^9u^3z^3%\\ +210v^9u^4z^4+980v^8u^3z^3-1624v^7u^3z^3+1534u^5v^2z-300u^4vz-700v^9u^4z^3%\\ -1260u^3v^8z^2-140u^3v^9z^2+4252v^6u^3z+20v^7u^4z^7+4340v^8u^4z^3%\\ -9464v^7u^4z^3+872v^5u^8z^4+176v^4u^8z^4+7824v^5u^7z^4-100v^7u^{10}z^7%\\ +6554u^7v^6z^5+3998u^8v^6z^5+14940u^4v^5z^2+1520v^3u^6z^4+2246v^4u^7z^5%\\ -9220u^4v^4z^2-46u^8v^4z^5+320v^4z^7u^7+1280v^6u^9z^5+380v^6u^9z^7%\\ -2804u^5v^3z^3+1806v^5u^8z^6+540u^5vz^2+120v^6u^{10}z^7-526v^5u^9z^6%\\ -286v^4u^8z^6-140v^7uz^2+840u^4v^9z^2+770u^3v^8z-13520u^6v^5z^3%\\ +14940v^5u^6z^2+252u^2v^6z^2+420v^6uz^2+7880v^4u^5z^3+9428v^6u^7z^3%\\ -1344u^9v^6z^3+412u^8v^5z^3+2940v^6u^8z^3-5014v^6u^8z^4-2416v^4u^7z^4%\\ +1302v^6u^{10}z^4+2246v^4z^5u^6-1834v^6z^6u^6+460v^3u^5z^4-5200v^4u^6z^4%\\ -70v^7u^7z+2800v^7u^7z^2+1890v^8u^4z+448v^7u^9z^4-210v^7u^{10}z^4%\\ -2416v^4u^5z^4-3920v^8u^4z^2+336v^6u^9z^4-1876v^5u^9z^4+1560v^5u^7z^6%\\ -490v^9u^4z-8008v^5u^7z^3+2948u^7v^4z^3+540u^5z^3v^2+150u^4z^2v+70v^9u^3z%\\ -5964v^6u^3z^2-2804u^6v^3z^3+7880u^6v^4z^3+4856v^3u^4z^2+4336v^5u^3z^2%\\ +6552u^5v^3z^2+252v^6u^8z^2+4336v^5u^7z^2-1378v^5u^7z-12914v^6u^4z^2%\\ -12914v^6u^6z^2+17336v^5u^5z^2+1042u^7v^4z-3634u^7v^4z^2-580u^7v^3z%\\ +1658u^7v^3z^2+360u^7v^2z+196u^8v^5z^2-19028u^5v^6z^2-9220u^6v^4z^2%\\ +4856u^6v^3z^2-2096u^5v^2z^2-4366v^5z^5u^6+432v^6u^{10}z^6+3998v^6z^5u^5%\\ +1812v^5z^5u^4+500v^8u^9z^7+112u^{10}v^7z^6-220u^9v^5z^7+308v^4z^6u^5%\\ -100v^4z^7u^6+872v^5u^4z^4-1246v^6z^6u^5+6554v^6z^5u^6+17116v^6u^6z^3%\\ +1280v^6z^5u^4+7824v^5u^5z^4-700v^4z^5u^4-46v^4z^5u^5-286v^4z^6u^6%\\ -1344v^6u^{10}z^5-9772u^7v^6z^4-1834u^8v^6z^6-546v^6z^5u^2+460u^5v^5z^7%\\ -70v^7uz^4-952v^5u^4z^6-4366u^7v^5z^5+120v^6u^5z^7-2370u^8v^5z^5%\\ -1344u^3v^6z^5-300u^4v^6z^7+1302u^2v^6z^4+588u^3v^6z^6+1148u^3v^5z^5%\\ +432u^4v^6z^6+10780v^7u^4z^2-13724u^6v^6z^4-2648u^7v^6z^6-526v^5z^6u^5%\\ -5964v^6u^7z^2+1812u^9v^5z^5-34v^4z^2u^2-1396v^4u^7z^6+320v^4u^8z^7%\\ +4340v^8u^7z^3-3634v^4u^3z^2+196v^5u^2z^2+2940u^3v^6z^3+412v^5u^3z^3%\\ -1344v^6u^2z^3-8008u^4v^5z^3-13520u^5v^5z^3-88v^4u^3z^3-856v^3u^4z^3%\\ +9428v^6u^4z^3-1624v^7u^8z^3+17116v^6u^5z^3+1658u^3v^3z^2-500v^5u^8z^7%\\ +140v^7u^9z^3-420v^5z^2u+140v^7uz^3-280u^2v^8z^3-420v^6uz^3+336u^3v^6z^4%\\ -1876v^5u^3z^4-5014v^6u^4z^4-910v^5z^4u^2+896v^5z^3u^2+2948v^4u^4z^3%\\ -9772v^6u^5z^4+826v^6u^7z+980v^4u^3z^4+176v^4u^4z^4+126v^5u^8z+122u^8v^4z%\\ -180u^8v^3z+60u^8v^2z-420u^9v^5z^2+420v^6u^9z^2+210v^6u^{11}z^4+70v^7u^8z%\\ -70v^7u^{11}z^4-420u^{10}v^6z^3-120u^7vz-280v^8u^9z^3+140v^9u^8z^3-28v^8u^{11}z^5%\\ +20v^9u^{10}z^7+56v^8u^{11}z^6+25u^{10}v^7z^8+10u^{11}v^8z^8-40u^{11}v^8z^7+140u^{10}v^8z^4%\\ +70u^7v^6-5v^7u^4z^8+20u^6z^7v^2+14v^7u^{12}z^5+20v^7u^{12}z^7+15v^6u^{12}z^8%\\ -5v^7u^{12}z^8-20v^4u^{12}z^7+28v^4u^{12}z^6+60v^5u^{12}z^7+5v^4u^{12}z^8-15v^5u^{12}z^8%\\ -42v^6u^{12}z^5+84v^6u^{12}z^6-28v^7u^{12}z^6-60v^6u^{12}z^7+42v^5u^{12}z^5%\\ +140v^4u^9z^2+420v^5u^{10}z^3-210v^5u^{11}z^4-14v^4u^{12}z^5-84v^5u^{12}z^6%\\ -140v^4u^{10}z^3+70v^4u^{11}z^4+40u^{11}v^3z^7-10v^3z^8u^{11}+5v^2z^8u^{10}-56u^{11}v^3z^6%\\ +280u^9v^3z^3-140u^{10}v^3z^4+70z^4u^9v^2+28u^{10}z^6v^2-20u^{10}z^7v^2-14u^{10}z^5v^2%\\ +28u^{11}v^3z^5-210v^6u^8z+240u^7vz^2-120u^8z^2v^2-140z^3u^8v^2+140v^7u^{10}z^3%\\ -140v^7u^9z^2-60u^5vz^3+150u^6vz^2+240u^3vz^2-520u^7z^2v^2+98z^5u^8v^2%\\ +260z^3u^7v^2+70z^4u^8v^2+14z^5u^7v^2-84z^6u^8v^2-210z^4u^7v^2+28u^9z^6v^2%\\ +20u^9z^7v^2-98u^9z^5v^2+238u^{10}v^3z^5-70u^8v^3z^4+154u^9v^3z^5-140u^{10}v^3z^6%\\ +80u^8v^3z^3-350u^9v^3z^4-856u^7v^3z^3+540u^6v^2z^3+460u^7v^3z^4+20u^6v^2z^4%\\ +70u^8v^3z^5-28u^9v^3z^6-550v^3z^5u^7+14v^2z^5u^6+28v^3z^6u^8+56v^2z^6u^7%\\ +20u^{10}v^3z^7+20v^3z^7u^9+5v^3z^8u^{10}-10v^2z^8u^9+98v^2z^5u^5-84v^2z^6u^6%\\ -210v^2z^4u^5+10v^2z^8u^8-550v^3u^6z^5+392v^3u^7z^6+70v^3z^5u^5+28v^3z^6u^6%\\ -80v^3u^8z^7-10v^3u^9z^8-80v^3z^7u^7+30v^3z^8u^8-88v^4u^8z^3+308v^4u^9z^6%\\ +392v^4u^{10}z^6-100v^4u^9z^7-700v^4u^9z^5-644v^4u^{10}z^5-100v^4u^{10}z^7%\\ -700v^4u^9z^3+490v^4u^{10}z^4+980v^4u^9z^4+5v^4z^8u^{10}-34v^4u^8z^2+1148v^5u^{10}z^5%\\ +896v^5u^9z^3-910v^5u^{10}z^4-952v^5u^{10}z^6-182v^4u^{11}z^5-364v^5u^{11}z^6%\\ -100v^4u^{11}z^7+434v^5u^{11}z^5+196v^4u^{11}z^6+140v^5u^{11}z^7+20v^4u^{11}z^8%\\ +460v^5u^{10}z^7-20v^5u^{11}z^8-95v^5z^8u^{10}+20v^4z^8u^9+520v^6u^8z^7%\\ -100v^4z^8u^8+120v^5u^9z^8-500v^5z^7u^7+20v^5z^8u^8-75v^6z^8u^{10}-546v^6u^{11}z^5%\\ +588v^6u^{11}z^6-84v^7u^{11}z^6-300v^6u^{11}z^7+126v^7u^{11}z^5+20v^7u^{11}z^7%\\ +60v^6u^{11}z^8-20v^6z^8u^9+520v^6z^7u^7-80v^6z^8u^8+14v^7uz^5-182v^4u^2z^5%\\ -644u^3v^4z^5-364v^5u^3z^6+196v^4u^3z^6+420uv^5z^3+490v^4u^2z^4-14v^4z^5u%\\ +70v^4uz^4-84v^5u^2z^6-700u^2v^4z^3-140uv^4z^3+140uv^4z^2+42v^5z^5u%\\ -40v^8u^4z^7+140u^4v^5z^7-42v^6z^5u+434u^2v^5z^5+84u^2v^6z^6+28v^4u^2z^6%\\ -20v^4u^3z^7+60v^5u^3z^7-120u^2z^2v^2-140u^3z^3v^2-14z^5u^3v^2+70z^4u^3v^2%\\ +28u^4z^6v^2+28u^5z^6v^2-98u^4z^5v^2-20u^5z^7v^2+260u^4z^3v^2+70u^4z^4v^2%\\ +20v^7u^3z^7-28u^2v^7z^6-210uv^5z^4-350u^3v^3z^4+154u^4v^3z^5-28u^5v^3z^6%\\ +80u^3v^3z^3-70u^4v^3z^4+280u^2v^3z^3-140u^2v^3z^4+238u^3v^3z^5-140u^4v^3z^6%\\ +28v^3z^5u^2-56v^3z^6u^3+20u^6v^3z^7-10u^7v^3z^8+5u^6v^2z^8+20u^5v^3z^7%\\ +5u^6v^3z^8+40v^3z^7u^4-10v^3z^8u^5-10u^7z^8v^2+392v^4u^4z^6-100v^4u^4z^7%\\ -100v^4u^5z^7+20v^4z^8u^5+120v^5u^7z^8+5v^4u^6z^8-95v^5u^6z^8-20v^5z^8u^5%\\ +5v^4z^8u^4+20v^4u^7z^8-60v^6u^3z^7-15v^5u^4z^8+60v^6z^8u^5+380v^6u^6z^7%\\ +130v^7u^7z^8-75v^6u^6z^8-20v^6u^7z^8+15v^6z^8u^4+30v^9u^7z^8-80v^8u^7z^8%\\ -120u^6z^2+110u^8z^2v^3-60z^3u^6v+280v^8u^8z^2-140v^8u^7z\Bigr)$ \bigskip $\triangleright \qquad A_1(z,u,v)=\dfrac{6}{35}(1-z)^3\bigl(5z^3u^3+5z^2u^3-20u^2z^2 +3zu^3-16u^2z+28uz+u^3-14-6u^2+14u\bigr)(2uv-u-1)u^2v^4$ \bigskip $\triangleright \qquad A_2(z,u,v) = -\dfrac{6}{35} v^4 (u-2v+1)(1-uz)^3\bigl(-5z^3u^3+20z^2u^3 -5u^2z^2-28zu^3+16u^2z-3uz+14u^3-14u^2+6u-1\bigr)$ \bigskip $\triangleright \qquad A_3(z,u,v) = \dfrac{1}{35}\Bigl(-672v^7u^6z^6-3444u^4v^4z+720v^8u^8z^7%\\ -600v^7u^8z^7+1848v^7u^5z^5-2520v^4u^6z-1008v^8u^8z^6+1260v^5u^3z%\\ +504u^5v^8z^5-6888v^4u^5z-240v^7u^7z^7+2016u^7v^7z^6+630u^4v^8+4704u^5v^4%\\ +5040v^6u^4-3564u^5v^3+5166u^4v^4-2394u^4v^3+1848v^4u^3+468v^2u^4%\\ -180v^8u^8z^8-252u^3v^4z-420u^8v^7z^5+1512v^5u^6z+6552v^5u^5z+6048v^5u^4z%\\ -1680v^7u^5z^4+150v^7u^8z^8+840u^8v^7z^6+504u^8v^8z^5-3528v^7u^7z^5%\\ +84v^{10}z^5u^7+1680v^9u^7z^6+336v^9u^8z^6+6552v^8z^5u^6-168v^{10}u^7z^6%\\ +2520v^9u^6z^6-720v^9u^7z^7+1080v^8u^7z^7-2016v^8u^6z^6+840v^{10}u^6z^5%\\ -1848v^9u^7z^5+60v^9u^8z^8-3528v^8u^7z^6-168v^9u^8z^5-4620v^9u^6z^5%\\ -3864v^9u^5z^5-5040v^9u^5z^3-240v^9u^8z^7+60u^6-420u^5v^7-378v^3u^3%\\ +3780v^6u^3+126v^4u^2-4032u^5v^5-3654v^5u^3-3150u^4v^7+2520u^5v^6+1050u^6v^4%\\ -630u^6v^5-2310v^7u^3-630v^5u^2-6300v^5u^4+1062v^2u^6-1332v^3u^6+1512v^2u^5%\\ +630u^2v^8+1260v^6u^2-1260v^7u^2-270u^5v-420u^6v+1260v^8u^3+126v^5u^7%\\ -252u^7v^4-162u^7v^2+756v^3u^4z+4032v^3u^5z-5040u^5v^6z-5040v^6u^4z%\\ +4200v^7u^5z^2+840v^7u^5z+3360v^7u^4z+4788v^8u^7z^5-1512v^7u^6z^5%\\ +1680v^9u^5z^2-1680v^9u^6z^3+5040v^8u^6z^3-4200u^6v^7z^3+2100v^7u^7z^4%\\ -5040v^8u^5z^2+6300v^9u^5z^4+4200v^9u^6z^4-5040v^8u^5z^4-1680v^7u^5z^3%\\ +7560v^8u^5z^3+840v^9u^7z^4+5040v^7u^6z^4-2520v^8u^7z^4-420v^{10}u^6z^4%\\ -8820v^8u^6z^4+1008u^5v^8z^6+2520u^4v^8z^4-2016u^4v^8z^5+2520v^7u^3z%\\ +360v^7u^6z^7-360v^8u^5z^7+840v^{10}u^4z^5-168v^9u^3z^6-336v^9u^4z^6%\\ +252v^7u^4z^5-252v^8u^3z^5-168v^{10}u^4z^6-30v^9u^5z^8+84v^{10}u^3z^5%\\ -336v^9u^4z^5+672v^9u^3z^5+120v^9u^4z^7+84v^9u^2z^5+30v^9u^6z^8+504v^8u^4z^6%\\ +1260v^8u^3z^4+90v^8u^6z^8-504v^7u^5z^6-420v^9u^2z^4-840v^9u^3z^4+540u^6vz%\\ +3096u^6v^3z-2088u^6v^2z-1260v^7u^4z^4-600v^9u^6z^7+1008v^9u^5z^6%\\ -420v^{10}z^4u^3-1680v^{10}u^4z^4-672v^{10}z^6u^5+840v^{10}u^3z^3%\\ +2520v^9u^4z^4+1512v^{10}u^5z^5-2520v^8u^3z^3+840v^9u^2z^3-840v^9u^2z^2%\\ +420v^9u^2z+120v^{10}z^7u^5-936u^5v^2z-4200v^9u^4z^3+2520u^3v^8z^2%\\ +840u^3v^9z^2-2520v^6u^3z+2520v^7u^4z^3+3360u^4v^9z^2-2520u^3v^8z%\\ +1260v^8u^4z-2520v^8u^4z^2-840v^9u^4z-420v^9u^3z-252v^5u^7z+420u^7v^4z%\\ -432u^7v^3z-36u^7v^2z-2520v^7u^4z^2+342u^7v^3-210v^9u^3-30u^8+30u^7%\\ +120u^7v^{10}z^7-840u^4v^{10}z^2+420u^3v^{10}z+840u^5v^{10}z^3%\\ +1680u^4v^{10}z^3-840u^3v^{10}z^2+360u^8v^2z+300u^7vz-1680u^5v^{10}z^4%\\ -252u^8v^3z-240u^8vz-210u^2v^9-672u^6v^{10}z^6-30u^6v^{10}z^8-30u^7v^{10}z^8%\\ +240u^6v^{10}z^7+84u^8v^4z-30u^7v+120u^8v-90v^7u^7z^8+120v^9u^7z^8%\\ -90v^8u^7z^8-120u^7z+60u^8z+126u^8v^3-180u^8v^2-42u^8v^4\Bigr)$ \bigskip $\triangleright \qquad A_4(z,u,v) = \dfrac{1}{35}\Bigl(30-840v^7u^6z^6+6888u^4v^4z-1080v^8u^8z^7%\\ -252u^9v^7z^5-1008u^9v^8z^6+240v^7u^8z^7-1260u^9v^8z^4+420v^7u^5z^5%\\ +1260v^7u^8z^4+252v^4u^6z+2016v^8u^8z^6-1512v^5u^3z+360u^{10}v^8z^7%\\ -504u^5v^8z^5-3096u^3v^3z-360u^9v^7z^7+3444v^4u^5z-300vu^2z+600v^7u^7z^7%\\ +504v^7u^9z^6+840v^9u^5z-420v^4u^2z-2016u^7v^7z^6+420u^2v+30uv-60uz%\\ +1260u^6v^7-630u^4v^8-630u^6v^8-1260u^5v^8-1260u^6v^6+210v^9u^5-1512v^2u^3%\\ -1848u^5v^4-5040v^6u^4+378u^5v^3-5166u^4v^4+2394u^4v^3-4704v^4u^3-468v^2u^4%\\ -360uv^2z+240uvz+2520v^7u^6z^2+180v^8u^8z^8+2520u^6v^8z^2+2520u^3v^4z%\\ -1848u^8v^7z^5+252v^5u^2z-1260v^5u^6z-6048v^5u^5z-6552v^5u^4z-420v^9u^7z%\\ -2100v^7u^5z^4-150v^7u^8z^8+90v^8u^9z^8+90u^9v^7z^8-90u^{10}v^8z^8%\\ +672u^8v^7z^6-504u^8v^8z^5+1512v^7u^7z^5+1680v^{10}u^8z^4+840v^9u^9z^4%\\ -840v^{10}z^5u^7-504v^8u^{10}z^6-1680v^9u^7z^6-2520v^9u^8z^6-4788v^8z^5u^6%\\ +2016u^9v^8z^5-240v^{10}u^9z^7+672v^{10}u^8z^6+168v^{10}u^7z^6+420v^{10}u^9z^4%\\ -840v^{10}u^9z^5-336v^9u^6z^6+240v^9u^7z^7+420v^9u^{10}z^4-720v^8u^7z^7%\\ +1008v^8u^6z^6-84v^{10}u^6z^5+4620v^9u^7z^5-60v^9u^8z^8+3528v^8u^7z^6%\\ -120v^{10}u^8z^7+3864v^9u^8z^5-840v^{10}u^8z^3+840v^{10}u^7z^2-420v^{10}u^6z%\\ +1848v^9u^6z^5+168v^9u^5z^5+30v^{10}u^9z^8-1512v^{10}u^8z^5+840v^9u^8z^2%\\ +1680v^9u^5z^3+720v^9u^8z^7-840v^9u^9z^3+30v^9u^{11}z^8-30v^9u^{10}z^8%\\ +30v^{10}u^{10}z^8+600v^9u^9z^7+180v^2-120v+42v^4-126v^3+120u^2z-60u^2%\\ -30u+2310u^5v^7-342v^3u+3564v^3u^3+162v^2u-1062u^2v^2-2520v^6u^3+210v^9u^6%\\ +270u^3v-1050v^4u^2+252v^4u+1332v^3u^2+3654u^5v^5-126v^5u+4032v^5u^3%\\ +3150u^4v^7-3780u^5v^6-126u^6v^4+630u^6v^5+420v^7u^3+630v^5u^2+6300v^5u^4%\\ +672v^{10}u^9z^6+336v^9u^9z^5-84v^{10}u^{10}z^5-120v^9u^{11}z^7+252v^8u^{10}z^5%\\ -672v^9u^{10}z^5+168v^9u^{11}z^6-84v^9u^{11}z^5-1008v^9u^9z^6-120v^{10}u^{10}z^7%\\ -120v^9u^9z^8+168v^{10}u^{10}z^6+336v^9u^{10}z^6-4032v^3u^4z-756v^3u^5z%\\ -1680v^{10}u^7z^3+840v^{10}u^6z^2+5040u^5v^6z+2520u^6v^8z+5040v^6u^4z%\\ -4200v^7u^5z^2-3360v^7u^5z-840v^9u^7z^2-840v^7u^4z-6552v^8u^7z^5-1260v^8u^5z%\\ +936v^2u^4z+3528v^7u^6z^5-1680v^9u^5z^2-840v^{10}u^6z^3+5040v^9u^6z^3%\\ -7560v^8u^6z^3-2520v^8u^7z^2+1680u^6v^7z^3+1680v^7u^7z^4-2520v^8u^8z^4%\\ +5040v^8u^5z^2-840v^9u^5z^4-4200v^9u^6z^4+2520v^8u^5z^4+420v^9u^6z+432u^2v^3z%\\ +36u^2v^2z+4200v^7u^5z^3+4200v^9u^7z^3-540vzu^3+2088v^2zu^3-84v^4zu+252v^3uz%\\ -5040v^8u^5z^3+2520v^8u^8z^3-2520v^9u^8z^4-6300v^9u^7z^4+1680v^{10}u^7z^4%\\ -5040v^7u^6z^4+5040v^8u^7z^4+420v^{10}u^6z^4+8820v^8u^6z^4-3360v^9u^6z^2%\\ -2520v^7u^7z^3-2520v^7u^6z+2520v^6u^6z\Bigr)$ \subsection{The polynomials $B_i(z,u)$} \mbox{} \bigskip $\triangleright \qquad B_0(z,u) = 10uz-120u^2z+1140u^2z^2-8190u^5z^2- 4236z^5u^6-1980z^3u^5-680z^4u^6-980 u^4z-605z^4u^4-4826z^5u^5+4354z^6u^6-5020z^3u^4+8585z^4u^5+500zu^3+ 2980z^3u^3-4140z^2u^3+8790z^2u^4- 1470u^6-490u^2+1470u^3-2450u^4+70u+980 u^6z+2450u^5+8190u^6z^2+1040u^9z^7+ 960u^{10}z^7-1040u^7z^7+518u^7z^6+490 u^7-70u^8+4236u^8z^5+605u^9z^4-518 u^8z^6-4354u^9z^6-55u^8z^8-8585u ^8z^4+4826u^9z^5+112u^{10}z^6-500u^7 z+55u^9z^8-390u^{10}z^8+490u^{10}z^4+ 5020u^8z^3-8790u^7z^2+4140u^8z^2- 2980u^9z^3+150u^{11}z^8+680u^7z^4-1694 u^{10}z^5-440u^{11}z^7+196u^{11}z^6+462u^{11}z^5+1980u^7z^3-112u^5z^6-140uz^2 +14u^2z^5+1694u^4z^5+40u^5z^8-960 u^6z^7+440u^5z^7-5u^4z^8-28u^2 z^6+140u^3z^6+20u^3z^7-70uz^4+14z^5u-140u^4z^7-196u^4z^6-150u^6z^8 -462u^3z^5+350u^2z^4-490u^3z^4+140 uz^3-980u^2z^3-20u^{13}z^7+140u^{10}z^2-140u^{11}z^3+70u^{12}z^4+5u^{13}z^8 +28u^{13}z^6-14u^{13}z^5-40u^{12}z^8+140u ^{12}z^7-140u^{12}z^6-350u^{11}z^4 -14u^{12}z^5-10u^9z+120u^8z+390u^7z^8-1140u^9z^2+980u^{10}z^3$ \bigskip $\triangleright \qquad B_1(z,u)= -6(1+u)u^5(1-z)^3 \Bigl(5z^3u^3+5z^2u^3-20u^2z^2+3u^3z-16u^2z+28uz+u^3-6u^2+14u-14 \Bigr)$ \bigskip $\triangleright \qquad B_2(z,u)= 6(1+u) \Bigl( 5z^3u^3-20z^2u^3+ 5u^2z^2-16u^2z+3uz+28u^3z-6u-14u^3 +14u^2+1 \Bigr) (1-uz)^3$ \subsection{The polynomials $C_i(z,u)$} \mbox{} \bigskip $\triangleright \qquad C_0(z,u) = 950uz-6360u^2z+5120u^2z^2+10850u^5z^2-58440z^5u^6-39420z^3u^5+32210z^4u^6 -22540u^4z+275z^4u^4-38218z^5u^5+38066z^6u^6-32540z^3u^4+69865z^4u^5+17260zu^3 +17660z^3u^3-16280z^2u^3+29070z^2u^4+22540u^6z-10850u^6z^2+13960u^9z^7 +7320u^{10}z^7-13960u^7z^7+21574u^7z^6+58440u^8z^5-275u^9z^4-21574u^8z^6 -38066u^9z^6+1600u^8z^8-69865u^8z^4+ 38218u^9z^5-1540u^{10}z^6-17260u^7z-1600u^9z^8-2715u^{10}z^8 +3710u^{10}z^4+32540u^8z^3-29070u^7z^2+16280u^8z^2-17660u^9z^3+885u^{11}z^8 -32210u^7z^4-9352u^{10}z^5-2680u^{11}z^7+1484u^{11}z^6+2310u^{11}z^5 +39420u^7z^3+1540u^5z^6-700uz^2+28u^2z^5+9352u^4z^5+215u^5z^8 -7320u^6z^7+2680u^5z^7-25u^4z^8-140u^2z^6+784u^3z^6+100u^3z^7-350uz^4 +70z^5u-760u^4z^7-1484u^4z^6-885u^6z^8-2310u^3z^5+1960u^2z^4-3710u^3z^4 +700uz^3-5320u^2z^3-100u^{13}z^7+700u^{10}z^2-700u^{11}z^3+350u^{12}z^4 +25u^{13}z^8+140u^{13}z^6-70u^{13}z^5-215u^{12}z^8+760u^{12}z^7 -784u^{12}z^6-1960u^{11}z^4-28u^{12}z^5-950u^9z+6360u^8z+2715u^7z^8 -5120u^9z^2+5320u^{10}z^3$ \bigskip $\triangleright \qquad C_1(z,u) = 18480u^5z^2-36960u^6z^3-18480z^5u^6- 18480z^3u^5+36960z^4u^6+3024u^4z-1848z^5u^5+3696z^6u^6+9240z^4u^5-504zu^3 -1260u^6+252u^2-1260u^3+2268u^4+6384u^6z-16800u^5z+588u^5+18480u^6z^2-2640 u^9z^7-2640u^7z^7+14784u^7z^6+1212u^7-600u^8+120u^9-18480u^8z^5+14784u^8 z^6+3696u^9z^6+660u^8z^8+9240u^8z^4-1848u^9z^5-3864u^7z+660u^9z^8+36960 u^7z^4-5280u^8z^7-18480u^7z^3-33264u^7z^5-240u^9z+1440u^8z$ \bigskip $\triangleright \qquad C_2(z,u) = -120+240uz-1440u^2z-18480u^5z^2+36960u^6z^3+18480z^5u^6+18480z^3u^5-36960z^4 u^6-6384u^4z+1848z^5u^5-3696z^6u^6-9240z^4u^5+3864zu^3+1260u^6-1212u^2+ 1260u^3-588u^4+600u-3024u^6z+16800u^5z- 2268u^5-18480u^6z^2+2640u^9z^7+2640u^7z^7-14784u^7z^6-252u^7+18480u^8z^5 -14784u^8z^6-3696u^9z^6-660u^8z^8- 9240u^8z^4+1848u^9z^5+504u^7z-660u^9z^8 -36960u^7z^4+5280u^8z^7+18480u^7z^3+33264u^7z^5 $ \subsection{The polynomials $D_i(z,u)$} \mbox{} \bigskip $\triangleright \qquad D_0(z,u) = -\dfrac{u}{350}\Bigl( -1960uz^3-19000u^3z^3+19050u^3z^2- 84uz^5+370z+840uz^4+4844u^3z^5+400u^3z ^4+2520u^9z^4+1960u^9z^3+140u^9z^2- 8900u^8z^3-1650u^8z^2+336u^2z^6-644u ^2z^5-2520u^2z^4+8900u^2z^3-7650u^2z ^2-28uz^6+2450u-1008u^3z^6+7650u^7z^2+ 1650uz^2+20u^2z^7-350-7350u^2+7350u^5-2450 u^6-140z^2-70z^4+140z^3+14z^5-2340uz+ 5900u^2z-6860u^3z+6860u^5z-5900u^6z+2340u^ 7z-370u^8z-20790u^4z^2+5840u^4z^3+22630 u^4z^4-15546u^4z^5+20790u^5z^2-17040u^5z^4 -1528u^5z^5-19050u^6z^2-5840u^6z^ 3+17040u^6z^4-400u^8z^4+15546u^8z^5- 4844u^9z^5+12250u^3-12250u^4+350u^7+19000 u^7z^3-22630u^7z^4+1 \Bigr)$ %$\triangleright \qquad D_0(z,u) = %\dfrac{(1-u)^8 (u^4-15u^3+80u^2-240u+36 )u}{350}+ %\dfrac{u(1-u)^7(u^5-15u^4+80u^3-240u^2-24u+150)}{175}(1-z) %-\dfrac{u^2 (5u-9)(1-u)^6}{7}(1-z)^2 %-\dfrac{4u^3 (1+u)(1-u)^5}{7}(1-z)^3 %+\dfrac{13u^4 (1+u)(1-u)^4}{7} (1-z)^4 %-\dfrac{u(1-u)^3 %(7u^9-105u^8+560u^7-1680u^6+52u^5-2412u^4+1680u^3-560u^2+105u-7)}{175} %(1-z)^5 %-\dfrac{2u^2 %(1-u)^2(u^9-15u^8+80u^7-240u^6+101u^5-251u^4+240u^3-80u^2+15u-1)}{25} %(1-z)^6 %-\dfrac{(1-u)(2u^9-30u^8+160u^7-480u^6+292u^5-412u^4+480u^3-160u^2+30u-2)u^3}{35} %(1-z)^7 %+\dfrac{(1-u)(1-14u^7-14u+66u^2-174u^3+u^8+66u^6-174u^5+2u^4)u^4}{70} %(1-z)^8$ \bigskip $\triangleright\qquad D_1(z,u) = \dfrac{-6u}{35}\Bigl( -7+42u-98u^2-98u^5+82u^6+14uz-98u^2z+294u^3z-630u^4z+434u^5z-238u^6z +74u^7z-10u^8z+280u^4z^2-280u^4z^3+140u^4z^4-28u^4z^5+280u^5z^2-560u^5z^3+ 560u^5z^4-280u^5z^5-280u^6z^3+560u^6z^4-504u^6z^5-28u^8z^5+98u^3+ 28u^4-32u^7+5u^8+140u^7z^4-280u^7z^5+224 u^7z^6+224u^6z^6+56u^8z^6-80u^7z^7 -40u^8z^7+10u^8z^8+56u^5z^6-40u^6z^7+10u^7z^8\Bigr)$ %$\triangleright\qquad D_1(z,u) = \dfrac{6u(1-u)^8}{5} + % \dfrac{12u^2}{5}(1-u)^7(1-z) %-\dfrac{24u^5(1+u)(1-u)^3}{5} (1-z)^5 %-\dfrac{48u^6(1+u)(1-u)^2}{5} (1-z)^6 %-\dfrac{48(1+u)u^7(1-u)}{7} (1-z)^7 %-\dfrac{12(1+u)u^8}{7} (1-z)^8$ \bigskip $\triangleright\qquad D_2(z,u) = -\dfrac{1}{35}\Bigl( 30-192u+492u^2+588u^5-588u^6-60uz+444u^2z- 1428u^3z+2604u^4z-3780u^5z+1764u^6z-588u^7z +84u^8z+1680u^5z^2-1680u^5z^3+840u^5z^4 -168u^5z^5+1680u^6z^2-3360u^6z^3 +3360u^6z^4-1680u^6z^5+840u^8z^4 -1680u^8z^5-168u^9z^5-588u^3+168u^4+252u^7 -42u^8-1680u^7z^3+3360u^7z^4-3024u^7 z^5+1344u^7z^6+336u^6z^6+1344u^8z^6+ 336u^9z^6-240u^7z^7-240u^9z^7-480u^8z^7 +60u^8z^8+60u^9z^8 \Bigr)$ %$\triangleright\qquad D_2(z,u) = -\dfrac{6(2u-5)(1-u)^8}{35} % -\dfrac{12u(2u-5)(1-u)^7}{35} (1-z) % +\dfrac{24u^5(1+u)(1-u)^3}{5} (1-z)^5 % +\dfrac{48u^6(1+u)(1-u)^2}{5} (1-z)^6 % +\dfrac{48(1+u)(1-u)u^7}{7} (1-z)^7 % +\dfrac{12(1+u)u^8}{7} (1-z)^8$ \section{Tables} The next Tables collect the full statements of the theorems, % ~\ref{theo:avg-desc-lbst}, \ref{theo:var-desc-lbst}, % \ref{theo:prob-rdesc-lbst} and~\ref{theo:avg-asc-lbst} considering the general cases as they appear in the main text of the paper as well as the special cases not listed there. \addtolength{\tabcolsep}{2ex} \renewcommand{\arraystretch}{3} \begin{table} \begin{center} \begin{tabular}{|c|l|}\hline $j$ & $\hfil \avgdesc{n}{j}$ \\\hline\hline & $\displaystyle\frac65,\qquad\mbox{for $n\ge5$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{1} & $\displaystyle \avgdesc{1}{1}=1,\ \avgdesc{2}{1}=\tfrac 32,\ \avgdesc{3}{1}=1,\ \avgdesc{4}{1}=\tfrac 54$ \\[2mm]\hline & $\displaystyle\frac{18}5-\frac3n,\qquad\mbox{for $n\ge6$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{2} & $\displaystyle \avgdesc{2}{2}=\tfrac 32, \ \avgdesc{3}{2}=3,\ \avgdesc{4}{2}=\tfrac{11}4,\ \avgdesc{5}{2}=3$ \\[2mm]\hline & $\displaystyle\frac{136}{35}-\frac6n,\qquad\mbox{for $n\ge7$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{3} & $\displaystyle \avgdesc{3}{3}=1, \ \avgdesc{4}{3}=\tfrac{11}{4},\ \avgdesc{5}{3}=\tfrac{13}{5},\ \avgdesc{6}{3}=\tfrac{29}{10}$ \\[2mm]\hline & $\displaystyle \frac92-\frac9n,\qquad\mbox{for $n\ge8$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{4} & $\displaystyle \avgdesc{4}{4}=\tfrac 54,\ \avgdesc{5}{4}=3, \ \avgdesc{6}{4}=\tfrac{29}{10},\ \avgdesc{7}{4}=\tfrac{113}{35}$ \\[2mm]\hline $5\le j\le n-4$ & $\begin{array}{l} \displaystyle -\frac{12}{7}H_n+ \frac{12}{7}H_j+\frac{12}{7}H_{n+1-j} \\ \displaystyle -\frac{6}{7j}-\frac{6}{7(n+1-j)} +\frac{79}{70} \\ \displaystyle -\frac{3(3j-5)}{7n}+\frac{6(j-1)^2}{7\ffact n2}+ \frac{2(2j-3)\ffact{(j-1)}{2}}{7\ffact n3} \\ \displaystyle +\frac{3(j-2)\ffact{(j-1)}{3}}{7\ffact n4} -\frac{3(2j-5)\ffact{(j-1)}{4}}{7\ffact n5}+ \frac{2(j-3)\ffact{(j-1)}{5}}{7\ffact n6} \end{array} $ \\[-1cm] \mbox{} & \mbox{} \\ \hline \end{tabular} \end{center} \bigskip \caption{Average number of descendants of the \th{j} node in a random LBST of size $n$.} % (Thm.~\ref{theo:avg-desc-lbst}).}\label{table:avg-desc-lbst} \end{table} \begin{table} \begin{center} \begin{tabular}{|c|l|}\hline $j$ & $\hfil \mdesc{2}{n}{j}$ \\\hline\hline & $\dfrac25\qquad\mbox{for $n\ge5$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{1} & $\displaystyle \mdesc{2}{1}{1}=0,\ \mdesc{2}{2}{1}=1,\ \mdesc{2}{3}{1}=0,\ \mdesc{2}{4}{1}=\frac12$ \\[2mm]\hline & $\displaystyle \frac{36}{5}H_n-\frac{206}{25}\qquad\mbox{for $n\ge6$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{2} & $\displaystyle \mdesc{2}{2}{2}=1, \ \mdesc{2}{3}{2}=6,\ \mdesc{2}{4}{2}=\frac{13}{2},\ \mdesc{2}{5}{2}=\frac{41}{5}$ \\[2mm]\hline & $\displaystyle \frac{72}{5}H_n-\frac{4534}{175}+\frac{6}{n}\qquad\mbox{for $n\ge7$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{3} & $\displaystyle \mdesc{2}{3}{3}=0, \ \mdesc{2}{4}{3}=\frac{13}{2},\ \mdesc{2}{5}{3}=8, \ \mdesc{2}{6}{3}=\frac{52}{5}$ \\[2mm]\hline & $\displaystyle\frac{108}{5}H_n-\frac{7886}{175}-\frac{36}{5(n-1)}+\frac{126}{5n}\qquad\mbox{for $n\ge8$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{4} & $\displaystyle \mdesc{2}{4}{4}=\frac12,\ \mdesc{2}{5}{4}=\frac{41}{5}, \ \mdesc{2}{6}{4}=\frac{52}{5},\ \mdesc{2}{7}{4}=\frac{468}{35}$ \\[2mm]\hline $5\le j\le n-4$ & $\begin{array}{l} \displaystyle \left(\frac {36n}{5}-\frac {12}{35}\right) H_n + \left(\frac {36j}{5}-\frac {36n}{5}-\frac {48}{7}\right) H_{n+1-j} +\left(\frac {12}{35}-\frac {36j}{5}\right) H_j\\ \displaystyle -\frac{132}{35j}-\frac {132}{35(n+1-j)} +\frac {3489}{175}-\frac {33j}{5} +\left(\frac {66}{7}-\frac {429j}{35}+\frac {33j^2}{5}\right)\frac{1}{n}\\ \displaystyle +\frac {132 (j-1)^{2}}{35\ffact n2} +\frac { 44(2j-3) \ffact{(j-1)}2}{ 35\ffact n3} +\frac {66 (j-2 )\ffact{(j-1)}3}{35 \ffact n4}\\ \displaystyle -\frac {66(2j-5) \ffact{(j-1)}4}{35 \ffact n5} +\frac {44(j-3)\ffact{(j-1)}5}{35 \ffact n6} \end{array}$ \\[-1cm] \mbox{} & \mbox{} \\ \hline \end{tabular} \end{center} \bigskip \caption{Second factorial moment of the number of descendants of the \th{j} node in a random LBST of size $n$.} % (Thm.~\ref{theo:var-desc-lbst}).} \label{table:var-desc-lbst} \end{table} \begin{table} \begin{center} \begin{tabular}{|c|l|}\hline $m$ & $\hfil \probdescrnd{n}{m}=\Prob{\descrnd{n}=m}$ \\\hline\hline & $\displaystyle\frac37\left(1+\frac1n\right)\qquad\mbox{for $n\ge6$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{1} & $\displaystyle \probdescrnd{1}{1}=1,\ \probdescrnd{2}{1}=\tfrac14,\ \probdescrnd{3}{1}=\tfrac29,\ \probdescrnd{4}{1}=\tfrac18,\ \probdescrnd{5}{1}=\tfrac{13}{125}$ \\[2mm]\hline & $\displaystyle\frac17\left(1+\frac1n\right),\qquad\mbox{for $n\ge6$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{2} & $\displaystyle \probdescrnd{2}{2}=\tfrac14, \ \probdescrnd{3}{2}=0,\ \probdescrnd{4}{2}=\tfrac1{16},\ \probdescrnd{5}{2}=\tfrac 4{125}$ \\[2mm]\hline & $\displaystyle\frac3{35}\left(1+\frac1n\right),\qquad\mbox{for $n\ge6$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{3} & $\displaystyle \probdescrnd{3}{3}=\tfrac19, \ \probdescrnd{4}{3}=0,\ \probdescrnd{5}{3}=\tfrac{3}{5}$ \\[2mm]\hline & $\displaystyle \frac2{35}\left(1+\frac1n\right)\qquad\mbox{for $n\ge6$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{4} & $\displaystyle \probdescrnd{4}{4}=\tfrac1{16},\ \probdescrnd{5}{4}=0$ \\[2mm]\hline $5\le m< n$ & $\displaystyle \frac{12}{7}\,\frac{(n+2+m)(n-1-m)}{n^2(m+2)(m+1)} -\frac{12}{7}\, \frac{\ffact m5}{n^2\ffact n5}+\frac{12}{7n^2}$ \\[2mm]\hline $n$ & $\displaystyle\frac1n$ \\[-1cm] \mbox{} & \mbox{} \\ \hline \end{tabular} \end{center} \bigskip \caption{Probability that a random node in a random LBST of size $n$ has $m$ descendants.} % (Thm.~\ref{theo:prob-rdesc-lbst}).}\label{table:prob-rdesc-lbst} \end{table} \begin{table} \begin{center} \begin{tabular}{|c|l|}\hline $j$ & $\hfil \avgasc{n}{j}$ \\\hline\hline & $\displaystyle\frac65H_n-\frac{6}{25},\qquad\mbox{for $n\ge5$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{1} & $\displaystyle \avgasc{1}{1}=1,\ \avgasc{2}{1}=\frac32,\ \avgasc{3}{1}=2,\ \avgasc{4}{1}=\frac94$ \\[2mm]\hline & $\displaystyle\frac65H_n-\frac{21}{25},\qquad\mbox{for $n\ge6$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{2} & $\displaystyle \avgasc{2}{2}=\frac32, \ \avgasc{3}{2}=1,\ \avgasc{4}{2}=\frac74, \ \avgasc{5}{2}=\frac{19}{10}$ \\[2mm]\hline & $\displaystyle\frac65H_n-\frac{87}{175}-\frac65\frac1{\ffact n2},\qquad\mbox{for $n\ge7$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{3} & $\displaystyle \avgasc{3}{3}=2, \ \avgasc{4}{3}=\frac74,\ \avgasc{5}{3}=\frac{11}{5}, \ \avgasc{6}{3}=\frac{12}{5}$ \\[2mm]\hline & $\displaystyle \frac65H_n-\frac{11}{25}-\frac{18}5\frac1{\ffact n2}-\frac{12}5\frac1{\ffact n3},\qquad\mbox{for $n\ge8$}$ \\[2mm]\cline{2-2} \raisebox{5ex}[-5ex]{4} & $\displaystyle \avgasc{4}{4}=\frac94,\ \avgasc{5}{4}=\frac{19}{10}, \ \avgasc{6}{4}=\frac{12}{5}, \ \avgasc{7}{4}=\frac{18}{7}$ \\[2mm]\hline $5\le j\le n-4$ & $ \begin{array}{l} \displaystyle \frac{24}{35}H_n+ \frac{18}{35}H_j+\frac{18}{35}H_{n+1-j} \\ \displaystyle +\frac{12}{35j}+\frac{12}{35(n+1-j)} -\frac{279}{175}-\frac{6}{7n} \\ \displaystyle +\frac{18j}{35n}-\frac{12(j-1)^2}{35\ffact n2}- \frac{4(2j-3)\ffact{(j-1)}{2}}{35\ffact n3} \\ \displaystyle -\frac{6(j-2)\ffact{(j-1)}{3}}{35\ffact n4} +\frac{6(2j-5)\ffact{(j-1)}{4}}{35\ffact n5}- \frac{4(j-3)\ffact{(j-1)}{5}}{35\ffact n6} \end{array} $ \\[-1cm] \mbox{} & \mbox{} \\ \hline \end{tabular} \end{center} \bigskip \caption{Average number of ascendants of the \th{j} node in a random LBST of size $n$.} % (Thm.~\ref{theo:avg-asc-lbst}).} \label{table:avg-asc-lbst} \end{table} \begin{table} \begin{center} \begin{tabular}{|c|l|}\hline $j$ & $\hfil \masc{2}{n}{j}$ \\\hline\hline & $\displaystyle \frac{36}{25}H_{n}^{2} - \frac{144}{125}H_{n} - \frac{36}{25}H_{n}^{(2)}+\frac{766}{625}+\frac{3}{125}\frac{1}{n}- \frac{12}{125}\frac{1}{n-1}+\frac{18}{125}\frac{1}{n-2}-\frac{12}{125} \frac{1}{n-3}$ \\ 1 & $\displaystyle + \frac{3}{125}\frac{1}{n-4} \qquad \text{for} \; n \ge 5$ \\[2mm]\cline{2-2} & $\displaystyle \masc{2}{1}{1} = 0 \; , \; \masc{2}{2}{1} = 1 \; , \; \masc{2}{3}{1} = 2 \; , \; \masc{2}{4}{1} = 3 $ \\[2mm]\hline & $\displaystyle \frac{36}{25}H_{n}^{2}-\frac{324}{125}H_{n}-\frac{36}{25}H_{n}^{(2 )}+\frac{1726}{625}-\frac{27}{125}\frac{1}{n}+\frac{108}{125} \frac{1}{n-1}-\frac{162}{125}\frac{1}{n-2}$ \\ 2 & $\displaystyle + \frac{108}{125} \frac{1}{n-3} - \frac{27}{125}\frac{1}{n-4} \qquad \text{for} \; n \ge 6$ \\[2mm]\cline{2-2} & $\displaystyle \masc{2}{2}{2} = 1 \; , \; \masc{2}{3}{2} = 0 \; , \; \masc{2}{4}{2} = 2 \; , \; \masc{2}{5}{2} = \frac{11}{5}$ \\[2mm]\hline & $\displaystyle \frac{36}{25}H_{n}^{2}-\left(\frac{1548}{875}+ \frac{72}{25} \frac{1}{n(n-1)}\right)H_{n}-\frac{36}{25}H_{n}^{(2)}+ \frac{77094}{30625}+\frac{2169}{875}\frac{1}{n}-\frac{2892}{875} \frac{1}{n-1}$ \\ & $\displaystyle + \frac{1476}{875}\frac{1}{n-2}-\frac{1044}{875} \frac{1}{n-3}+\frac{321}{875}\frac{1}{n-4}-\frac{36}{875}\frac{1}{n-5}+ \frac{6}{875}\frac{1}{n-6}$ \\ \raisebox{4ex}[-4ex]{3} & $\displaystyle {} - \frac{72}{25}\frac{1}{n^{2}}+\frac{72}{25} \frac{1}{(n-1 )^{2}} \qquad \text{for} \; n \ge 7$ \\[2mm]\cline{2-2} & $\displaystyle \masc{2}{3}{3} = 2 \; , \; \masc{2}{4}{3} = 2 \; , \; \masc{2}{5}{3} = \frac{18}{5} \; , \; \masc{2}{6}{3} = \frac{22}{5}$ \\[2mm]\hline & $\displaystyle \frac{36}{25}H_{n}^{2} + \left(-\frac{204}{125}+ \frac{144}{25} \frac{1}{n}-\frac{72}{25}\frac{1}{n-1}-\frac{72}{25} \frac{1}{n-2} \right)H_{n} - \frac{36}{25}H_{n}^{(2)} + \frac{11077}{4375}$ \\ & $ \displaystyle {} + \frac{5517}{875}\frac{1}{n} - \frac{786}{125}\frac{1}{n-1}- \frac{246}{125}\frac{1}{n-2}+\frac{378}{125}\frac{1}{n-3}- \frac{177}{125}\frac{1}{n-4}+\frac{54}{125}\frac{1}{n-5}$\\ \raisebox{4ex}[-4ex]{4} & $ \displaystyle {} - \frac{12}{125}\frac{1}{n-6}+\frac{6}{875}\frac{1}{n-7} - \frac{144}{25}\frac{1}{n^{2}}+\frac{72}{25}\frac{1}{(n-1)^{2}}+ \frac{72}{25}\frac{1}{(n-2)^{2}} \qquad \text{for} \; n \ge 8 \; ,$ \\[2mm]\cline{2-2} & $\displaystyle \masc{2}{4}{4} = 3 \; , \; \masc{2}{5}{4} = \frac{11}{5} \; , \; \masc{2}{6}{4} = \frac{22}{5} \; , \; \masc{2}{7}{4} = \frac{36}{7} $ \\[2mm]\hline \end{tabular} \end{center} \end{table} \begin{table}[t] \renewcommand{\arraystretch}{1.8} \setlength{\arraycolsep}{0mm} \setlength{\tabcolsep}{2mm} \hspace*{-1.5cm} \begin{center} \begin{tabular}{|c|l|}\hline $j$ & $\hfil \masc{2}{n}{j}$ \\ \hline\hline $5 \le j \le n-4$ & \begin{minipage}{13cm} $ \begin{array}{l} \frac{576}{245}H_{n}H_{n-j} + \frac{576}{245}H_{n}H_{j} - \frac{288}{245}H_{n}^{2}+ \frac{324}{1225}H_{n-j}^{2}- \frac{1368}{1225}H_{n-j}H_{j}+ \frac{324}{1225}H_{j}^{2} \\ {} + \Big( \frac{72}{42875} \frac{227j+525}{j} + \frac{792}{245}\frac{1}{n+1-j} - \frac{2}{1225} \frac{2j^{6}-6j^{5}-55j^{4}+120j^{3} +953j^{2}-1014j+540}{n} \\ {} + \frac{4}{245}\frac{(j-1)^{2} (j^{4}-4j^{3}-11j^{2}+30j+72)}{n-1} - \frac{4}{245}\frac{(j-1)(j-2) (2j^{4}-12j^{3}+13j^{2}+15j-36)}{n-2} \\ {} + \frac{8}{245}\frac{(j-1)^{2} (j-2)^{2}(j-3)^{2}}{n-3} - \frac{2}{245}\frac{(j-1)(j-2)(j-3)(j-4) (2j^{2}-10j+15)}{n-4} \\ {} + \frac{4}{1225}\frac{(j-1)(j-2)(j-3)^{2} (j-4) (j-5)}{n-5}\Big) H_{n} \\ {} + \Big( - \frac{36}{42875} \frac{5697j +70}{j}-\frac{288}{245}\frac{1}{n+1-j} + \frac{1}{6125} \frac{20j^{6}-102j^{5}-445j^{4}+2040j^{3}+8165j^{2}+402j+360}{n} \\ {} - \frac{2}{1225}\frac{(j-1)(10j^{5}-71j^{4}+14j^{3} +557j^{2}-42j-1224)}{n-1} + \frac{2}{1225}\frac{(j-1)(j-2)(20j^{4}-162j^{3}+319j^{2} +129j-612)}{n-2} \\ {} - \frac{4}{1225}\frac{(j-1)(j-2)(j-3)(10j^{3}-81j^{2} +194j-102)}{n-3} + \frac{1}{1225}\frac{(j-1)(j-2)(j-3)(j-4) (20j^{2}-142j+255)}{n-4} \\ {} - \frac{2}{6125}\frac{(j-1)(j-2)(j-3)(j-4) (j-5)(10j-51)}{n-5}\Big) H_{n-j} \\ {} + \Big(-\frac{36}{42875} \frac{2267j+2030}{j}- \frac{288}{245} \frac{1}{n+1-j} + \frac{1}{6125} \frac{20j^{6}-18j^{5}-655j^{4}+360j^{3}+10895j^{2}-20682j+10440}{n} \\ {} - \frac{2}{1225}\frac{ (j-1) (10j^{5}-29j^{4}-154j^{3}+263j^{2}+882j-216)}{n-1} + \frac{2}{1225}\frac{(j-1)(j-2) (20j^{4}-78j^{3}-59j^{2}+171j-108)}{n-2} \\ {} - \frac{4}{1225}\frac{(j-1)(j-2)(j-3) (10j^{3}-39j^{2} +26j-18)}{n-3} + \frac{1}{1225}\frac{(j-1)(j-2)(j-3) (j-4)(20j^{2}-58j+45)}{n-4} \\ {} - \frac{2}{6125}\frac{(j-1)(j-2)(j-3) (j-4)(j-5)(10j-9)}{n-5}\Big) H_{j} \\ {} + \frac{288}{245} H_{n}^{(2)} - \frac{3204}{1225}H_{n-j}^{(2)}-\frac{3204}{1225}H_{j}^{(2)} + \frac{12}{1225}\frac{1}{j+4}-\frac{24}{175} \frac{1}{j+3}+\frac{792}{1225} \frac{1}{j+2}- \frac{2088}{1225} \frac{1}{j+1} \\ {} - \frac{53148}{42875} \frac{1}{j} -\frac{1044}{875}\frac{1}{j-1}+ \frac{396}{875} \frac{1}{j-2}- \frac{12}{125}\frac{1}{j-3}+ \frac{6}{875}\frac{1}{j-4}+\frac{144}{175} \frac{1}{j^{2}} + \frac{6}{875} \frac{1}{n-3-j}-\frac{12}{125}\frac{1}{n-2-j} \\ {} + \frac{396}{875}\frac{1}{n-1-j}-\frac{1044}{875} \frac{1}{n-j} - \frac{24}{8575}\frac{1123j-420}{ (n+1-j)j}-\frac{2088}{1225}\frac{1}{n+2-j} +\frac{792}{1225} \frac{1}{n+3-j}- \frac{24}{175}\frac{1}{n+4-j} \\ {} + \frac{12}{1225}\frac{1}{n+5-j}- \frac{792}{245}\frac{1}{ (n+1-j)^{2}} + \frac{2297696}{214375} \\ {} - \frac{5522j^{7}-8166j^{6}-167395j^{5}+142845j^{4} +3249683j^{3}-1044579j^{2} - 2445930j+1096200}{643125 \, nj} \\ {} + \frac{2 (2761j^{7}-12366j^{6}-25787j^{5}+116883j^{4} +176746j^{3}-361269j^{2} + 120672j+22680)}{128625 \, (n-1)j} \\ {} - \frac{2 (5522j^{7}-41298j^{6}+82913j^{5} +11427j^{4}-226090j^{3} +256698j^{2} - 49482j-22680)}{128625 \, (n-2)j} \\ {} + \frac{4 (j-1)(j-3) (2761j^{5}-17888j^{4} +38198j^{3}-28798j^{2} - 5718j+3780)}{128625 \, (n-3)j} \\ {} - \frac{5522j^{7}-74430j^{6}+407885j^{5}-1158375j^{4} +1755053j^{3}-1233465j^{2} + 169920j+113400}{128625 \, (n-4)j} \\ {} + \frac{2 (2761j^{7}-45498j^{6}+299185j^{5}-999255j^{4} +1757614j^{3}-1456887j^{2} + 313560j+113400)}{643125 \, (n-5)j} \\ {} + \frac{2 (2j^{6}-6j^{5}-55j^{4}+120j^{3}+953j^{2}-1014j +540)}{1225 \, n^{2}} - \frac{4 (j-1)^{2} (j^{4}-4j^{3}-11j^{2}+30j+72 )}{245 \, (n-1)^{2}} \\ {} + \frac{4 (j-1)(j-2) (2j^{4}-12j^{3}+13j^{2} +15j-36 )}{245 \, (n-2)^{2}} - \frac{8(j-1)^{2}(j-2)^{2}(j-3)^{2})}{245 \, (n-3)^{2}} \\ {} + \frac{2 (j-1)(j-2)(j-3)(j-4)(2j^{2}-10j+15 )}{245 \, (n-4)^{2}} - \frac{4 (j-1)(j-2)(j-3)^{2}(j-4)(j-5)} {1225 \, (n-5 )^{2}} \end{array} $ \end{minipage} \\ \hline \end{tabular} \end{center} \bigskip \caption{Second factorial moment of the number of ascendants of the \th{j} node in a random LBST of size $n$.} \end{table} \end{document}