\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Returns, Hills, and $t$-ary Trees }
\vskip 1cm
\large
Helmut Prodinger\\
Department of Mathematical Sciences\\
Stellenbosch University\\
7602 Stellenbosch\\
South Africa\\
\href{mailto:hproding@sun.ac.za}{\tt hproding@sun.ac.za} \\
\end{center}
\vskip .2 in
\begin{abstract}
A recent analysis of returns and hills of generalized Dyck paths is
carried over to the language of $t$-ary trees, from which, by explicit
bivariate generating functions, all the relevant results follow quickly
and smoothly. A conjecture about the (discrete) limiting distribution
of hills is settled in the affirmative.
\end{abstract}
\section{Introduction}
In a recent paper in this journal~\cite{CaMc16},
\emph{generalized Dyck paths} where investigated: they have an
up-step $\mathsf{u}=(1,1)$ and a down-step
$\mathsf{d}=(1,-t+1)$, where $t\ge2$, start at the origin, end
on the $x$-axis, and never go below the $x$-axis. A general
reference for such lattice paths is an encyclopedic paper by
Banderier and Flajolet \cite{BaFl02}.
Two parameters were investigated (with the help of Riordan
arrays): the number of returns to the $x$-axis (the origin
itself does not count), and the number of (contiguous) subpaths
of the form $\mathsf{u}^{t-1}\mathsf{d}$, that sit on the
$x$-axis.
In the present note, I would like to emphasize that the
language of trees, in particular $t$-ary trees, is favorable
here, because it allows one to write the relevant generating
functions with ease, without any mentioning of Riordan arrays,
and also leads to settling a conjecture mentioned in the
recent paper mentioned before \cite{CaMc16}.
The family of $t$-ary trees is recursively described: such a
tree is either an external node (depicted as a square), or a
root (an internal node, depicted as a circle), followed by
subtrees (in this order) $T_1,\dots,T_t$. For this and many
other concepts, we refer to the universal book by Flajolet and
Sedgewick \cite{FlSe09}. The generating function
$T(z)=\sum_{n\ge0}a_nz^n$, where $a_n$ is the number of trees
of size $n$ ($n$ internal nodes) is, following the recursive
definition, given by $T(z)=1+zT^t(z)$. Extracting coefficients
is efficiently done by setting $z=u/(1+u)^t$, thus $T=1+u$, and
contour integration; the method is closely related to the
Lagrange inversion formula. Here is an example: \begin{align*}
[z^n]T^k(z)&=\frac1{2\pi i}\oint\frac{dz}{z^{n+1}}T^k(z)\\
&=\frac1{2\pi
i}\oint\frac{du(1+u-tu)(1+u)^{t(n+1)}}{(1+u)^{t+1}u^{n+1}}(1+u)^k\\
&=[u^{n}](1+u-tu)(1+u)^{tn+k-1}\\
&=\binom{tn+k-1}{n}-(t-1)\binom{tn+k-1}{n-1}\\
&=\frac{k}{n}\binom{tn+k-1}{n-1}. \end{align*} This produces
in particular (for $k=1$) the numbers
$a_n=\frac1n\binom{tn}{n-1}$.
There is a natural bijection between the family of generalized
Dyck paths and the family of $t$-ary trees. It is based on the
decomposition of paths according to the \emph{first} return to
the $x$-axis. The first part of the Dyck paths is
(recursively) responsible for the first $t-1$ subtrees, and the
rest of the Dyck path for the remaining $t$-th subtree. It is
then apparent that the number of down-steps is the same as the
number of internal nodes of the associated tree. Here is the
situation depicted for $t=3$. \begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.5]
%\draw[step=1.cm,black] (-0.0,-0.0) grid
(20,6); \draw[ultra thick] (0.0,0.) to (1.,1.);
\draw (1,1) .. controls (2,5) .. (3,1); \draw
(3,1) .. controls (4,7) .. (5,1); \node at
(5.5,1) {$\cdot$}; \node at (6,1) {$\cdot$};
\node at (6.5,1) {$\cdot$}; \draw (7,1) ..
controls (8,3) .. (9,1); \draw [ultra
thick](9,1) to (10,2); \draw (1+9,1+1) ..
controls (2+9,6) .. (3+9,1+1); \draw (3+9,1+1)
.. controls (4+9,4) .. (5+9,1+1); \node at
(5.5+9,2) {$\cdot$}; \node at (6+9,2)
{$\cdot$}; \node at (6.5+9,2) {$\cdot$}; \draw
(16,2) .. controls (17,5) .. (18,2); \draw
[ultra thick](18,2) to (19,0);
\draw (19,0) .. controls (20,6) .. (21,0);
\draw (21,0) .. controls (22,3) .. (23,0);
\node at (23.5,0) {$\cdot$}; \node at (24,0)
{$\cdot$}; \node at (24.5,0) {$\cdot$}; \draw
(25,0) .. controls (26,4) .. (27,0);
\draw [thick, decorate, decoration={brace,
amplitude=10pt, mirror, raise=4pt}] (1cm, -0.5)
to node[below,yshift=-0.5cm] {$T_{1}$} (9cm,
-0.5);
\draw [thick, decorate, decoration={brace,
amplitude=10pt, mirror, raise=4pt}] (10cm,
-0.5) to node[below,yshift=-0.5cm] {$T_{2}$}
(18cm,- 0.5);
\draw [thick, decorate, decoration={brace,
amplitude=10pt, mirror, raise=4pt}] (19cm,
-0.5) to node[below,yshift=-0.5cm] {$T_{3}$}
(27cm, -0.5);
\end{tikzpicture} \end {center}
\caption{The decomposition of generalized Dyck
paths leading (recursively) to a ternary tree
with subtrees $T_1, T_2, T_3$.}\end{figure}
Now a little reflection convinces us that the number of
returns is the same as the number of (internal) nodes
on the path from the root to the rightmost leaf. And,
further: the number of hills is the number of nodes on
this rightmost path with the property that its first
$t-1$ subtrees are empty (are the empty subtree,
consisting only of an external node).
\begin{figure}[h]\begin{center}
\begin{tikzpicture}[scale=0.5] \node at
(0,0){$\bullet$}; \node at
(3,-1){$\bullet$}; \node at
(0,-1){$\blacksquare$}; \node at
(-3,-1){$\blacksquare$}; \node at
(6,-2){$\bullet$}; \node at
(9,-3){$\bullet$}; \node at
(12,-4){$\bullet$}; \node at
(15,-5){$\bullet$}; \draw[thick] (0,0)
to (15,-5); \draw[thick] (0,0) to
(0,-1); \draw[thick] (0,0) to (-3,-1);
\node at (3,-2){$\blacksquare$}; \node
at (0,-2){$\bullet$};
\draw[thick] (3,-1) to (0,-2);
\draw[thick] (3,-1) to (3,-2);
\node at (-1,-3){$\blacksquare$}; \node
at (0,-3){$\blacksquare$}; \node at
(1,-3){$\blacksquare$};
\draw[thick] (-1,-3) to (0,-2);
\draw[thick] (0,-3) to (0,-2);
\draw[thick] (1,-3) to (0,-2);
\node at (3,-3){$\blacksquare$}; \node
at (6,-3){$\bullet$};
\draw[thick] (6,-3) to (6,-2);
\draw[thick] (3,-3) to (6 ,-2);
\node at (5,-4){$\blacksquare$}; \node
at (6,-4){$\bullet$}; \node at
(7,-4){$\blacksquare$};
\draw[thick] (5,-4) to (6,-3);
\draw[thick] (6,-4) to (6,-3);
\draw[thick] (7,-4) to (6,-3);
\node at (8,-4){$\blacksquare$}; \node
at (9,-4){$\blacksquare$}; \draw[thick]
(8,-4) to (9,-3); \draw[thick] (9,-4)
to (9,-3);
\node at (11,-5){$\blacksquare$}; \node
at (12,-5){$\blacksquare$};
\draw[thick] (11,-5) to (12,-4);
\draw[thick] (12,-5) to (12,-4);
\node at (13,-6){$\bullet$}; \node at
(15,-6){$\blacksquare$}; \node at
(17,-6){$\blacksquare$}; \draw[thick]
(13,-6) to (15,-5); \draw[thick]
(15,-6) to (15,-5); \draw[thick]
(17,-6) to (15,-5);
\node at (5,-5){$\blacksquare$}; \node
at (6,-5){$\blacksquare$}; \node at
(7,-5){$\blacksquare$};
\draw[thick] (5,-5) to (6,-4);
\draw[thick] (6,-5) to (6,-4);
\draw[thick] (7,-5) to (6,-4);
\node at (14,-7){$\blacksquare$}; \node
at (12,-7){$\blacksquare$}; \node at
(13,-7){$\blacksquare$};
\draw[thick] (12,-7) to (13,-6);
\draw[thick] (13,-7) to (13,-6);
\draw[thick] (14,-7) to (13,-6);
\end{tikzpicture}\end{center}
\caption{A ternary tree with 10 (internal)
nodes. It has 6 returns and 3 hills.} \end
{figure}
In what follows, we will analyze these
parameters in terms of $t$-ary trees. In
particular, we will freely speak about returns
and hills of $t$-ary trees.
Cameron and McLeod \cite{CaMc16}, defined the
\emph{negative binomial distribution} via
\begin{equation*}
\mathbb{P}\{Y=k\}=\binom{k-1}{r-1}p^r(1-p)^{k-r}.
\end{equation*} This is somewhat in contrast
with the book Analytic Combinatorics
\cite{FlSe09} and \emph{Wikipedia}, as it is a
shifted version, and the roles of $p$ and $1-p$
are interchanged from the more common
definitions. Nevertheless, we will stick to
this definition here, for the reason of
comparisons. The numbers $r$ and $p$ are called
the parameters of the distribution.
\section{The number of returns on $t$-ary
trees}
Let $F(z,v)$ be the generating function with
respect to the size and the number of returns,
i.~e., the coefficient of $z^nv^k$ is the
number trees with $n$ internal nodes and $k$
returns. Then we find the equation
\begin{equation*} F(z,v)=1+zT^{t-1}(z)vF(z,v).
\end{equation*} Since
$zT^{t-1}(z)=\frac{T(z)-1}{T(z)}$, this leads
to the explicit form \begin{equation*}
F(z,v)=\frac1{1-v\frac{T(z)-1}{T(z)}}.
\end{equation*} Therefore \begin{equation*}
[v^k]F(z,v)=\Big(\frac{T(z)-1}{T(z)}\Big)^k=\Big(\frac{u}{1+u}\Big)^k.
\end{equation*} Furthermore \begin{align*}
[z^n][v^k]F(z,v)&=[z^n]\Big(\frac{u}{1+u}\Big)^k\\
&=\frac1{2\pi
i}\oint\frac{dz}{z^{n+1}}\Big(\frac{u}{1+u}\Big)^k\\
&=\frac1{2\pi
i}\oint\frac{du(1+u-tu)(1+u)^{t(n+1)}}{u^{n+1}(1+u)^{t+1}}\Big(\frac{u}{1+u}\Big)^k\\
&=[u^{n-k}](1+u-tu)(1+u)^{tn-1-k}\\
&=\binom{tn-1-k}{n-k}-(t-1)\binom{tn-1-k}{n-1-k}\\
&=\frac{k}{n}\binom{tn-1-k}{n-k}. \end{align*}
Division by $a_n$ gives the probability that a
random tree of size $n$ has $k$ returns:
\begin{equation*}
p_k(n)=k\frac{\binom{tn-1-k}{n-k}}{\binom{tn}{n-1}}\to
\frac{k(t-1)^2}{t^{k+1}},\quad
\text{fixed}\ k,\quad n\to\infty.
\end{equation*}
In order to compute the $d$-th (factorial)
moment, we evaluate \begin{align*}
\frac{\partial^d}{\partial
v^d}F(z,v)\Big|_{v=1}=d!T(z)(T(z)-1)^d=d!(1+u)u^d.
\end{align*} Furthermore, \begin{align*}
[z^n]\frac{\partial^d}{\partial
v^d}F(z,v)\Big|_{v=1}&=[u^{n-d}]d!(1+u-tu)(1+u)^{tn}\\*
&=d!\binom{tn}{n-d}-d!(t-1)\binom{tn}{n-1-d}=\frac{(td+1)d!}{n-d}\binom{tn}{n-1-d}.
\end{align*} For the expected value, we
consider $d=1$ and divide by $a_n$, with the
result \begin{equation*}
\frac{(t+1)n}{n(t-1)+2} \sim\frac{t+1}{t-1}.
\end{equation*} The second factorial moment is
obtained via $d=2$, with the result
\begin{equation*}
\frac{2(2t+1)n(n-1)}{(tn-n+3)(tn-n+2)}\sim\frac{2(2t+1)}{(t-1)^2}.
\end{equation*} This leads to the variance:
\begin{equation*} 2\frac {n ( t-1 ) ( n-1 )
( tn+1 ) }{ ( tn-n+3 ) ( tn-n+2 )
^2}\sim\frac{2t}{(t-1)^2}. \end{equation*}
This section reproved and extended the results
of \cite{CaMc16} on the number of returns.
Note that the quantity
$\frac{k(t-1)^2}{t^{k+1}}$ is
$\mathbb{P}\{Y=k+1\}$, where $Y$ is a random
variable, distributed according to the negative
binomial distribution for $r=2$ and
$p=\frac{t-1}{t}$.
\section{The number of hills on $t$-ary trees}
Let $G(z,v)$ be the generating function with
respect to the size (variable $z$) and the
number of hills (variable $v$). Then we find
the recursion \begin{equation*}
G(z,v)=1+zT^{t-1}(z)G(z,v)+z(v-1)G(z,v).
\end{equation*} Since $zT^{t-1}(z)=1-1/T(z)$,
we find the explicit solution \begin{equation*}
G(z,v)=\frac{T(z)}{1-(v-1)zT(z)}=\sum_{k\ge0}(v-1)^kz^kT^{k+1}(z).
\end{equation*} By $d$-fold differentation,
followed by setting $v=1$, we get the
generating function of the $d$-th factorial
moments (apart from normalization):
\begin{equation*} d!z^dT^{d+1}(z).
\end{equation*} Furthermore, \begin{align*}
[z^n]d!z^dT^{d+1}(z)&=\frac{d!}{2\pi i}\oint
\frac{dz}{z^{n+1-d}}T^{d+1}(z)\\
&=\frac{d!}{2\pi i}\oint
\frac{du(1+u-tu)(1+u)^{t(n-d)+d}}{u^{n+1-d}}\\
&=d![u^{n-d}](1+u-tu)(1+u)^{t(n-d)+d}\\
&=d!\binom{tn-(t-1)d}{n-d}-d!(t-1)\binom{tn-(t-1)d}{n-1-d}\\
&=\frac{(d+1)!}{n-d}\binom{tn-(t-1)d}{n-1-d}.
\end{align*} For $d=1$, this leads to the
expected value: \begin{align*}
\frac{n}{\binom{tn}{n-1}}\frac{2}{n-1}\binom{tn-t+1}{n-2}=\frac{2(tn-t+1)!(tn-n+1)!}
{t(tn-1)!(tn-n-t+3)!}\to
\frac{2(t-1)^{t-2}}{t^{t-1}}. \end{align*} The
variance evaluates to \begin{equation*}
\frac{n}{\binom{tn}{n-1}}\frac{6}{n-2}\binom{tn-2t+2}{n-3}+
\frac{2(tn-t+1)!(tn-n+1)!}
{t(tn-1)!(tn-n-t+3)!}-\bigg[\frac{2(tn-t+1)!(tn-n+1)!}
{t(tn-1)!(tn-n-t+3)!}\bigg]^2, \end{equation*}
which we do not attempt to simplify any
further.
Writing \begin{equation*}
G(z,v)=\sum_{n,k}g_{n,k}z^nv^k, \end{equation*}
it is possible to derive an explicit form for
the coefficients $g_{n,k}$, but they are not as
nice as the corresponding quantities in the
previous section: \begin{align*}
G(z,v)&=\sum_{k\ge0}(v-1)^kz^kT^{k+1}(z)\\
&=\sum_{n\ge0}z^n\sum_{k\ge0}(v-1)^k\frac{k+1}{n-k}\binom{tn-(t-1)k}{n-1-k}\\
&=\sum_{n\ge0}z^n\sum_{k\ge0}\sum_{0\le j\le
k}\binom
kjv^j(-1)^{k-j}\frac{k+1}{n-k}\binom{tn-(t-1)k}{n-1-k}.
\end{align*} This leads to \begin{equation*}
g_{n,j}=\sum_{j\le k\le n}\binom kj
(-1)^{k-j}\frac{k+1}{n-k}\binom{tn-(t-1)k}{n-1-k}.
\end{equation*}
The limiting distribution of $g_{n,j}/a_n$, for
$j$ fixed, must thus be determined in a
different way.
We need a crash course in asymptotic tree
enumeration here; all this can be found in
Flajolet and Sedgewick's book \cite{FlSe09},
but compare also an older paper by Meir and
Moon \cite{MeMo78}, in particular the notion of
\emph{simply generated families of trees}. The
procedure that we describe here is closely
related to the discussion in
\cite[Section IX-3]{FlSe09}, where very similar
parameters were analyzed.
We start from $u=z\phi(u)$, with
$\phi(u)=(1+u)^t$. The quantity $\tau$ is
determined via the equation
$\phi(\tau)=\tau\phi'(\tau)$. In our case this
leads to $\tau=\frac{1}{t-1}$. Then there is
the quantity $\rho=\frac{\tau}{\phi(\tau)}$,
which here evaluates to \begin{equation*}
\rho=\frac{(t-1)^{t-1}}{t^t}. \end{equation*}
Then one knows by general principles that the
function $u(z)$ has a square-root singularity
around $z=\rho$, with the local expansion
\begin{equation*} u\sim \tau-
\sqrt{\frac{2\tau}{\rho\phi{''}(\tau)}}\sqrt{1-z/\rho}.
\end{equation*} This is here \begin{equation*}
T(z)=1+u\sim
\frac{t}{t-1}-\sqrt{\frac{2t}{(t-1)^3}}\sqrt{1-z/\rho}.
\end{equation*} This expansion will now be used
inside of $G(z,v)$, with the result (Maple):
\begin{equation*} G(z,v)\sim a-\frac{\sqrt 2
t^{2t-3/2}}{(t-1)^{3/2}\big(t^{t-1}+(t-1)^{t-2}-(t-1)^{t-2}v\big)^2}\sqrt{1-z/\rho},
\end{equation*} with $a$ being an unimportant
constant. Note that \begin{equation*}
\frac{\sqrt 2
t^{2t-3/2}}{(t-1)^{3/2}\big(t^{t-1}+(t-1)^{t-2}-(t-1)^{t-2}v\big)^2}\Bigg|_{v=1}=
\sqrt{\frac{2t}{(t-1)^3}}. \end{equation*}
Thus, the limiting distribution is given by the
probability generating function
\begin{equation*}
\frac{t^{2t-2}}{\big(t^{t-1}+(t-1)^{t-2}-(t-1)^{t-2}v\big)^2}=
\frac{\frac{t^{2t-2}}{(t^{t-1}+(t-1)^{t-2})^2}}{\Big(1-\frac{(t-1)^{t-2}}{t^{t-1}+(t-1)^{t-2}}v\Big)^2}.
\end{equation*} The coefficient of $v^k$ in it
given by \begin{equation*}
(k+1)\frac{t^{2t-2}(t-1)^{(t-2)k}}{(t^{t-1}+(t-1)^{t-2})^{k+2}}.
\end{equation*} which is $\mathbb{P}\{Y=k+2\}$,
for a random variable $Y$, which follows the
negative binomial distribution with parameters
$r=2$ and
$p=\frac{t^{t-1}}{t^{t-1}+(t-1)^{t-2}}$, as
conjectured in \cite{CaMc16}.
\section{Acknowledgment}
Thanks are due to Stephan Wagner for stimulating feedback.
\begin{thebibliography}{1}
\bibitem{BaFl02}
C.~Banderier and P.~Flajolet, Basic analytic combinatorics of directed lattice
paths, {\em Theoret. Comput. Sci.} {\bf 281} (2002), 37--80.
\bibitem{CaMc16}
N.~T. Cameron and J.~E. McLeod, Returns and hills on generalized {D}yck paths,
{\em J. Integer Sequences} {\bf 19} (2016),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL19/McLeod/mcleod3.html}{Article 16.6.1}.
\bibitem{FlSe09}
P.~Flajolet and R.~Sedgewick, {\em Analytic Combinatorics}, Cambridge
University Press, 2009.
\bibitem{MeMo78}
A.~Meir and J.~W. Moon, On the altitudes of nodes in random trees, {\em Canad.
J. Math.} {\bf 30} (1978), 997--1015.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A15, 05A16; Secondary 60C05.
\noindent \emph{Keywords:} t-ary trees, Dyck paths, generating functions, negative binomial distribution, asymptotic tree enumeration.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A001764},
\seqnum{A006013},
\seqnum{A006629},
\seqnum{A006630}, and
\seqnum{A006631}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received June 27 2016;
revised versions received August 26 2016; August 27 2016.
Published in {\it Journal of Integer Sequences}, August 29 2016.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}