\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}