\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \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} \usepackage{tikz} \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}}} \newcommand{\ignore}[1]{} \newcommand{\F}{F_3} \newcommand{\f}{\tilde{f}} \newcommand{\tL}{\tilde{L}} \newcommand{\tsL}{\tilde{\mathcal{L}}} \newcommand{\U}{\line(1,1){1}} \newcommand{\D}{\line(1,-1){1}} \newcommand{\DD}{\line(1,-2){1}} \newcommand{\vtx}{\circle*{.2}} \DeclareMathOperator{\Var}{Var} \DeclareMathOperator{\negbin}{negbin} \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 and Hills on Generalized Dyck Paths } \vskip 1cm \large Naiomi T. Cameron\\ Department of Mathematical Sciences \\ Lewis \& Clark College \\ Portland, OR 97219\\ USA\\ \href{mailto:ncameron@lclark.edu}{\tt ncameron@lclark.edu} \\ \ \\ Jillian E. McLeod\\ Department of Mathematics \\ U.S. Coast Guard Academy \\ New London, CT 06320\\ USA\\ \href{mailto:jillian.e.mcleod@uscga.edu}{\tt jillian.e.mcleod@uscga.edu}\\ \end{center} \vskip .2in \begin{abstract} In 2009, Shapiro posed the following question: ``What is the asymptotic proportion of Dyck paths having an even number of hills?" In this paper, we answer Shapiro's question, as well as a generalization of the question to ternary paths. We find that the probability that a randomly chosen ternary path has an even number of hills approaches $125/169$ as the length of the path approaches infinity. Our strategy relies on properties of the Fine number sequence and extends certain relationships between the Catalan and Fine number generating functions. \end{abstract} \section{Introduction}\label{introduction} Much has been written about patterns of returns and hills on Dyck paths, which are enumerated by the Catalan numbers. Here we begin by extending some of those results to the setting of the sequence, $$t_n=\frac{1}{2n+1}\binom{3n}{n},$$ which we will henceforth refer to as the {\em ternary numbers.}\footnote{The reader should not confuse our use of the term ``ternary numbers" with any unrelated synonym for base $3$ numbers.} The ternary numbers (\seqnum{A001764}) are a well-known sequence, appearing often throughout the literature and having many interpretations. For example, Stanley \cite[Exercise 5.45--46]{stanley2} documents the ternary numbers counting noncrossing trees with $n$ edges (see Figure \ref{noncrossingtrees}), recursively labeled forests on $[n]$, and plane ternary trees with $3n+1$ vertices. Bearing these combinatorial interpretations in mind, it is not difficult to see that the generating function for the ternary numbers $T(z)=\sum_{n=0}^\infty{t_nz^n}$ satisfies the cubic equation \begin{equation}T(z)=1+zT^3(z).\label{cubicequation}\end{equation} For example, equation (\ref{cubicequation}) can be explained in terms of non-crossing trees by noting that every noncrossing tree is either empty or can be pictorially decomposed as \begin{center} \setlength{\unitlength}{.65cm} \begin{picture}(8,2) \put(0,0){\vtx} \put(6,0){\vtx} \qbezier(0, 0)(3,3)(6, 0) \qbezier(0, 0)(1,.75)(2, 0) \qbezier(0, 0)(1,-.75)(2, 0) \qbezier(6, 0)(5,.75)(4, 0) \qbezier(6, 0)(5,-.75)(4, 0) \qbezier(6, 0)(7,.75)(8, 0) \qbezier(6, 0)(7,-.75)(8, 0) \put(.75,-0.1){$\mathcal{T}_1$} \put(4.75,-0.1){$\mathcal{T}_2$} \put(6.75,-0.1){$\mathcal{T}_3$} \end{picture} \end{center} \medskip \noindent where each of $\mathcal{T}_1$, $\mathcal{T}_2$ and $\mathcal{T}_3$ is a noncrossing tree. Since each edge of a noncrossing tree is associated with a $z$ in $T(z)$ and $T(z)$ is the generating function for $\mathcal{T}_1$, $\mathcal{T}_2$ and $\mathcal{T}_3$, we obtain the relationship in (\ref{cubicequation}). \begin{figure} \begin{center} \setlength{\unitlength}{.5cm} \begin{picture}(24,4) \multiput(0,0)(1,0){24}{\vtx} \multiput(0,2)(1,0){24}{\vtx} \qbezier(0, 2)(0.5,2.5)(1, 2) \qbezier(0, 2)(1,3)(2, 2) \qbezier(0, 2)(1.5,3.5)(3, 2) \qbezier(4, 2)(5.5,3.5)(7, 2) \qbezier(4, 2)(4.5,2.5)(5, 2) \qbezier(5, 2)(5.5,2.5)(6, 2) \qbezier(8, 2)(8.5,2.5)(9, 2) \qbezier(10, 2)(10.5,2.5)(11, 2) \qbezier(8, 2)(9.5,3.5)(11, 2) \qbezier(12,2)(12.5,2.5)(13,2) \qbezier(13,2)(13.5,2.5)(14,2) \qbezier(13,2)(14,3)(15,2) \qbezier(16,2)(16.5, 2.5)(17,2) \qbezier(18,2)(18.5,2.5)(19,2) \qbezier(17,2)(18,3)(19,2) \qbezier(20,2)(20.5,2.5)(21,2) \qbezier(21,2)(21.5,2.5)(22,2) \qbezier(22,2)(22.5,2.5)(23,2) \qbezier(0,0)(0.5,0.5)(1,0) \qbezier(2,0)(2.5,0.5)(3,0) \qbezier(0,0)(1,1)(2,0) \qbezier(4,0)(5,1)(6,0) \qbezier(5,0)(5.5,0.5)(6,0) \qbezier(4,0)(5.5,1.5)(7,0) \qbezier(8,0)(9.5,1.5)(11,0) \qbezier(9,0)(10,1)(11,0) \qbezier(10,0)(10.5,0.5)(11,0) \qbezier(12,0)(13.5, 1.5)(15,0) \qbezier(13,0)(14,1)(15,0) \qbezier(13,0)(13.5,0.5)(14,0) \qbezier(16,0)(17.5,1.5)(19,0) \qbezier(17,0)(17.5,0.5)(18,0) \qbezier(18,0)(18.5,0.5)(19,0) \qbezier(20,0)(21,1)(22,0) \qbezier(21,0)(21.5,0.5)(22,0) \qbezier(22,0)(22.5,0.5)(23,0) \end{picture} \end{center} \caption{There are $t_3=12$ non-crossing trees with 4 vertices.} \label{noncrossingtrees} \end{figure} The ternary numbers can be considered an analogue of the Catalan number sequence \seqnum{A000108}, $c_n=\frac{1}{n+1}\binom{2n}{n},$ whose generating function $C(z)=\sum_{n=0}^\infty{c_nz^n}$ satisfies $C(z)=1+zC^2(z)$ and has the closed form $$C(z)=\frac{1-\sqrt{1-4z}}{2z^2}.$$ Among many other interpretations, the Catalan numbers count {\em Dyck paths}, which are paths that start at $(0,0)$, end at $(2n,0)$, use up steps $U$ of the form $(1,1)$, down steps $D$ of the form $(1,-1)$ and never go below the $x$-axis. For example, $UUDUDD$ is a Dyck path of length $6$ and there are a total of $c_3=5$ possible Dyck paths of length $6$. (See Figure \ref{dyckpaths}.) \begin{figure} \begin{center} \setlength{\unitlength}{.4cm} \begin{picture}(18,6) \put(0,4){\U} \put(1,5){\D} \put(2,4){\U} \put(3,5){\D} \put(4,4){\U} \put(5,5){\D} \put(7,4){\U} \put(8,5){\D} \put(9,4){\U} \put(10,5){\U} \put(11,6){\D} \put(12,5){\D} \put(14,4){\U} \put(15,5){\U} \put(16,6){\D} \put(17,5){\D} \put(18,4){\U} \put(19,5){\D} \put(0,0){\U} \put(1,1){\U} \put(2,2){\D} \put(3,1){\U} \put(4,2){\D} \put(5,1){\D} \put(7,0){\U} \put(8,1){\U} \put(9,2){\U} \put(10,3){\D} \put(11,2){\D} \put(12,1){\D} \put(0,4){\vtx} \put(1,5){\vtx} \put(2,4){\vtx} \put(3,5){\vtx} \put(4,4){\vtx} \put(5,5){\vtx} \put(7,4){\vtx} \put(8,5){\vtx} \put(9,4){\vtx} \put(10,5){\vtx} \put(11,6){\vtx} \put(12,5){\vtx} \put(14,4){\vtx} \put(15,5){\vtx} \put(16,6){\vtx} \put(17,5){\vtx} \put(18,4){\vtx} \put(19,5){\vtx} \put(0,0){\vtx} \put(1,1){\vtx} \put(2,2){\vtx} \put(3,1){\vtx} \put(4,2){\vtx} \put(5,1){\vtx} \put(7,0){\vtx} \put(8,1){\vtx} \put(9,2){\vtx} \put(10,3){\vtx} \put(11,2){\vtx} \put(12,1){\vtx} \put(6,0){\vtx} \put(13,0){\vtx} \put(6,4){\vtx} \put(13,4){\vtx} \put(20,4){\vtx} \end{picture} \end{center} \caption{Of the $c_3=5$ Dyck paths of length 6 there are two with no hills.} \label{dyckpaths} \end{figure} One way to generalize Dyck paths is to hold the length of the down step $D$ as a parameter. \begin{definition} Let $t\geq 0$. A {\em $t$-Dyck path} is a path from $(0,0)$ to $(tn,0)$ where $n\geq 0$ with step set $\{U(1,1)\}\cup\{D(1,-t+1)\}$ which never goes below the $x$-axis. \end{definition} \begin{figure} \begin{center} \begin{tikzpicture} [scale=.4,auto=left] \tikzstyle{black} = [circle, minimum width=2pt, fill, inner sep=0pt] \draw [semithick] (0,0) -- (1,1) -- (2,2) -- (3,3) -- (4,4) -- (5, 2) -- (6,0); \node[black] at (0,0) {}; \node[black] at (1,1) {}; \node[black] at (2,2) {}; \node[black] at (3,3) {}; \node[black] at (4,4) {}; \node[black] at (5,2) {}; \node[black] at (6,0) {}; \draw [semithick] (7,0) -- (8,1) -- (9,2) -- (10,3) -- (11,1) -- (12, 2) -- (13,0); \node[black] at (7,0) {}; \node[black] at (8,1) {}; \node[black] at (9,2) {}; \node[black] at (10,3) {}; \node[black] at (11,1) {}; \node[black] at (12,2) {}; \node[black] at (13,0) {}; \draw [semithick] (14,0) -- (15,1) -- (16,2) -- (17,0) -- (18,1) -- (19, 2) -- (20,0); \node[black] at (14,0) {}; \node[black] at (15,1) {}; \node[black] at (16,2) {}; \node[black] at (17,0) {}; \node[black] at (18,1) {}; \node[black] at (19,2) {}; \node[black] at (20,0) {}; \end{tikzpicture} \end{center} \caption{Of the $t_2=3$ ternary paths of length 6, there are two with no hills. \label{fig:ternarypaths}} \end{figure} In the case where $t=3$, we obtain so-called {\em ternary paths} which are counted by the ternary numbers. For example, $UUUDUD$ is one of the $3$ possible ternary paths of length $6$. (See Figure \ref{fig:ternarypaths}.) Using a decomposition argument similar to that used for noncrossing trees, one can show that $T(z)$ is the generating function for the number of ternary paths of length $3n$. In general, it is known that the number of $t$-Dyck paths of length $tn$ is the generalized Catalan number $$\frac{1}{(t-1)n+1}\binom{tn}{n}.$$ Let $C_t(z)$ denote the generating function for the generalized Catalan numbers, that is, $$C_t(z)=\sum_{n=0}^\infty{\frac{1}{(t-1)n+1}\binom{tn}{n}z^n}.$$ The fact that $$C_t(z)=1+z(C_t(z))^t$$ follows immediately from the fact that every $t$-Dyck path is either the empty path or has the form $U\mathcal{P}_1U\mathcal{P}_2U\mathcal{P}_3\cdots U\mathcal{P}_{t-1}D\mathcal{P}_t$ where each $\mathcal{P}_i$ is a $t$-Dyck path. Note that $C_0(z)=1$, $C_1(z)=1/(1-z)$, $C_2(z)=C(z)$ is the generating function for the Catalan numbers and \begin{equation} C_3(z)=T(z)\label{gfternarynos}\end{equation} is the generating function for the ternary numbers $t_n=\frac{1}{2n+1}\binom{3n}{n}$. We also want to point out a fact that we use often in this paper. Adopting the conventional notation $[z^n]A(z)$ to denote the coefficient of $z^n$ in a formal power series $A(z)$, we note that Graham et al.\ \cite{graham} showed via the cycle lemma that \begin{equation} [z^n]C_t^s(z)=\frac{s}{tn+s} \binom{tn+s}{n}.\label{powersofC_t}\end{equation} In this more general context, we want to consider a few of the commonly studied statistics on Dyck paths. One common statistic for Dyck paths is the number of returns. A {\em return} on a $t$-Dyck path is a non-origin point on the path with ordinate 0. An {\em elevated $t$-Dyck path} is a $t$-Dyck path with exactly one return. Notice that an elevated $t$-Dyck path has the form $U\mathcal{P}_1U\mathcal{P}_2U\mathcal{P}_3\cdots U\mathcal{P}_{t-1}D$ where each $\mathcal{P}_i$ is a $t$-Dyck path. Therefore, we know that the generating function for the number of elevated $t$-Dyck paths is $z(C_t(z))^{t-1}$. In Section \ref{returns}, we provide a limiting distribution for the number of returns on $t$-Dyck paths. Another common statistic associated with Dyck paths is the number of peaks at a certain height. A {\em peak} in a $t$-Dyck path is an occurrence of the sequence $UD$ and the {\em height} of a peak is the ordinate of the intersection of its two steps. For Dyck paths, a peak of height one is also known as a hill. More generally though, for $t\geq 1$, we define a {\em hill} in a $t$-Dyck path as a ground level subpath of the form $U^{t-1}D$. Note that a hill in a $t$-Dyck path is not generally the same as a peak of height $t-1$. For instance, there are two $3$-Dyck paths of length 6 having no hills, while there is just one $3$-Dyck path of length 6 having no peaks at height 2. (See Figure \ref{fig:ternarypaths}.) In this paper, we are more concerned with hills than peaks. Any discussion of hills among Dyck paths will surely include references to the Fine numbers (\seqnum{A000957}). The Fine number sequence, which begins $$1, 0, 1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724, 91144, \ldots$$ has a number of interesting connections to the Catalan sequence. In this paper, $f_n$ will denote the $n$th Fine number and $F(z)=\sum_{k=0}^\infty{f_nz^n}$ will denote the generating function for the Fine numbers, which in its closed form, is $$F(z)=\frac{1-\sqrt{1-4z}}{z(3-\sqrt{1-4z})}.$$ The Fine number sequence is well documented in the literature, notably as the subject of some surveys \cite{barcucci, cheon, deutsch0, deutsch1}. Among their numerous applications, the Fine numbers count Dyck paths of length $2n$ having no hills. For example, of the five Dyck paths of length 6, there are $f_3=2$ having no hills. See Figure \ref{dyckpaths}. In Sections \ref{ternaryfine} and \ref{genfinemotzkin} of this article, we describe and interpret a natural analogue of the Fine number sequence for $t$-Dyck paths. The Motzkin numbers (\seqnum{A001006}) form another combinatorial sequence with deep connections to the Catalan numbers. The Motzkin numbers $\{m_n\}$ count {\em Motzkin paths}, which are paths from $(0,0)$ to $(n,0)$ with step set $\{U(1,1),L(1,0),D(1,-1)\}$ which never go below the $x$-axis. If we modify Motzkin paths by requiring that the level step take one of two possible colors, then $C^2(z)$ is the generating function for the number of resulting paths. With the further restriction of no level steps on the $x$-axis, the generating function is $F(z)$. In the effort to describe a Fine analogue for $t$-Dyck paths, there is a natural encounter with a Motzkin analogue for $t$-Dyck paths, as we will see in Section \ref{genfinemotzkin}. At various points in the paper, we will encounter Riordan arrays. A {\em Riordan array} $\mathcal{R}=(g(z),f(z))$ is an infinite lower triangular matrix whose $k$th column has a generating function given by $g(z)f^k(z)$ with $g(0)\neq 0$ and $f(0)=0$. It is sometimes helpful to use Riordan arrays to summarize statistics on paths and other combinatorial objects and we will do so here when convenient. For example, the entry in row $n$ and column $k$ (where $n,k\geq 0$) of the Riordan array (\seqnum{A033184}) \begin{equation} \big(C(z),zC(z)\big)=\left( \begin{array}{cccccccc} 1 &&&&&&&\\ 1 & 1 &&&&&&\\ 2 & 2 & 1 &&&&&\\ 5 & 5 & 3 & 1 &&&&\\ 14 & 14 & 9 & 4 & 1 &&&\\ 42 & 42 & 28 & 14 & 5 & 1 &&\\ 132 & 132 & 90 & 48 & 20 & 6 & 1 &\\ &&&\dots&&&&\\ \end{array} \right), \label{CzC} \end{equation} is $[z^n]z^kC^{k+1}(z)$, the coefficient of $z^n$ in $z^kC^{k+1}(z)$. Note also that $[z^n]z^kC^{k+1}(z)$ is the number of Dyck paths of length $2(n+1)$ having exactly $k+1$ returns to the $x$-axis. Riordan arrays form a group under matrix multiplication known as the Riordan group, which has served as both a tool and object of combinatorial study \cite{riordangroupreference1}. The product of two Riordan arrays is given by $$\left(g_1(z),f_1(z)\right)* \left(g_2(z),f_2(z)\right)=\left(g_1(z) g_2(f_1(z)),f_2(f_1(z))\right).$$ One can also express the product of a Riordan array and an infinite column vector as $$\left(g_1(z),f_1(z)\right)* h(z)=g_1(z) h(f_1(z)),$$ where $h(z)$ is the generating function for the entries of an infinite column vector. In the study of returns and hills among $t$-Dyck paths, we will encounter the {\em negative binomial} distribution, which often shows up in combinatorial statistics \cite{flajolet}, and we wish to remind the reader about the characteristics of a negative binomial distribution. In general, we say $Y$ has the negative binomial distribution with parameters $r,p$ and write $Y\sim\negbin(r,p)$, when $$P(Y=k)=\binom{k-1}{r-1}p^r(1-p)^{k-r},$$ or equivalently, $Y$ is the random variable for the trial at which the $r$th success occurs in a sequence of Bernoulli trials with success probability $p$. The distribution $\negbin(r,p)$ is known to have expected value $E(Y)=\frac{r(1-p)}{p}$ and variance $\Var(Y)=\frac{r(1-p)}{p^2}$. The article is organized as follows. In Section \ref{returns-hills}, we consider the asymptotic distribution for the number of returns and the number of hills among $t$-Dyck paths. In Section \ref{even-dyck}, we compute exact probabilities for the number of hills among Dyck paths of length $2n$ in order to determine the asymptotic proportion of Dyck paths having an even number of hills. We also introduce an analogue of the Fine numbers for the ternary numbers and determine the asymptotic probability that a ternary path has an even number of hills. In Section \ref{genfinemotzkin}, we describe a Fine analogue for $C_t(z)$ in terms of colored Motzkin-like paths and we present a combinatorial identity involving its generating function. \section{Returns and hills via the Riordan group} \label{returns-hills} In this section, we use the Riordan group to study the number of returns and hills among ternary paths. The ultimate goal is to determine the limiting distribution for the number of returns and for the number of hills among $t$-Dyck paths. \subsection{The number of returns among ternary paths, \texorpdfstring{$t$}{Lg}-Dyck paths} \label{returns} First, we describe the generating function for the number of ternary paths having a given number of returns. Recall from equation (\ref{gfternarynos}) that $C_3(z)=T(z)$ is the generating function for the number of ternary paths. \begin{proposition} Let $T(z)$ be the generating function for the number of ternary paths. For $0\leq m\leq n$, $z^mT^{2m}(z)$ is the generating function for the number of ternary paths of length $3n$ having exactly $m$ returns to the $x$-axis. \label{gfternarypathswithmreturns} \end{proposition} \begin{proof} Any ternary path of length $3n$ where $n\geq 1$ has at least one return, i.e., the empty path is the only path with no returns. For $n\geq 0$, any nonempty ternary path of length $3n$ with exactly $m$ returns must has the form $$(U{P}_1U{Q}_1D)(U{P}_2U{Q}_2D)(U{P}_3U{Q}_3D)\cdots (U{P}_mU{Q}_mD)$$ where each $P_i$, $Q_i$ is a (possibly empty) ternary path. When counting ternary paths with $T(z)$, each $D$ is associated with a $z$, so the generating function for the number of ternary paths with exactly $m$ returns is $z^mT^{2m}(z)$. \end{proof} If $r_{n,m}$ denotes the number of ternary paths of length $3n$ having $m$ returns to the $x$-axis, then the following array (\seqnum{A109971}) \begin{equation} (r_{n,m})_{n,m \geq 0}=\left( \begin{array}{cccccccc} 1 &&&&&&&\\ 0 & 1 &&&&&&\\ 0 & 2 & 1 &&&&&\\ 0 & 7 & 4 & 1 &&&&\\ 0 & 30 & 18 & 6 & 1 &&&\\ 0 & 143 & 88 & 33 & 8 & 1 &&\\ 0 & 728 & 455 & 182 & 52 & 10 & 1 &\\ &&&\dots&&&&\\ \end{array} \right)= \big(1,zT^2(z)\big), \label{ternaryreturnsmatrix} \end{equation} is a Riordan array whose row sums are the ternary numbers. \begin{theorem} The probability that a randomly chosen ternary path has $m$ returns approaches $\frac{4m}{3^{m+1}}$ as path length approaches infinity. The asymptotic distribution for the (nonzero) number of returns among ternary paths is the negative binomial distribution with parameters $2$ and $2/3$. Hence, the expected number of returns among ternary paths approaches $2$ with variance $3/2$. \label{ternaryreturns} \end{theorem} \begin{proof} We proceed by calculating the associated probabilities. Let $Y_n\geq 0$ denote the number of returns for a ternary path of length $3n$. Let $p_m(n)$ be the probability that a randomly chosen ternary path of length $3n$ has $m$ returns, that is, $p_m(n)=P(Y_n=m)$. We know from Proposition \ref{gfternarypathswithmreturns} that the generating function for the number of paths with $m$ returns is $z^mT^{2m}(z)$. Making use of (\ref{powersofC_t}), we obtain \begin{eqnarray*} p_m(n)&=&{ \frac{[z^n]z^mT^{2m}(z)}{[z^n]T(z)} }\\ &=& \frac{{ \frac{2m}{3(n-m)+2m}}{\binom{3(n-m)+2m}{n-m}}}{{\frac{1}{2n+1}}{\binom{3n}{n}}} \\ &=&\frac{2m(2n+1)(n-m+1)(n-m+2) \cdot \cdot \cdot (n-1)}{3(3n-m)(3n-m+1)(3n-m+2) \cdot \cdot \cdot (3n-1)}\\ &=&\frac{2m(2n+1)(n-1)^{\underline{m-1}}}{3(3n-1)^{\underline{m}} } \end{eqnarray*} where $x^{\underline{j}} = x(x-1)(x-2)\cdots(x-j+1)$. It follows immediately that as $n\to\infty$, $$p_m(n)\to\frac{4m}{3^{m+1}}=\binom{(m+1)-1}{1}\left(\frac{2}{3}\right)^2\left(\frac{1}{3}\right)^{(m+1)-2}=P(Y=m+1)$$ where $m\geq 0$ and $Y\sim \negbin(2,\frac{2}{3})$. So, we see that $p_m(n)\to P(Y=m+1)$ where $Y\sim \negbin(2,\frac{2}{3})$. Notice that $Y_n=0$ if and only if $n=0$. So if we wish to restrict to the case where the number of returns is nonzero, we may consider $Y_n+1$. Since $E(Y)=\frac{2(1/3)}{2/3}=1$, we can conclude that $E(Y_n+1)=E(Y_n)+1 \to E(Y)+1=2$ and $\Var(Y_n+1)=\Var(Y_n)\to \Var(Y)=\frac{E(Y)}{2/3}=\frac{3}{2}$. We can also use the Riordan group to determine (exactly) $E(Y_n)$, the expected number of returns among ternary paths of length $3n$. Observe that the total number of returns among all ternary paths of length $3n$ is given by the generating function for the infinite column vector, $$\left( \begin{array}{cccccccc} 1 &&&&&&&\\ 0 & 1 &&&&&&\\ 0 & 2 & 1 &&&&&\\ 0 & 7 & 4 & 1 &&&&\\ 0 & 30 & 18 & 6 & 1 &&&\\ 0 & 143 & 88 & 33 & 8 & 1 &&\\ 0 & 728 & 455 & 182 & 52 & 10 & 1 &\\ &&&\dots&&&&\\ \end{array} \right) \left( \begin{array}{c} 0\\1\\2\\3\\4\\5\\6\\ \vdots \end{array} \right),$$ where the matrix on the left is given in equation (\ref{ternaryreturnsmatrix}). In terms of Riordan group multiplication, this product is \begin{eqnarray*} (1,zT^2(z))*\frac{z}{(1-z)^2}&=&\frac{zT^2(z)}{(1-zT^2(z))^2}\\ &=&z\left(\frac{T}{1-zT^2}\right)^2\\ &=&zT^4. \end{eqnarray*} The last equality follows from the fact that \begin{equation} \frac{T}{1-zT^2}=\frac{T^2}{T-zT^3}=\frac{T^2}{1}=T^2.\label{T^2identity}\end{equation} Hence, the expected number of returns among ternary paths of length $3n$ is \begin{eqnarray*} E(Y_n)&=& \frac{[z^{n}]zT^4}{[z^{n}]T}\\ &=&\frac{ \frac{4}{3(n-1)+4}\binom{3(n-1)+4}{n-1} }{ \frac{1}{2n+1}\binom{3n}{n} }\\ &=& \frac{ 4(3n+1)n }{ (3n+1)(2n+2) }\\ &=&\frac{2n}{n+1}. \end{eqnarray*} And we have verified that indeed, the expected number of returns for ternary paths approaches 2. We may also compute (exactly) the variance $\Var Y_n$ by considering the square of the number of returns. Notice that \begin{eqnarray*} \left( \begin{array}{cccccccc} 1 &&&&&&&\\ 0 & 1 &&&&&&\\ 0 & 2 & 1 &&&&&\\ 0 & 7 & 4 & 1 &&&&\\ 0 & 30 & 18 & 6 & 1 &&&\\ 0 & 143 & 88 & 33 & 8 & 1 &&\\ 0 & 728 & 455 & 182 & 52 & 10 & 1 &\\ &&&\dots&&&&\\ \end{array} \right) \left( \begin{array}{c} 0\\1\\4\\9\\16\\25\\36\\ \vdots \end{array} \right)&=& (1,zT^2(z))*\frac{z+z^2}{(1-z)^3}\\ &=&\frac{zT^2}{(1-zT^2)^3}+\frac{z^2T^4}{(1-zT^2)^3}\\ &=&\frac{zT^4}{1-zT^2}+z^2T^7\\ &=&zT^5+z^2T^7 \end{eqnarray*} which implies that \begin{eqnarray*} \Var Y_n&=&EY_n^2-(EY_n)^2\\ &=& \frac{[z^{n}]zT^5+z^2T^7}{[z^{n}]T}-\left(\frac{2n}{n+1}\right)^2\\ &=&\frac{ \frac{4}{3(n-1)+4}\binom{3(n-1)+4}{n-1} }{ \frac{1}{2n+1}\binom{3n}{n} }\\ \end{eqnarray*} and $\Var\ Y_n\to\frac{3}{2}$ as $n\to\infty$. \end{proof} Now in the case of Dyck paths, the expected number of returns approaches 3 with variance 4 and the limiting distribution is $\negbin(2,\frac{1}{2})$. Naturally, it would be nice to know the corresponding statistics for generalized Dyck paths, and it is possible do so given the fact that the generating function for the number $t$-Dyck paths having exactly $m$ returns is $z^mC_t^{(t-1)m}(z)$. The necessary calculations that follow proceed almost exactly as above and we obtain the following result. \begin{theorem} Let $Y_n$ denote the random variable for the number of returns among $t$-Dyck paths of length $tn$ and let $\displaystyle Y=\lim_{n\to\infty}{Y_n}$. Then $$Y\sim \negbin \left(2,\frac{t-1}{t}\right)$$ Hence, the expected number of returns among nontrivial $t$-Dyck paths approaches $\frac{t+1}{t-1}$ with variance $\frac{2t}{(t-1)^2}$. \end{theorem} \begin{proof} If $Y_n$ denotes the number of returns among $t$-Dyck paths of length $tn$, then $$P(Y_n=m)= \frac{{(t-1)m((t-1)n+1)n^{\underline{m}} }}{tn(tn-1)^{\underline{m}}} $$ which approaches $$\frac{m(t-1)^2}{t^{m+1}}=\binom{m+1-1}{2-1}\left(\frac{t-1}{t}\right)^2\left(\frac{1}{t}\right)^{m-1}$$ as $n\to\infty$. \end{proof} \subsection{The number of hills among ternary paths, \texorpdfstring{$t$}{Lg}-Dyck paths} \label{hills} We begin this subsection with the observation that the formula for the number of ternary paths of length $3n$ having exactly $k$ hills is not as nice as the formula we saw for the number of returns in the previous subsection. This is due to the fact that counting hills among ternary paths requires an analogue to the Fine numbers. Let $F_t(z)$ be the generating function for the number of $t$-Dyck paths of length $tn$ having no hills. (In the case where $t=2$, $F_t(z)$ is the generating function for the Fine numbers.) It follows that the generating function for the number of $t$-Dyck paths of length $tn$ having exactly $m$ hills is $z^m F_t^m(z)$ and the $n$th row of the Riordan array $(F_t(z),zF_t(z))$ gives a distribution of the $t$-Dyck paths of length $tn$ by number of hills. Though there is no closed formula for the entries of $(F_t(z),zF_t(z))$, there is much that can be said about this Riordan array and in Sections \ref{ternaryfine} and \ref{genfinemotzkin}, we indulge the reader with more detail in the case when $t=3$. The following identity extends naturally from the relationship between the Catalan and Fine numbers: \begin{equation} \displaystyle C_t(z)=\frac{F_t(z)}{1-zF_t(z)}\iff F_t(z)=\frac{C_t(z)}{1+zC_t(z)} \label{catfine1} \end{equation} Because this identity will come in handy now, we will use it here without proof. However, the interested reader is directed to Theorem \ref{catalanfineidentity} in Section \ref{genfinemotzkin} for further exploration and justification of (\ref{catfine1}). Because there is no nice closed formula for the number of hills among $t$-Dyck paths, some care must be taken to give a closed formula for the exact probability that a ternary path has a given number of hills. Again, we defer to Section \ref{ternaryfine} for the necessary details regarding this computation. At present, however, we can use the Riordan group to compute the moments for the asymptotic distribution of hills among ternary paths, and in fact more generally, among $t$-Dyck paths. \begin{theorem} The expected number of hills among $t$-Dyck paths approaches $\frac{2}{t}\left(\frac{t-1}{t}\right)^{t-2}$ with variance $\frac{2}{t}\left(\frac{t-1}{t}\right)^{t-2} \left( \frac{ t^{t-1}+(t-1)^{t-2} }{ t^{t-1} } \right) $ as path length approaches infinity. In particular, the expected number of hills among ternary paths approaches $\frac{4}{9}$ with variance $\frac{44}{81}$. \end{theorem} \begin{proof} Let $X_n$ denote the random variable for the number of hills on a $t$-Dyck path of length $tn$. It is relatively straightforward to compute the first moment $E(X_n)$. The generating function for the total number of hills among $t$-Dyck paths is simply $zC_t^2(z)$ --- this is true because every hill is preceded and followed by a $t$-Dyck path of some length. Hence, \begin{align*} E(X_n)&=\frac{[z^n]zC_t^2}{[z^n]C_t}=\frac{[z^{n-1}]C_t^2}{[z^n]C_t}\\ &= \frac{ \frac{2}{t(n-1)+2}\binom{t(n-1)+2}{n-1} }{ \frac{1}{(t-1)n+1}\binom{tn}{n} }\\ &=\frac{ 2n(tn-(t-1))!((t-1)n+1)! }{ (tn)!((t-1)n-(t-3))! }\\ &=\frac{2((t-1)n+1)^{\underline{t-2}}}{t(tn-1)^{\underline{t-2}}}, \end{align*} where $x^{\underline{j}} = x(x-1)(x-2)\cdots(x-j+1)$. Consequently, we see that $E(X_n)\to \frac{2}{t}\left(\frac{t-1}{t}\right)^{t-2}$ as $n\to \infty$. To compute the second moment $E(X_n^2)$, we need to compute the sum of the squares of the number of hills among $t$-Dyck paths of length $tn$. Here, we will make use of Riordan group algebra. Given that the generating function for the sequence of squares is $\frac{z+z^2}{(1-z)^3}$, we want to consider the sequence obtained by the Riordan product \begin{align*} (F_t,zF_t)* \frac{z+z^2}{(1-z)^3}&= \frac{zF_t^2+z^2F_t^3}{(1-zF_t)^3}\\ &=\frac{zF_t^2}{(1-zF_t)^3}+z^2C_t^3\\ &=\frac{zC_t^3}{\frac{C_t}{1+zC_t}}+z^2C_t^3\\ &=zC_t^2+2z^2C_t^3, \end{align*} which gives us the sum of the squares of the number of hills among $t$-Dyck paths. Hence, the second moment is \begin{align*} E(X_n^2)&=\frac{[z^n]zC_t^2+2z^2C_t^3}{[z^n]C_t}\\ &=E(X_n)+\frac{[z^{n-2}]2C_t^3}{[z^n]C_t}\\ &=E(X_n)+2\frac{\frac{3}{t(n-2)+3}\binom{t(n-2)+3}{n-2} }{ \frac{1}{(t-1)n+1}\binom{tn}{n} }\\ &=\frac{2((t-1)n+1)^{\underline{t-2}}}{t(tn-1)^{\underline{t-2}}}+\frac{6(n-1)n}{(t(n-2)+3)(t(n-2)+4)} \frac{((t-1)n+1)^{\underline{2t-4}}}{(tn)^{\underline{2t-4}}} \end{align*} and $E(X_n^2)\to \frac{2}{t}\left(\frac{t-1}{t}\right)^{t-2} + \frac{6}{t^2}\left(\frac{t-1}{t}\right)^{2t-4}= \frac{2}{t}\left(\frac{t-1}{t}\right)^{t-2} \left( \frac{ t^{t-1}+3(t-1)^{t-2}}{t^{t-1}} \right) $ Now, we may compute the variance of $X_n$ as follows \begin{align*} \Var(X_n)&= E(X_n^2)-(E(X_n))^2\\ &= \frac{2((t-1)n+1)^{\underline{t-2}}}{t(tn-1)^{\underline{t-2}}}+\frac{6(n-1)n}{(t(n-2)+3)(t(n-2)+4)} \frac{((t-1)n+1)^{\underline{2t-4}}}{(tn)^{\underline{2t-4}}}\\ & - \left(\frac{2((t-1)n+1)^{\underline{t-2}}}{t(tn-1)^{\underline{t-2}}}\right)^2 \end{align*} and notice that $\Var(X_n)\to \frac{2}{t}\left(\frac{t-1}{t}\right)^{t-2} + \frac{6}{t^2}\left(\frac{t-1}{t}\right)^{2t-4}-\frac{4}{t^2}\left(\frac{t-1}{t}\right)^{2t-4}= \frac{2}{t}\left(\frac{t-1}{t}\right)^{t-2} \left( \frac{ t^{t-1}+(t-1)^{t-2} }{ t^{t-1} } \right) $ as $n\to\infty$. \end{proof} The relationship between the asymptotic mean and variance for the number of hills provides the initial evidence for the following conjecture. \begin{conjecture} Let $X_n$ denote the random variable for the number of hills among $t$-Dyck paths of length $tn$ and let $\displaystyle X=\lim_{n\to\infty}{X_n}$. Then $$X\sim \negbin\left(2, \frac{t^{t-1}}{t^{t-1}+(t-1)^{t-2}}\right)$$ \end{conjecture} The evidence for this conjecture is based on verification of the result in the case where $t\leq 3$ (see Section \ref{even-dyck}) and the computation of the moments $E(X_n^m)$. To compute $E(X_n^m)$, we consider the $m$th power of the number of hills. The generating function for the power sequence $0^m,1^m,2^m,3^m,\dots$ is $\displaystyle \frac{e_m(z)}{(1-z)^{m+1}}$, where $$e_m(z)=\sum_{k=1}^m{e_{m,k}z^k}$$ is the Eulerian polynomial of degree $m$ and $$e_{m,k}=\displaystyle \sum_{j=0}^k{(-1)^j(k-j)^m\binom{m+1}{j} }$$ are the Eulerian numbers (\seqnum{A008292}). To find the $m$th moment for the number of hills, we consider the Riordan product \begin{align*} (F_t,zF_t)* \frac{e_m(z)}{(1-z)^{m+1}} &= \displaystyle\sum_{k=1}^m{e_{m,k} \frac{z^kF_t^{k+1}}{(1-zF_t)^{m+1}} } \end{align*} Now we may compute the expected value of $X_n^m$, making use of identity (\ref{catfine1}), as follows: \begin{align*} E(X_n^m)&=\frac{[z^n] \displaystyle\sum_{k=1}^m{e_{m,k} \frac{z^kF_t^{k+1}}{(1-zF_t)^{m+1}} }}{[z^n] C_t} \\ &=\frac{ \displaystyle\sum_{k=1}^m{e_{m,k}\ [z^n]\ z^kC_t^{k+1} \left(\frac{C_t}{F_t}\right)^{m-k} } }{[z^n] C_t} \\ &=\displaystyle \sum_{k=1}^m{e_{m,k}\ \frac{ [z^{n-k}]\ C_t^{k+1}(1+zC_t)^{m-k} }{[z^n] C_t } }\\ &= \sum _{k=1}^m \left(\sum _{j=0}^{m-k}{ e_{m,k} \binom{m-k}{j} \frac{ \frac{j+k+1}{t(n-(j+k))+j+k+1} \binom{t(n-(j+k))+j+k+1}{n-(j+k)}}{ \frac{1}{tn+1} \binom{tn+1}{n} }} \right)\\ &= \frac{1}{ [z^n]C_t(z)} \sum _{k=1}^m \left(\sum _{j=0}^{m-k}{ e_{m,k} \binom{m-k}{j} [z^{n}]z^{j+k}C_t^{j+k+1} } \right) \end{align*} Using Mathematica, this quantity has been verified to match the moments of $$\negbin\left(2, \frac{t^{t-1}}{t^{t-1}+(t-1)^{t-2}}\right)$$ for $t\leq 10$ and $m\leq 20$. \section{Dyck paths and ternary paths with an even number of hills}\label{even-dyck} In this section, we provide a response and extension to the following question posed by L. Shapiro \cite{cheon} in a private communication: ``What is the asymptotic proportion of Dyck paths having an even number of hills?" Our approach relies on properties of the Fine numbers, though it is also possible to use the techniques of the last section to answer the question. Along the way we uncover some interesting combinatorial relationships between the Fine and Catalan numbers sequences and one of their many generalizations. \subsection{Even number of hills among Dyck paths}\label{evenhillsdyck} Recall that $F(z)=\sum_{n=0}^\infty{f_nz^n}$ is the generating function for the Fine numbers. Our first observation is that the number of Dyck paths of length $2n$ having exactly $k$ hills is given by the $(n,k)$-th entry of th Riordan array (\seqnum{A065600}) \begin{equation} (F(z), zF(z)) = \left(\begin{array}{ccccccc} 1&&&&&& \\ 0&1&&&&& \\ 1 & 0 &1&&&& \\ 2 & 2 & 0 & 1&&& \\ 6 & 4 & 3 & 0 & 1&& \\ 18 & 13 & 6 & 4 & 0 & 1&\\ 57 & 40 & 21 & 8 & 5 & 0 & 1\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{array}\right), \label{finetriangle} \end{equation} where $F(z)$ is the generating function for the Fine numbers. It has been shown that the proportion of Dyck paths having no hills approaches $4/9$. This result, which appears in \cite{deutsch1}, follows from something described there as the ``hill-killer" identity: \begin{equation} C(z)+1=(z+2)F(z) \end{equation} which implies that \begin{equation}c_n=f_{n-1}+2f_n\label{hillkillrecursion}\end{equation} for $n\geq 1$. Dividing both sides of (\ref{hillkillrecursion}) by $c_n$ and using the fact that $c_{n-1}/c_n\sim 1/4$, one can reveal that \begin{equation} f_n/c_n\sim 4/9.\label{fn/cn}\end{equation} To find the proportion of Dyck paths having exactly one hill, we can make use of the following useful identity: \begin{equation} (2z+z^2)F^2(z)-(1+2z)F(z)+1=0, \label{hillkiller2intro} \end{equation} a result proven combinatorially by Cheon et al.\ \cite{cheon}. If $a_n$ is the number of Dyck paths of length $2n$ having one hill then $zF^2(z)$ is the generating function for $a_n$ (\seqnum{A065601}). Identity (\ref{hillkiller2intro}) implies that \begin{equation} 2a_n+a_{n-1}=f_n+2f_{n-1} \label{hillkill2recursion} \end{equation} for $n\geq 1$. Using the fact that $f_n/c_n\sim 4/9$, $c_{n-1}/c_n\sim 1/4$ and (\ref{hillkill2recursion}), we find the proportion of Dyck paths having exactly one hill approaches $8/27$, that is, \begin{equation} a_n/c_n\sim 8/27.\label{an/cn}\end{equation} This can be further generalized by multiplying both sides of (\ref{hillkiller2intro}) by $z^{k-1}F^{k-1},$ as \begin{equation} z^{k+1}F^{k+1}+2z^kF^{k+1}-z^{k-1}F^{k}-2z^{k}F^k+z^{k-1}F^{k-1}=0 \label{bighillkiller} \end{equation} to obtain a more general ``hill-killer" recurrence. \begin{proposition} Let $f_{n,k}$ denote the number of Dyck paths of semilength $n$ having exactly $k$ hills. That is, $f_{n,k}=[z^n]z^kF^{k+1}$. Then \begin{equation} f_{n-1,k}+2f_{n,k}-f_{n,k-1}-2f_{n-1,k-1}+f_{n-1,k-2}=0 \label{dotdiag} \end{equation} \label{dotdiagprop} \end{proposition} \begin{proof} Follows directly from (\ref{bighillkiller}). \end{proof} We may now use the recurrence in Proposition \ref{dotdiagprop} to answer Shapiro's question. \begin{theorem} The proportion of Dyck paths having an even number of hills approaches $5/8$ as the length of the paths approaches infinity. \end{theorem} \begin{proof} Dividing both sides of equation (\ref{dotdiag}) by $c_n$ leads to the following: \begin{equation} \frac{f_{n-1,k}}{c_{n-1}}\cdot\frac{c_{n-1}}{c_n}+2\frac{f_{n,k}}{c_n}-\frac{f_{n,k-1}}{c_n}-2\frac{f_{n-1,k-1}}{c_{n-1}}\cdot\frac{c_{n-1}}{c_n}+\frac{f_{n-1,k-2}}{c_{n-1}}\cdot\frac{c_{n-1}}{c_n}=0 \label{dotdiagbyc_n} \end{equation} Let $\displaystyle L_k:=\lim_{n\to\infty}{\frac{f_{n,k}}{c_n}}$ be the asymptotic proportion of Dyck paths having $k$ hills. Using the fact that $\displaystyle\lim_{n\to\infty}{\frac{c_{n-1}}{c_n}}=\frac{1}{4},$ equation (\ref{dotdiagbyc_n}) implies \begin{eqnarray*} \frac{1}{4}L_k + 2L_k-L_{k-1}-2L_{k-1}\cdot \frac{1}{4}+L_{k-2}\cdot \frac{1}{4}&=&0 \end{eqnarray*} which simplifies to \begin{eqnarray} \frac{9}{4}L_k &= & \frac{3}{2}L_{k-1}-\frac{1}{4}L_{k-2} \label{recurrence1} \end{eqnarray} for $k\geq 2$. Note that $L_0=4/9$ and $L_1=8/27$, as we saw in equations (\ref{fn/cn}) and (\ref{an/cn}). Solving the linear recurrence in (\ref{recurrence1}) gives, \begin{equation*} L(z):=\sum_{k=0}^\infty{L_kz^k}=\frac{4}{9-6z+z^2}=\frac{4/9}{\left({1-z/3}\right)^2}, \end{equation*} the (asymptotic) probability distribution for the number of hills. Hence, $$[z^k]L(z)=(k+1)\cdot\frac{4}{9}\left(\frac{1}{3}\right)^k$$ which is the negative binomial distribution with index $2$ and parameter $2/3$. (Incidentally, this is the same as the asymptotic distribution for the number of returns among ternary paths, as we saw in Section \ref{returns}.) To obtain the asymptotic probability that a Dyck path has an {\em even} number of hills, take the sum of the even indexed coefficients of $L(z)$, which is $$\sum_{k=0}^\infty{[z^{2k}]L(z)}=\sum_{n=0}^\infty{(2k+1)\cdot\frac{4}{9}\left(\frac{1}{9}\right)^{k}}={\frac{5}{8}}$$ \end{proof} \subsection{Even number of hills among ternary paths}\label{ternaryfine} Here we extend our approach in Section \ref{evenhillsdyck} to answering Shapiro's question about Dyck paths and determine the asymptotic probability that a randomly chosen ternary path has an even number of hills. In this extension, we encounter and interpret the appropriate analogue of the Fine numbers for the ternary numbers. Recall from (\ref{gfternarynos}) that $C_3(z)=T(z)$ denotes the generating function for the ternary numbers $$t_n=\frac{1}{2n+1}\binom{3n}{n}$$ The Riordan array (\seqnum{A110616}) \begin{equation} (T(z),zT(z))= \left(\begin{array}{ccccccc} 1&&&&&& \\ 1&1&&&&& \\ 3 & 2 &1&&&& \\ 12 & 7 & 3 & 1&&& \\ 55 & 30 & 12 & 4 & 1&& \\ 273 & 143 & 55 & 18 & 5 & 1&\\ 1428 & 728 & 273 & 88 & 25 & 6 & 1\\ \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{array}\right), \label{T,zT} \end{equation} counts ternary paths ending at height $k\geq 0$. The $(n,k)$th entry is the number of ternary paths with length $3n+k$ and terminal height $k$. Let $t_{n,k}$ denote the $(n,k)$th entry of (\ref{T,zT}), so that $t_{n,0}=t_n$. Then $t_{n,k}=[z^n]z^kT^{k+1}=[z^{n-k}]T^{k+1}$, which as a consequence of (\ref{gfternarynos}) and (\ref{powersofC_t}) is \begin{equation} t_{n,k}=\frac{k+1}{2n-k+1}\binom{3n-2k}{n-k}. \label{t_n,k} \end{equation} This fact can be used to show that $\lim_{n\to\infty}{t_{n-1}/t_n}=4/27$. The generating function $T^2(z)$ for the nonzero terms in the second column of (\ref{T,zT}) corresponds to \seqnum{A006013} which counts \begin{itemize} \item elevated ternary paths of length $3(n+1)$, \item ground level points on all ternary paths of length $3n$, \item leaves at the root of all noncrossing trees with $n+2$ vertices, \item even trees with $2(n+1)$ edges where the degree of the root is two, and \item a third of the leaves at the root of all ternary trees with $3(n+1)$ edges. \end{itemize} It is not hard to show, using (\ref{t_n,k}), that the average number of ground level points on all ternary paths approaches 3, that is $\displaystyle \lim_{n\to\infty}{t_{n+1,1}/t_n}=3$. Similarly, since the number of leaves at the root for all noncrossing trees of order $n+1$ is given by $t_{n,1}=[z^n]zT^2(z)=[z^{n-1}]T^2(z)=\frac{1}{n}\binom{3n-2}{n-1},$ one can show that the average number of leaves at the root ${t_{n,1}/t_n}$ approaches $4/9$. Next we offer an analogue to the Fine number sequence for the ternary numbers. We will refer to a ternary path having no hills as a {\em ternary-Fine path}. Let $\F(z)$ denote the generating function for the number of ternary-Fine paths of length $3n$. The sequence corresponding to $\F(z)$ begins $1, 0, 2, 7, 34, 171,\dots$ (\seqnum{A023053}). \begin{theorem} If $T(z)$ is the generating function for the number of ternary paths of length $3n$ and $\F(z)$ is the generating function for the number of ternary paths of length $3n$ having no hills, then $\displaystyle T(z)=\frac{\F(z)}{1-z\F(z)}$ and equivalently, $\displaystyle \F(z)=\frac{T(z)}{1+zT(z)}$. \label{TtoF} \end{theorem} \begin{proof} Every ternary path can be decomposed according to its number of hills. A ternary path with $k$ hills would have the form $$(P_1UUD)(P_2UUD)\cdots (P_{k}UUD)P_{k+1}$$ where each $P_i$ is a (possibly empty) ternary path with no hills. The associated generating function is $z^k\F^{k+1}(z)$ and summing over all $k\geq 0$ provides the result. \end{proof} In addition to ternary-Fine paths of length $3n$, $\F(z)$ also counts \begin{itemize} \item paths from $(0,0)$ to $(n,0)$ which never go below the $x$-axis and use step set $\{U(1,1)\}\cup\{L_k(1,0):k=1,2,3\}\cup\{D_k(1,-1):k=1,2,3\}\cup\{D(1,-2)\}$ but $L_1,L_2,L_3,D_3$ are not allowed to touch the $x$-axis, \label{ternarymotzkin} \item noncrossing trees with $n+1$ vertices having no leaves at the root, \item $2$-plane trees with $n+1$ vertices, root labeled $2$ and no leaves at the root \end{itemize} A detailed justification of the first bullet above will be presented in Section \ref{genfinemotzkin}. \begin{figure} \begin{center} \setlength{\unitlength}{.6cm} \begin{picture}(8,2) \put(0,0){\vtx} \put(-0.25,0.25){$1$} \put(6,0){\vtx} \put(5.9,0.25){$k$} \put(4.5,-0.15){\small $N_1$} \put(6.5,-0.15){\small $N_2$} \put(0.5,-0.15){\small $N_3$} \qbezier(0, 0)(3,3)(6, 0) \put(3,1.75){$e$} \qbezier(0, 0)(1,.75)(2, 0) \qbezier(0, 0)(1,-.75)(2, 0) \qbezier(6, 0)(5,.75)(4, 0) \qbezier(6, 0)(5,-.75)(4, 0) \qbezier(6, 0)(7,.75)(8, 0) \qbezier(6, 0)(7,-.75)(8, 0) \end{picture} \end{center} \caption{A nonempty noncrossing tree $N$ with no leaf at its root must have the form above.} \label{zFT^2} \end{figure} \begin{remark} We may refer to the sequence associated with $\F(z)$ as the {\em ternary-Fine numbers}. It is worth noting that using the Lindstr{o}m-Gessel-Viennot nonintersecting path system argument for determinants \cite{gessel,lindstrom}, one may conclude that the Hankel transform of the ternary-Fine numbers is equal to the Hankel transform of the ternary numbers (\seqnum{A051255}). \end{remark} Next we discuss the limiting distribution for the number of hills among ternary paths. Before proceeding, we present a few generating function identities for $\F$ which prove useful in accomplishing this. \begin{theorem} Let $\F(z)$ be the generating function for the number of ternary paths of length $3n$ having no hills. Then $$z\F(z) T^2(z)=\F(z) +z\F(z) -1$$ \label{zFT^2thm} \end{theorem} \begin{proof} First, rewrite this equation as $$\F=1 + z\F(T^2-1).$$ We shall prove this last statement combinatorially in terms of noncrossing trees. $\F$ counts noncrossing trees having no leaves at the root. Observe that any noncrossing tree $N$ with no leaf at the root is either empty or it consists of the following components: (A) the ``longest" edge $e$ from the root (that is, the edge $e$ from $1$ to $k$, where $k$ is as large as possible); (B) subtrees $N_1$, $N_2$ (not both empty) attached to the left and right of $k$ respectively, and; (C) a (possibly empty) subtree $N_3$ with no leaves at its root attached to the root $1$. See Figure \ref{zFT^2}. Since, $z$ counts (A), $T^2-1$ counts (B) and $\F$ counts (C), it is clear that $1 + z\F(T^2-1)$ also counts the number of noncrossing trees having no leaf at the root. \end{proof} The two preceding theorems can be used to give the following recursive identity for the $\F(z)$. Note that Theorem \ref{Fpolycor} can be thought of as an analogue of the Fine number identity (\ref{hillkiller2intro}) referenced in \cite{cheon}. In Section \ref{genfinemotzkin}, we will consider the generalization of this identity for $t$-Dyck paths. \begin{theorem} Let $\F(z)$ be the generating function for the number of ternary paths of length $3n$ having no hills. Then \begin{equation} \F^3(z-z^2-z^3)+\F^2(2z+3z^2)-\F(1+3z)+1=0 \label{Fpolynomial} \end{equation} \label{Fpolycor} \end{theorem} \begin{proof} First, we establish the following preliminary result: \begin{equation} T^2=\F^2(1-z-z^2)+\F(2+3z)-2 \label{T^2} \end{equation} We begin with the observation from Theorem \ref{TtoF} that $$zT^2=\frac{z\F^2}{(1-z\F)^2}$$ which implies \begin{eqnarray*} z\F^2&=&zT^2(1-2z\F+z^2\F^2)\\ z\F^2&=&zT^2-2z^2T^2\F+z^3T^2\F^2)\\ zT^2&=&z\F^2+2z^2T^2F-z^3T^2\F^2. \end{eqnarray*} Now, using Theorem \ref{zFT^2thm}, we obtain \begin{eqnarray*} zT^2&=&z\F^2+2z^2T^2F-z^3T^2\F^2\\ zT^2&=&z\F^2+2z\F+2z^2\F-2z-z^2\F^2-z^3\F^2+z^2\F\\ T^2&=&\F^2(1-z-z^2)+\F(2+3z)-2. \end{eqnarray*} Multiplying both sides of equation (\ref{T^2}) by $zF$ and using Theorem \ref{zFT^2thm} provides the result. \end{proof} The number of ternary paths of length $3n$ having exactly $k$ hills is given by the $(n,k)$th entry of the Riordan matrix (\seqnum{A101371}) \begin{equation} (\F(z), z\F(z)) = \left(\begin{array}{ccccccc} 1&&&&&& \\ 0&1&&&&& \\ 2 & 0 &1&&&& \\ 7 & 4 & 0 & 1&&& \\ 34 & 14 & 6 & 0 & 1&& \\ 171 & 72 & 21 & 8 & 0 & 1&\\ 905 & 370 & 114 & 28 & 10 & 0 & 1\\ &&\cdots&&&& \end{array}\right). \label{ternaryfinetriangle} \end{equation} Notice that the row sums of (\ref{ternaryfinetriangle}) are the ternary numbers. Let $\f_{n,k}:=[z^n]z^k\F^{k+1}$ denote the $(n,k)$th entry of (\ref{ternaryfinetriangle}), so that $\f_{n,0}=\f_n$. Now Theorem \ref{Fpolycor} suggests a recursion for $\f_{n,k}$. By multiplying both sides of (\ref{Fpolynomial}) by $z^{k-1}F^{k-1}$, we have \begin{equation*} \F^{k+2}(z^k-z^{k+1}-z^{k+2})+\F^{k+1}(2z^k+3z^{k+1})-\F^k(z^{k-1}+3z^k)+z^{k-1}\F^{k-1}=0, \end{equation*} for all $k\geq 1, $ and by taking the $n$th coefficient of this last expression, we obtain the following recursion for the triangle in (\ref{ternaryfinetriangle}): \begin{equation} \f_{n+1,k+1}-\f_{n,k+1}-\f_{n-1,k+1}+2\f_{n,k}+3\f_{n-1,k}-\f_{n,k-1}-3\f_{n-1,k-1}+\f_{n-1,k-2} = 0 \label{F_n,k-recurrence} \end{equation} for all $n\geq 1$ and $k\geq 2$. We can now also answer Shapiro's question in the context of ternary paths. \begin{theorem} The proportion of ternary paths having an even number of hills approaches $125/169$ as the length of the paths approaches infinity. \end{theorem} \begin{proof} Let $\tL_k$ denote the asymptotic probability that a ternary path has $k$ hills. That is, let $$\tL_k=\lim_{n\to\infty}\frac{\f_{n,k}}{t_n}.$$ We will use equation (\ref{T^2}) to find a generating function for $\tL_k$. Divide both sides of equation (\ref{F_n,k-recurrence}) by $t_n$ and let $n$ tend to infinity. Notice that as $n\to\infty,$ \begin{equation*} \frac{\f_{n+1,k}}{t_n}= \frac{\f_{n+1,k}}{t_{n+1}}\cdot \frac{t_{n+1}}{t_n}\rightarrow \frac{27}{4}\tL_k \end{equation*} and \begin{equation*} \frac{\f_{n-1,k}}{t_n}= \frac{\f_{n-1,k}}{t_{n-1}}\cdot \frac{t_{n-1}}{t_n}\rightarrow \frac{4}{27}\tL_k. \end{equation*} With these two observations and using recursion (\ref{F_n,k-recurrence}), we have \begin{align} \left(\frac{27}{4}-1-\frac{4}{27}\right)\tL_{k+1}+\left(2+3\cdot\frac{4}{27}\right)\tL_k-\left(1+3\cdot\frac{4}{27}\right)\tL_{k-1}+\frac{4}{27}\tL_{k-2} &=&0\\ \Rightarrow \frac{605}{108}\tL_{k+1} +\frac{22}{9}\tL_k-\frac{13}{9}\tL_{k-1}+\frac{4}{27}\tL_{k-2}&=&0 \label{tL-recurrence} \end{align} Using this recurrence, along with initial conditions $\tL_0, \tL_1,$ and $\tL_2$, we can determine that the generating function for $\tL_k$ is \begin{equation} \tL(z)=\sum_{k=0}^\infty{\tL_kz^k}=\frac{324z+405}{605+264z-156z^2+16z^3}=\left(\frac{9}{11-2z}\right)^2=\left(\frac{9/11}{1-2z/11}\right)^2 \end{equation} (We refer the interested reader to Appendix \ref{appendix} for a verification of the initial conditions $\tL_0, \tL_1,$ and $\tL_2$.) Hence, the proportion of ternary paths having $k$ hills is $$[z^k]\tL(z)=(k+1)\cdot\frac{81}{121}\left(\frac{2}{11}\right)^k$$ which is the negative binomial distribution $\negbin(2, 9/11)$ with mean $4/9$ and variance $44/81$. Finally, the proportion of ternary paths having an even number of hills is given by $$\sum_{k=0}^\infty{[z^{2k}] \tL(z)}= \frac{81}{121}\sum_{k=0}^\infty{(2k+1) \cdot \left(\frac{4}{121}\right)^k } = {\frac{125}{169}}$$ \end{proof} \section{Generalized Fine and Motzkin analogues}\label{genfinemotzkin} In this section, we generalize the Fine analogue from the previous section and provide some interpretations. In particular, we give a generating function identity for which Theorem \ref{Fpolycor} is a special case. In connection with this generalized Fine analogue, we also introduce an analogue for the Motzkin numbers and discuss some of its interpretations. Recall that a $t$-Dyck path is a path from $(0,0)$ to $(tn,0)$ with step set $\{U(1,1)\}\cup\{D(1,-t+1)\}$ which never goes below the $x$-axis and that $C_t(z)$ is the generating function for the number of $t$-Dyck paths of length $tn$, that is, $$C_t(z)=\sum_{n=0}^\infty{\frac{1}{(t-1)n+1}\binom{tn}{n}z^n}.$$ Let's start with our Fine analogue. \begin{theorem} Let $F_t(z)$ be the generating function for the number of $t$-Dyck paths having no hills. Then $$\displaystyle C_t(z)=\frac{F_t(z)}{1-zF_t(z)}.$$ \label{catalanfineidentity} \end{theorem} \begin{proof} This follows from the fact that $t$-Dyck paths can be sorted according to their number of hills. A $t$-Dyck path with $k$ hills would have the form $$\mathcal{F}_0U^{t-1}D\mathcal{F}_1U^{t-1}D\mathcal{F}_2\cdots U^{t-1}D\mathcal{F}_k,$$ where each $\mathcal{F}_i$ is a $t$-Dyck path with no hills. Hence, the generating function for the number of $t$-Dyck paths with $k$ hills is $z^k(F_t(z))^{k+1}$ and summing from $k=0$ to infinity gives the result. \end{proof} Note that $F_1(z)=1$, $F_2(z)=F(z)$ is the generating function for the Fine numbers and $F_3(z)=\F(z)$ is the Fine analogue of Section \ref{ternaryfine}. In this paper, we have seen non-obvious generating function identities for $F_2(z)$ and $F_3(z)$ which we want to understand in terms of $F_t(z)$. Recalling the approach to equation (\ref{hillkiller2intro}) which was used in \cite{cheon}, we first want to consider a different path interpretation of $F_t(z)$. Consider the set of paths from $(0,0)$ to $(n,0)$ with step set $\{(1,1)\}\cup\{(1,-k+1):k=1,2,\dots t\}$ which never go below the $x$-axis. In the case when $t=2$, these are Motzkin paths. Hence, we will refer to these paths in general as $[t]$-Motzkin paths. There is a well-known correspondence between these $[t]$-Motzkin paths, plane $[t]$-trees and other combinatorial structures \cite{stanley2}. With an appropriate coloring, these objects become another manifestation of the generalized Catalan numbers. \begin{remark} The reader should be careful to distinguish the $[t]$-Motzkin paths described here from ``$t$-Motzkin paths" that have been described elsewhere in the literature. For instance, in \cite{cheon} the term ``2-Motzkin path" is used to describe a path with step set $$\{U(1,1), L_1(1,0), L_2(1,0),D(1,-1)\}.$$ However, here, the step set for $[t]$-Motzkin paths has cardinality $t+1$. If we let $M_t(z)$ denote the generating function for the number of $[t]$-Motzkin paths of length $n,$ then $M_1(z)=C_1(z)=1/(1-z)$, $M_2(z)=M(z)$ and $$M_3(z)=1+z+2z^2+5z^3+13z^4+36z^5+104z^6+309z^7+\cdots,$$ is \seqnum{A036765}. Based on a natural decomposition of $[t]$-Motzkin paths by initial step, one can easily see that $$M_t(z)=\sum_{k=0}^t{z^k(M_t(z))^k}.$$ \end{remark} \begin{definition} Let $t\geq 1$. A {\bf binomial $[t]$-Motzkin path} is a path from $(0,0)$ to $(n,0)$ with step set $$ \bigcup_{k=0}^t{\left\{S_{i}(1,-k+1):i=1,2,\dots,\binom{t}{k}\right\}}$$ \begin{eqnarray*} =\{S_{1}(1, 1)\}\cup\{S_{1}(1, 0),\dots, S_{\binom{t}{1}}(1, 0) \} \\ \cup\{S_{1}(1, -1),\dots, S_{\binom{t}{2}}(1, -1) \} \cup\dots \\ \dots \cup\{S_{1}(1, -k+1),\dots, S_{\binom{t}{k}}(1, -k+1) \}\cup\dots\\ \cup\{S_{1}(1, -t+3),\dots, S_{\binom{t}{t-2}}(1, -t+3) \} \cup \\ \{S_{1}(1, -t+2),\dots, S_{\binom{t}{t-1}}(1, -t+2) \} \cup \{S_{1}(1, -t+1)\} \end{eqnarray*} which never goes below the $x$-axis. That is to say, there are $2^t$ possible steps to choose from. Each step has the form $S_i(1,-k+1)$ where $k=0,1,\dots, t$. Each $S_{i}(1,-k+1)$ is distinguished with a color $i$ where $i$ is between $1$ and $\binom{t}{k}$. \end{definition} \begin{figure} \begin{center} \begin{tikzpicture} [scale=.7,auto=left] \tikzstyle{black} = [circle, minimum width=3pt, fill, inner sep=0pt] \node[black] (n11) at (0,9) {}; \node[black] (n12) at (1,9) {}; \node[black] (n13) at (2,9) {}; \node[black] (n14) at (3,9) {}; \foreach \from/\to in {n11/n12,n12/n13,n13/n14} \draw[black] (\from) -- (\to); \node at (0.5,9.25) {$3$}; \node at (1.5,9.25) {$3$}; \node at (2.5,9.25) {$3$}; \node[black] (n21) at (5,9) {}; \node[black] (n22) at (6,9) {}; \node[black] (n23) at (7,10) {}; \node[black] (n24) at (8,9) {}; \foreach \from/\to in {n21/n22,n22/n23,n23/n24} \draw[black] (\from) -- (\to); \node at (5.5,9.25) {$3$}; \node at (7.75,9.75) {$3$}; \node[black] (n31) at (0,7) {}; \node[black] (n32) at (1,8) {}; \node[black] (n33) at (2,8) {}; \node[black] (n34) at (3,7) {}; \foreach \from/\to in {n31/n32,n32/n33,n33/n34} \draw[black] (\from) -- (\to); \node at (1.5,8.25) {$3$}; \node at (2.75,7.75) {$3$}; \node[black] (n41) at (5,7) {}; \node[black] (n42) at (6,8) {}; \node[black] (n43) at (7,7) {}; \node[black] (n44) at (8,7) {}; \foreach \from/\to in {n41/n42,n42/n43,n43/n44} \draw[black] (\from) -- (\to); \node at (6.75,7.75) {$3$}; \node at (7.5,7.25) {$3$}; \node[black] (n51) at (9,7) {}; \node[black] (n52) at (10,8) {}; \node[black] (n53) at (11,9) {}; \node[black] (n54) at (12,7) {}; \foreach \from/\to in {n51/n52,n52/n53,n53/n54} \draw[black] (\from) -- (\to); \end{tikzpicture} \end{center} \caption{There are $27+9+9+9+1=55$ binomial $[3]$-Motzkin paths of length 3. Each up step of the form $(1,1)$ can be just one color; each level step of the form $(1,0)$ can be one of 3 colors; each down step of the form $(1,-1)$ can be one of 3 colors; each down step of the form $(1,-2)$ can be just one color.} \label{binmotzkinex} \end{figure} \begin{example} See Figure \ref{binmotzkinex} for a depiction of binomial $[3]$-Motzkin paths of length 3. There are 55 binomial $[3]$-Motzkin paths of length 3. Since each up step $U$ is one color, each level step $L$ is one of 3 colors, each down step $D_1$ of the form $(1,-1)$ is one of 3 colors and the down step $D_2$ of the form $(1,-2)$ can only be one color, we have 27 paths of the form $LLL$, 9 of the form $LUD_1$, 9 of the form $ULD_1$, 9 of the form $UD_1L$ and 1 of the form $UUD_2$. \end{example} In general, binomial $[t]$-Motzkin paths are counted by generalized Catalan numbers. \begin{theorem} The generating function for the number of binomial $[t]$-Motzkin paths of length $n$ is $(C_t(z))^t$. \end{theorem} \begin{proof} To see this, suppose $M_t^*(z)$ is the generating function for binomial $[t]$-Motzkin paths. Each binomial $[t]$-Motzkin path is either (1) empty, (2) of the form $L\mathcal{P}_1$ where $L$ is a level step and $\mathcal{P}_1$ is a colored $t$-Motzkin path, or (3) of the form $U \mathcal{P}_1U\mathcal{P}_2U\mathcal{P}_3\cdots U\mathcal{P}_{k-1}D_k\mathcal{P}_k$ where $k=2,\dots,t,$ $U$ is an up step, each $\mathcal{P}_i$ is a binomial $[t]$-Motzkin path and $D_k$ is a down step of the form $(1,-k+1)$. Since there are $\binom{t}{1}$ types of level step and $\binom{t}{k}$ types of down step of the form $(1,-k+1)$, we have \begin{eqnarray*} M_t^*(z)&=&1+\binom{t}{1}zM_t^*(z)+\binom{t}{2}z^2(M_t^*(z))^2+\binom{t}{3}z^3(M_t^*(z))^3+\cdots \ignore{+\binom{t}{t}z^{t}(M_t^*(z))^{t}}\\ &=&\sum_{k=0}^t{\binom{t}{k}z^k(M_t^*(z))^k}\\ &=&(1+zM_t^*(z))^t, \end{eqnarray*} which implies that \begin{equation}1+zM_t^*=(M_t^*)^{1/t}.\label{coloredmotzkin}\end{equation} Since $(C_t(z))^t$ satisfies (\ref{coloredmotzkin}) and $M_t^*(0)=1=C_t(0)$, it must be that $M_t^*(z)=(C_t(z))^t=(C_t(z)-1)/z$. \end{proof} There is of course a natural bijection $\phi$ between binomial $[t]$-Motzkin paths of length $n$ and $t$-Dyck paths of length $t(n+1)$. Suppose ${P}$ is a binomial $[t]$-Motzkin path. To create $\phi(P)$, first start with $U^{t-1}$. Then reading ${P}$ from left to right, whenever we encounter a step $S_{i}(1,-k+1)$ with color $i$, we adjoin a unique subpath $P_{k,i}$ of length $t$ consisting of $k$ down steps of the form $D(1,-k+1)$ and $t-k$ $U$'s. Since there are $\binom{t}{k}$ possibilities for the color $i$ and $\binom{t}{k}$ possible paths $P_{k,i}$, we can indeed assign each color $i$ with a unique path $P_{k,i}$. Notice that the adjoining of $P_{k,i}$ would add a net of $-t(k-1)$ to the height of the path. Complete $\phi(P)$ by adjoining the final step $D(1,-t+1)$. The resulting path $\phi(P)$ is a path of length $tn+t$ using $U(1,1)$'s and $D(1,-k+1)$'s, which never goes below the $x$-axis, i.e., a $t$-Dyck path. The inverse map $\phi^{-1}$ is achieved by reading a $t$-Dyck from left to right, $t$ consecutive steps at a time (ignoring the first $t-1$ $U's$ and the last $D$) and then reversing the step to subpath assignment. It is known that binomial $[2]$-Motzkin paths having no level steps on the $x$-axis are counted by the Fine numbers with generating function $F(z)=F_2(z)$. Given the bijection $\phi$ described above, it is clear that a $2$-Dyck path with a hill would correspond to binomial $[2]$-Motzkin paths with at least one level step on the $x$-axis. For $t\geq 3$, we want to give an interpretation of $F_t(z)$ in terms of binomial $[t]$-Motzkin paths which is consistent with the case when $t=2$. Considering the map $\phi$, one can imagine how a level step on the $x$-axis in a binomial $[t]$-Motzkin path could create a hill in a $t$-Dyck path, but clearly for $t\geq 3$, simply disallowing such level steps would not be sufficient to generate $F_t(z)$. \begin{theorem} $F_t(z)$ is the generating function for the number of binomial $[t]$-Motzkin paths of length $n$ with the following step restrictions: \begin{enumerate} \item no level steps allowed on the $x$-axis and \item only $\binom{t-1}{k-1}$ colors are allowed for down steps of the form $(1,-k+1)$ which end on the $x$-axis. \end{enumerate} \label{tfinepaths} \end{theorem} We may refer to the restricted binomial $[t]$-Motzkin paths described in Theorem \ref{tfinepaths} as {\bf $t$-Fine paths.} \begin{proof} Let $H_t(z)$ be the generating function for the number of $t$-Fine paths of length $n$. First, we will show that $H_t(z)$ satisfies: \begin{equation} H_t(z)=1+zH_t(z)[(C_t(z))^{t-1}-1] \end{equation} To see this, observe that every $t$-Fine path is either empty or has a return. If the $t$-Fine path has a return, then it has the form $$(U\mathcal{P}_1)(U\mathcal{P}_2)\cdots (U\mathcal{P}_{k-1})D_k\mathcal{F},$$ where each $\mathcal{P}_i$ is a binomial $[t]$-Motzkin path, $D_k$ is the down step of the form $(1,-k+1)$ incident with the first return and $\mathcal{F}$ is a $t$-Fine path. Since $D_k$ can be one of $\binom{t-1}{k-1}$ colors and $k=2, 3,\dots, \text{ or } t$, we have \begin{eqnarray*} H_t &=&1+zH_t\left[\sum_{k=2}^{t}{\binom{t-1}{k-1}(zC_t^t)^{k-1}}\right]\\ &=&1+zH_t\left[\sum_{k=1}^{t-1}{\binom{t-1}{k}(C_t-1)^k}\right]\\ &=&1+zH_t[((C_t-1)+1)^{t-1}-1]\\ &=&1+zH_t[(C_t)^{t-1}-1], \end{eqnarray*} which implies that $\displaystyle C_t^{t-1}=\frac{H_t-1+zH_t}{zH_t}$ or equivalently, $$\frac{C_t-1}{zC_t}=\frac{H_t+zH_t-1}{zH_t}.$$ And on the other hand, we have from Theorem \ref{catalanfineidentity} that $$\frac{C_t-1}{zC_t}=\frac{\frac{F_t}{1-zF_t}-1}{z\frac{F_t}{1-zF_t}}=\frac{F_t+zF_t-1}{zF_t}.$$ Hence, given $H_t(0)=1=F_t(0)$, it must be that $H_t(z)=F_t(z)$. \end{proof} Finally, we observe that as a direct consequence of Theorem \ref{catalanfineidentity} and the fact that $C_t=1+zC_t^t$, we have the following generating function identity for $F_t(z)$. \begin{theorem} \begin{equation*} 1+zF_t^t+\sum_{k=0}^{t-1}{\left[\binom{t-1}{k}+\binom{t}{k+1}z\right](-1)^{k+1}z^kF_t^{k+1}}=0 \end{equation*} \label{genfinepoly} \end{theorem} \begin{proof} Using Theorem \ref{catalanfineidentity}, we obtain \begin{eqnarray*} C_t(z) &=& 1+zC_t^t(z)\\ \implies F_t(z) &=& 1-zF_t(z)+zC_t^{t-1}(z)F_t(z)\\ \implies F_t(z) & =& \frac{(1-zF_t(z))^t}{(1-zF_t(z))^{t-1}}+\frac{z(F_t(z))^t}{(1-zF_t(z))^{t-1}}\\ \implies F_t(z)(1-zF_t(z))^{t-1} & =& (1-zF_t(z))^t+z(F_t(z))^t\\ \end{eqnarray*} and the result follows from the Binomial Theorem. \end{proof} \section{Conclusions and further work} Our study of returns and hills on $t$-Dyck paths has shown that, asymptotically speaking, the number of returns is easier to determine than the number of hills. We established that the asymptotic distribution for the number of returns among $t$-Dyck paths is negative binomial with parameters $(2,\frac{t-1}{t})$. Furthermore, in response to L. Shapiro's question, we have established that the probability that a randomly chosen Dyck path has an even number of hills approaches $\frac{5}{8}$ and the probability that a randomly chosen ternary path has an even number of hills approaches $\frac{125}{169}$. Hence, it is apparently more likely for a ternary path to have an even number of hills than for a Dyck path to have an even number of hills. In this case, we have used a recursive identity for the generalized Fine functions $F_2(z)$ and $F_3(z)$ to determine the exact probabilities needed to reach our conclusion. While such a recursive identity for $F_t(z)$ exists for all $t$ (Theorem \ref{genfinepoly}), the efficiency of its use decreases as $t$ increases. In Section \ref{hills}, we have provided strong evidence that the asymptotic distribution for the number of hills among $t$-Dyck paths is in fact negative binomial with parameters $\left(2, \frac{t^{t-1}}{t^{t-1}+(t-1)^{t-2}}\right),$ and it would be very desirable to make this evidence conclusive. \section{Acknowledgments} The authors wish to thank an anonymous referee for valuable suggestions which improved the quality of the paper. \begin{appendix} \section{Initial conditions for \texorpdfstring{${\tL}_n$}{Lg}} \label{appendix} Here are the computations to determine $\tL_0$, $\tL_1$, and $\tL_2$ as initial conditions for the recurrence in (\ref{tL-recurrence}). Equation (\ref{T^2}) implies that, for $n\geq 1$, \begin{equation} t_{n+1,1}=\f_{n+1,1}-\f_{n,1}-\f_{n-1,1}+2\f_{n,0}+3\f_{n-1,0} \label{T^2recurrence} \end{equation} \noindent Dividing both sides of (\ref{T^2recurrence}) by $t_{n+1}$, we obtain: \begin{align*} \frac{t_{n+1,1}}{t_{n+1}}&=\frac{\f_{n+1,1}}{t_{n+1}}-\frac{\f_{n,1}}{t_n}\cdot\frac{t_n}{t_{n+1}}-\frac{\f_{n-1,1}}{t_{n-1}}\cdot\frac{t_{n-1}}{t_n}\cdot\frac{t_n}{t_{n+1}}+2\frac{\f_{n,0}}{t_n}\cdot\frac{t_n}{t_{n+1}}+3\frac{\f_{n-1,0}}{t_{n-1}}\cdot\frac{t_{n-1}}{t_n}\cdot\frac{t_n}{t_{n+1}}\\ \Rightarrow \frac{4}{9} &= \tL_1-\tL_1\left(\frac{4}{27}\right)-\tL_1\left(\frac{4}{27}\right)^2+2\tL_0\left(\frac{4}{27}\right)+3\tL_0\left(\frac{4}{27}\right)^2 \\ \Rightarrow \frac{4}{9} & =\tL_1\left(1-\frac{4}{27}-\left(\frac{4}{27}\right)^2\right)+\tL_0\left(2\left(\frac{4}{27}\right)+3\left(\frac{4}{27}\right)^2\right)\\ \Rightarrow \frac{4}{9} &= \frac{605}{81}\tL_1+\frac{264}{81}\tL_0 \\ &\Rightarrow 324 = 605 \tL_1+264 \tL_0 \\ &\Rightarrow 2^2\cdot 3^4 = 5\cdot 11^2\tL_1+2^3\cdot 3\cdot 11\tL_0 \end{align*} \noindent Now, if we multiply equation (\ref{T^2}) by $zT^2$, we obtain \[ zT^4=z\F^2T^2(1-z-z^2)+z\F T^2(2+3z)-2zT^2 \] \noindent Using Theorem \ref{zFT^2thm}, we can simplify this to \begin{align*} zT^4+2zT^2&=(\F^2+z\F^2-\F)(1-z-z^2)+(\F+z\F-1)(2+3z)\\ \Rightarrow zT^4+2zT^2&=\F^2(1-2z^2-z^3)+\F(1+6z+4z^2)-(2+3z) \end{align*} \noindent and therefore, we have for $n\geq 2$, \begin{equation} t_{n+2,3}+2t_{n,1}=\f_{n+1,1}-2\f_{n-1,1}-\f_{n-2,1}+ \f_n +6\f_{n-1}+4\f_{n-2} \label{T^4recurrence} \end{equation} \noindent Dividing both sides of (\ref{T^4recurrence}) by $t_{n+1},$ we obtain \begin{align*} 2\left(\frac{4}{27}\right)+2\left(\frac{4}{9}\right)\left(\frac{4}{27}\right)&=\tL_1-2\tL_1\left(\frac{4}{27}\right)^2-\tL_1\left(\frac{4}{27}\right)^3 \\ &+\tL_0\left(\frac{4}{27}\right)+6\tL_0\left(\frac{4}{27}\right)^2 + 4\tL_0\left(\frac{4}{27}\right)^3 \\ \Rightarrow \frac{8\cdot 13}{3^5}&=\tL_1\left[1-2\left(\frac{4}{27}\right)^2-\left(\frac{4}{27}\right)^3\right]+\tL_0\left[\frac{4}{27}+6\left(\frac{4}{27}\right)^2+4\left(\frac{4}{27}\right)^3\right]\\ \Rightarrow 2^3\cdot 3^4\cdot 13& = 5\cdot 11^2 \cdot 31\cdot \tL_1 + 2^2\cdot 11 \cdot 131 \cdot \tL_0 \end{align*} \noindent (Note that (\ref{t_n,k}) can be used to conclude that $\displaystyle \lim_{n\to\infty}{t_{n+2,3}/t_{n+1}}=2$.) With two equations and two unknowns, we can determine $\tL_0$ and $\tL_1$. \begin{equation} \boxed{ \tL_0=\frac{2^3}{11^2} = \frac{81}{121} } \end{equation} \begin{equation} \boxed{ \tL_1=\frac{2^2\cdot 3^4}{11^3} = \frac{324}{1331} } \end{equation} \noindent Now, equation (\ref{Fpolynomial}) can be used to determine $\tL_2$. Equation (\ref{Fpolynomial}) implies that for $n\geq 1,$ \begin{equation} \f_n+3\f_{n-1}=\f_{n+1,2}-\f_{n,2}-\f_{n-1,2}+2\f_{n,1}+3\f_{n-1,1} \end{equation} \noindent Dividing both sides by $t_{n-1}$, we obtain \begin{eqnarray*} \tL_0\left(\frac{27}{4}\right)+3\tL_0&=&\tL_2\left(\frac{27}{4}\right)^2-\tL_2\left(\frac{27}{4}\right)-\tL_2+2\tL_1\left(\frac{27}{4}\right)+3\tL_1 \\ \frac{39}{4}\tL_0&=& \frac{605}{16}\tL_2+\frac{66}{4}\tL_1 \end{eqnarray*} \begin{equation} \Rightarrow \boxed{\tL_2= \frac{2^2\cdot 3^5}{11^4}=\frac{972}{14641}} \end{equation} \end{appendix} \begin{thebibliography}{AA} \bibitem{barcucci} E. Barcucci, E. Pergola, R. Pinzani, and S. Rinaldi, ECO method and hill-free generalized Motzkin paths, {\em S\'em. Lothar. Combin.} {\bf 46} (2001/2), Article B46b. Available at \url{https://www.emis.de/journals/SLC/wpapers/s46rinaldi.html}. \bibitem{cheon} G. Cheon, S. Lee, and L. Shapiro, The Fine numbers refined, {\em European J. Combin.} {\bf 31} (2010), 120--128. \bibitem{deutsch0} E. Deutsch, Dyck path enumeration, {\em Discrete Math.} {\bf 204} (1999), 167--202. \bibitem{deutsch1} E. Deutsch and L. Shapiro, A survey of the Fine numbers, {\em Discrete Math.} {\bf 241} (2001), 241--265. \bibitem{flajolet} P. Flajolet and R. Sedgewick, {\em Analytic Combinatorics}, Cambridge University Press, 2009. \bibitem{gessel} I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae, {\em Adv. in Math.} {\bf 58} (1985), 300--321. \bibitem{graham} R. Graham, D. Knuth, and O. Patashnik, {\em Concrete Mathematics}, Addison-Wesley, 1994. \bibitem{gu} N. Gu, H. Prodinger, and S. Wagner, Bijections for a class of labeled plane trees, {\em Europ. J. Combin.} {\bf 31} (2010), 720--732. \bibitem{lindstrom} B. Lindstr\"om, On vector representations of induced matroids, {\em Bull. London Math. Soc.} {\bf 5} (1973), 85--90. \bibitem{oeis} {\em The On-Line Encyclopedia of Integer Sequences}, published electronically at \url{http://oeis.org}, 2016. \bibitem{riordangroupreference1} L. Shapiro, S. Getu, W.-J. Woan, and L. Woodson, The Riordan group, {\em Discrete Math.} {\bf 34} (1991), 229--239. \bibitem{stanley2} R. Stanley, {\em Enumerative Combinatorics}, Vol.~2, Cambridge University Press, 1999. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A16, 11B83. \\ \noindent \emph{Keywords: } Catalan number, ternary number, Dyck path, Fine number, Motzkin number, hill, return, lattice path statistics. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000108}, \seqnum{A000957}, \seqnum{A001006}, \seqnum{A001764}, \seqnum{A006013}, \seqnum{A008292}, \seqnum{A023053}, \seqnum{A033184}, \seqnum{A036765}, \seqnum{A051255}, \seqnum{A065600}, \seqnum{A065601}, \seqnum{A101371}, \seqnum{A109971}, and \seqnum{A110616}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received February 5 2016; revised versions received May 19 2016; June 13 2016. Published in {\it Journal of Integer Sequences}, June 15 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}