<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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)&amp;=\frac1{2\pi i}\oint\frac{dz}{z^{n+1}}T^k(z)\\
	&amp;=\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\\
	&amp;=[u^{n}](1+u-tu)(1+u)^{tn+k-1}\\
	&amp;=\binom{tn+k-1}{n}-(t-1)\binom{tn+k-1}{n-1}\\
	&amp;=\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)&amp;=[z^n]\Big(\frac{u}{1+u}\Big)^k\\
			&amp;=\frac1{2\pi
			i}\oint\frac{dz}{z^{n+1}}\Big(\frac{u}{1+u}\Big)^k\\
			&amp;=\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\\
			&amp;=[u^{n-k}](1+u-tu)(1+u)^{tn-1-k}\\
			&amp;=\binom{tn-1-k}{n-k}-(t-1)\binom{tn-1-k}{n-1-k}\\
			&amp;=\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}&amp;=[u^{n-d}]d!(1+u-tu)(1+u)^{tn}\\*
			&amp;=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)&amp;=\frac{d!}{2\pi i}\oint
			\frac{dz}{z^{n+1-d}}T^{d+1}(z)\\
			&amp;=\frac{d!}{2\pi i}\oint
			\frac{du(1+u-tu)(1+u)^{t(n-d)+d}}{u^{n+1-d}}\\
			&amp;=d![u^{n-d}](1+u-tu)(1+u)^{t(n-d)+d}\\
			&amp;=d!\binom{tn-(t-1)d}{n-d}-d!(t-1)\binom{tn-(t-1)d}{n-1-d}\\
			&amp;=\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)&amp;=\sum_{k\ge0}(v-1)^kz^kT^{k+1}(z)\\
			&amp;=\sum_{n\ge0}z^n\sum_{k\ge0}(v-1)^k\frac{k+1}{n-k}\binom{tn-(t-1)k}{n-1-k}\\
			&amp;=\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}




</pre></body></html>