\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb,amsmath} \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} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \usepackage{amssymb,latexsym,pstcol,pstricks} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf Statistics on Dyck Paths } \vskip 1cm \large Toufik Mansour\\ Department of Mathematics \\ University of Haifa \\ 31905 Haifa \\ Israel \\ \ \\ and \\ \ \\ Center for Combinatorics\\ LPMC \\ Nan'kai University \\ Tianjin 300071 \\ P. R. China \\ \href{mailto:toufik@math.haifa.ac.il}{\tt toufik@math.haifa.ac.il} \\ \end{center} \vskip .2 in \begin{abstract} In this paper we consider several statistics on the set of Dyck paths. Enumeration of Dyck paths according to length and various other parameters has been studied in several papers. However, the statistic ``number of $udu$'s" has been considered only recently. We generalize this statistic and derive an explicit formula for the number of Dyck paths of length $2n$ according to the statistic ``number of $uu\cdots udu$'s" (``number of $udud\cdots udu$'s"). As a consequence, we derive several known results, as well as many new results. \end{abstract} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}{Proposition}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{lemma}{Lemma}[section] %\documentclass[12pt,reqno]{article} %\usepackage{fullpage} %\usepackage{amsmath} %\numberwithin{equation}{section} %\newtheorem{theorem}{Theorem}[section] %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{definition}[theorem]{Definition} %\newtheorem{conjecture}[theorem]{Conjecture} %\newtheorem{remark}[theorem]{Remark} %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{fact}[theorem]{Fact} \newtheorem{example}[theorem]{Example} %\newtheorem{axiom}[theorem]{Axiom} %\newtheorem{property}[theorem]{Property} %\newtheorem{problem}[theorem]{Problem} %\newtheorem{notation}[theorem]{Notation} \newenvironment{proof}[1][Proof]{\paragraph*{#1}}{\hspace*{\fill}$\Box$\bigskip} %\begin{document} \pagenumbering{arabic} \def\sof{\hfill\rule{2mm}{2mm}} \def\ls{\leq} \def\gs{\geq} \def\nn{{\bold n}} \def\ttx{{\left(\frac1{2\sqrt{x}}\right)}} \def\DD{\mathcal{D}} \def\SS{\mathcal{S}} \def\MM{\mathcal{M}} %=========================================================================== \section{Introduction} A \emph{lattice path} of length $n$ is a sequence of points $P_1,P_2,\ldots,P_n$ with $n\geq1$ such that each point $P_i$ belongs to the plane integer lattice and consecutive points $P_i$ and $P_{i+1}$ are connected by a line segment. We will consider lattice paths in $\mathbb{Z}^2$ whose permitted step types are up-steps $u=(1,1)$, down-steps $d=(1,-1)$, and horizontal steps $h=(1,0)$. We will focus on paths that start from the origin and return to the $x$-axis, and that never pass below the $x$-axis. Let $\DD_n$ denote the set of such paths, {\em Dyck paths}, of length $2n$ when only up-steps and down-steps are allowed, and let $\MM_n$ denote the set of such paths, {\em Motzkin paths}, of length $n$ when all the three types are allowed. It is well known that $|\DD_n|=C_n=\frac{1}{n+1}\binom{2n}{n}$, the $n$-th Catalan number (see~\cite[A000108]{Sloane}), having ordinary generating function $C(x)=\frac{1-\sqrt{1-4x}}{2x}$ which satisfies the relation \begin{equation}\label{eqcatalan} xC^2(x)-C(x)-1=0, \end{equation} and $|\MM_n|=M_n$, the $n$-th Motzkin number (see~\cite[A001006]{Sloane}), having ordinary generating function $M(x)=\frac{1-x-\sqrt{1-2x-3x^2}}{2x^2}$, which satisfies the relation \begin{equation}\label{eqmotzkin} x^2M^2(x)+(x-1)M(x)+1=0. \end{equation} Let $D$ be any Dyck path and $p$ be any word on alphabet $\{u,d\}$. We say that the Dyck path $D$ occurs $p$ at {\em low level} if $D$ can be decomposed as $D=D'pR$ such that $D'$ is a Dyck path. Otherwise we say that the Dyck path $D$ occurs $p$ at {\em high level}. The enumeration of Dyck paths according to length and various other parameters has been studied by several authors \cite{D2}-\cite{MSV13}. However, the statistic ``number of $udu$'s" has been considered only recently \cite{MSV13,Sun}. The paper is organized as follows. In Section~2 we consider the statistic ``the number of $uu\cdots udu$'s" and the statistic ``the number of $udud\cdots du$'s" in the set of Dyck paths. In Section~3 we consider these statistics at low and high level in the set of Dyck paths. %=========================================================================== \section{Enumeration of Dyck paths according to number of $uu\cdots udu$'s or number of $udud\cdots udu$'s} In this section we enumerate the number of Dyck paths according to the length and either the number of $uu\cdots udu$'s or the number of $udud\cdots udu$'s. \subsection{Enumeration of Dyck paths according to number of $uu\cdots udu$'s} Let $\alpha_i(D)$ be the number of occurrences of $\underbrace{uu\cdots u}_{i}du$ in the Dyck path $D$, see Table~\ref{tab1}. \begin{table}[ht] \begin{tabular}{l|lllllll||l|lllllll}\hline $n\backslash\alpha_1$ & $0$ & $1$ & $2$ & $3$ & $4$& $5$ &$6$ & $n\backslash\alpha_2$ & $0$ & $1$ & $2$ & $3$ & $4$& $5$ &$6$ \\ \hline $1$ & $1$ & & & & & & & $1$ & $1$ & & & & & & \\ $2$ & $1$ & $1$ & & & & & & $2$ & $2$ & & & & & & \\ $3$ & $2$ & $2$ & $1$ & & & & & $3$ & $4$ & $1$ & & & & & \\ $4$ & $4$ & $6$ & $3$ & $1$ & & & & $4$ & $10$& $3$ & $1$ & & & & \\ $5$ & $9$ & $16$& $12$& $4$ & $1$& & & $5$ & $26$& $12$& $3$ & $1$& & &\\ $6$ & $21$& $45$& $40$& $20$& $5$& $1$ & & $6$ & $72$& $41$& $15$& $3$& $1$ & &\\ $7$ & $51$& $126$&$135$&$80$&$30$& $6$ & $1$ & $7$ & $206$&$143$&$58$ &$18$&$3$& $1$ & \end{tabular} \vspace{10pt} \caption{Number of Dyck paths of length $2n$ according to the statistics $\alpha_1$ and $\alpha_2$.}\label{tab1} \end{table} Define the ordinary generating function for the number of Dyck paths of length $2n$ according to the statistics $\alpha_1,\alpha_2,\ldots$ as $F(x;q_1,q_2,\ldots)=\sum_{n\geq0}\sum_{D\in\DD_n}x^n\prod_{j\geq1}q_j^{\alpha_j(D)}$. To study the above ordinary generating function we need the following notation $$A_k(x;q_1,q_2,\ldots)=\sum_{n\geq0}\sum_{D\in\DD_n}x^n\prod_{j\geq1}q_j^{\alpha^k_j(D)},$$ where $\alpha^k_j(D)=\alpha_j\left(\underbrace{uu\cdots u}_kD\underbrace{dd\cdots d}_k\right)$. These ordinary generating functions satisfy the following recurrence relations. \begin{proposition}\label{th11} For all $k\geq0$, $$\begin{array}{ll} A_k(x;q_1,q_2,\ldots)&=1+x(1-q_1q_2\cdots q_{k+1})-x(1-q_1q_2\cdots q_{k+1})A_0(x;q_1,q_2,\ldots)\\ &+xA_{k+1}(x;q_1,q_2,\ldots)A_0(x;q_1,q_2,\ldots).\end{array}$$ \end{proposition} \begin{proof} An equation for the generating function $A_k(x;q_1,q_2,\ldots)$ is obtained from the ``first return decomposition" of a Dyck paths $D$: $D=uPdQ$, where $P,Q$ are Dyck paths. Thus, the four possibilities of $P$ and $Q$ either being empty or nonempty Dyck paths (see Figure~\ref{fig1}) give contribution \begin{figure}[ht] \begin{center} \begin{pspicture}(1.5,1) \psline[linewidth=.5pt]{->}(1,0)\psline[linewidth=.5pt]{->}(0,.5) \psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](.25,.25)(.5,0) \end{pspicture} \begin{pspicture}(2.5,1) \psline[linewidth=.5pt]{->}(2,0)\psline[linewidth=.5pt]{->}(0,1) \psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](1.25,.25)(1.5,0) \psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1.25,.25)(.25,.25)(.5,.5)(.75,.45)(1,.5)(1.25,.25) \rput(.8,.7){\tiny$P\neq\emptyset$} \end{pspicture} \begin{pspicture}(2.5,1) \psline[linewidth=.5pt]{->}(2,0)\psline[linewidth=.5pt]{->}(0,1) \psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](.25,.25)(.5,0) \psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1.5,0)(.5,0)(.75,.25)(1,.2)(1.25,.25)(1.5,0) \rput(1,.45){\tiny$Q\neq\emptyset$} \end{pspicture} \begin{pspicture}(3,1) \psline[linewidth=.5pt]{->}(3,0)\psline[linewidth=.5pt]{->}(0,1) \psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](1.25,.25)(1.5,0) \psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1.25,.25)(.25,.25)(.5,.5)(.75,.45)(1,.5)(1.25,.25) \psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](2.5,0)(1.5,0)(1.75,.25)(2,.2)(2.25,.25)(2.5,0) \rput(.8,.7){\tiny$P\neq\emptyset$}\rput(2.2,.45){\tiny$Q\neq\emptyset$} \end{pspicture} \caption{First return decomposition of a Dyck path with nonempty Dyck paths.}\label{fig1} \end{center} \end{figure} $x$, $x(A_{k+1}(x;q_1,q_2,\ldots)-1)$, $xq_1q_2\cdots q_{k+1}(A_0(x;q_1,_2,\ldots)-1),$ and $x(A_{k+1}(x;q_1,q_2,\ldots)-1)(A_0(x;q_1,q_2,\ldots)-1)$, respectively. Hence, we have the following recurrence relation $$\begin{array}{ll}A_k(x;q_1,q_2,\ldots)&=1+x(1-q_1q_2\cdots q_{k+1})-x(1-q_1q_2\cdots q_{k+1})A_0(x;q_1,q_2,\ldots)\\ &+xA_{k+1}(x;q_1,q_2,\ldots)A_0(x;q_1,q_2,\ldots),\end{array}$$ for all $k\geq0$, as required. \end{proof} \begin{theorem}\label{th13} The generating function $F(x;q_1,q_2,\ldots)$ satisfies the following equation $$F(x;q_1,q_2,\ldots)=\sum_{m\geq0}x^mF^m(x;q_1,q_2,\ldots)(1+x(1-F(x;q_1,q_2,\ldots))(1-q_1q_2\ldots q_{m+1})).$$ \end{theorem} \begin{proof} We simply use the fact $A_0(x;q_1,q_2,\ldots)=F(x;q_1,q_2,\ldots)$ and apply (see Proposition~\ref{th11}) the recurrence relation $$\begin{array}{ll} A_k(x;q_1,q_2,\ldots)&=1+x(1-q_1q_2\cdots q_{k+1})(1-A_0(x;q_1,q_2,\ldots))\\ &\qquad\qquad\qquad+xA_{k+1}(x;q_1,q_2,\ldots)A_0(x;q_1,q_2,\ldots).\end{array}$$ an infinite number of times and in each step we perform some rather tedious algebraic manipulations. \end{proof} \begin{example} Define $q_1=q$, $q_2=q^{-1}$, and $q_i=1$ for all $i\geq3$. Then Theorem~\ref{th13} gives that the ordinary generating function $f(x;q)=F(x;q,q^{-1},1,1,\ldots)$ satisfies $$f(x;q)=\frac{1}{1-xf(x;q)}+x(1-f(x;q))(1-q).$$ Solving the above equation we get that the ordinary generating function $$f(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\alpha_1(D)-\alpha_2(D)}$$ is given by $$\frac{1+x(1+x)(1-q)-\sqrt{(x(1+x)(1-q)+1)^2-4x(1+x(1-q))^2}}{2x(1+x(1-q))}.$$ In particular, the number of Dyck paths $D$ of length $2n$ such that $\alpha_1(D)=\alpha_2(D)$ is given by (see \cite[A078481]{Sloane}) $$\frac{1+x+x^2-\sqrt{(1+x+x^2)^2-4x(1+x)^2}}{2x(1+x)}.$$ \end{example} \begin{example} Define $q_{2i-1}=q$ and $q_{2i}=q^{-1}$ for all $i\geq1$. Then Theorem~\ref{th13} gives $$F(x;q,1/q,q,1/q,\ldots)=1+x+xq(F(x;q,1/q,q,1/q,\ldots)-1)+x^2F^3(x;q,1/q,q,\ldots).$$ Then the Lagrange inversion formula (see~\cite{wilf}) gives that $$\sum_{n\geq1}\sum_{D\in\DD_n}x^nq^{\alpha_1(D)-\alpha_2(D)+\alpha_3(D)-\cdots}= \sum_{n\geq1}\sum_{j=0}^n\sum_{i=0}^j\binom{n}{j}\binom{i}{j}\binom{3i}{n-1+i-j}q^{j-i}\frac{x^{n+i}}{n}.$$ In particular, the number of Dyck paths $D$ of length $2n$ with $\sum\limits_{i\geq0}\alpha_{2i+1}(D)=\sum\limits_{i\geq0}\alpha_{2i}(D)$ is given by $$\sum_{j=0}^{n-1}\frac{1}{n-j}\binom{n-j}{j}\binom{3j}{n-1-j}.$$ \end{example} \begin{example}\label{exaaa} Define $q_i=q$ for all $i\geq1$. Then Theorem~\ref{th13} gives that $$S(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\alpha_1(D)+\alpha_2(D)+\cdots}=\sum_{m\geq0}x^mS^m(x;q)(1+x(1-S(x;q))(1-q^{m+1})),$$ which is equivalent to $S(x;q)=1+\frac{x}{1-xS(x;q)}-\frac{xq(1-S(x;q))}{1-xqS(x;q)}$. Differentiating the above equation with respect to $q$ and substituting $q=1$ with using the fact that $S(x;1)=C(x)$, the generating function for the Catalan numbers, gives that $$\sum_{n\geq0}\sum_{D\in\DD_n}(\alpha_1(D)+\alpha_2(D)+\cdots)x^n= \frac{x^2C^4(x)}{1-xC^2(x)}=\sum_{n\geq2}\binom{2n-1}{n-2}x^2.$$ In other words, the statistic $\sum_{D\in\DD_n}\alpha_1(D)+\alpha_2(D)+\cdots$ equals $\binom{2n-1}{n-2}$, for all $n\geq2$ (see \cite[A002054]{Sloane}). \end{example} Denote the ordinary generating function $F(x;q_1,q_2,\ldots)$ with $q_k=q$ and $q_i=1$ for all $i\neq k$ by $F_k(x;q)$. Fix $k\geq1$, $q_k=q$ and $q_i=1$ for all $i\neq k$. From the definitions it is easy to see that $F_k(x;q)=F_{k-1}(x;q)$. Thus, Proposition~\ref{th11} gives that $$F_{k-1}(x;q)=1+x(1-q)-x(1-q)F_{0}(x;q)+xF_{k-1}(x;q)F_0(x;q),$$ and $$F_{j+1}(x;q)=\frac{F_j(x;q)-1}{xF_j(x;q)},$$ for all $j=0,1,\ldots,k-2$. To give an explicit formula for $F_k(x;q)$ we need the following lemma. \begin{lemma}\label{lem11} For all $j=0,1,\ldots,k-1$, $$F_j(x;q)=\frac{\sqrt{x}U_j\ttx F_0(x;q)-U_{j-1}\ttx}{\sqrt{x}\left[\sqrt{x}U_{j-1}\ttx F_0(x;q)-U_{j-2}\ttx\right]},$$ where $U_j(t)$ is the $j$-th Chebyshev polynomial of the second kind. \end{lemma} \begin{proof} We proceed by induction on $j$. The result is true for $j=0$. For $j\geq0$ we have that $F_{j+1}(x;q)=\frac{F_{j}(x;q)-1}{xF_{j}(x;q)}$. Thus, by the induction hypothesis for $j$ we obtain that the ordinary generating function $F_{j+1}(x;q)$ equals $$\frac{\sqrt{x}U_j\ttx F_0(x;q)-U_{j-1}\ttx-\sqrt{x}\left[\sqrt{x}U_{j-1}\ttx F_0(x;q)-U_{j-2}\ttx\right]}{x\left[\sqrt{x}U_j\ttx F_0(x;q)-U_{j-1}\ttx\right]},$$ which is $$\frac{\sqrt{x}\left[\frac{1}{\sqrt{x}}U_j\ttx-U_{j-1}\ttx \right]F_0(x;q)-\left[\frac{1}{\sqrt{x}}U_{j-1}\ttx-U_{j-2}\ttx\right]}{\sqrt{x}\left[\sqrt{x}U_j\ttx F_0(x;q)-U_{j-1}\ttx\right]}.$$ Using the recurrence relation $U_m(t)=2tU_{m-1}(t)-U_{m-2}(t)$ twice we get $$\frac{\sqrt{x}U_{j+1}\ttx F_0(x;q)-U_{j}\ttx}{\sqrt{x}\left[\sqrt{x}U_j\ttx F_0(x;q)-U_{j-1}\ttx\right]},$$ as claimed. \end{proof} Now we are ready to give an explicit formula for the ordinary generating function $F_k(x;q)$. \begin{theorem}\label{th12} Let $$\begin{array}{l} \alpha(x;q)=x^2(1-q)U_{k-2}\ttx-x\sqrt{x}U_{k-1}\ttx,\\ \beta(x;q)=x\sqrt{x}(1-q)\left[U_{k-3}\ttx+\sqrt{x}U_{k-2}\ttx\right]-\sqrt{x}U_{k-1}\ttx,\\ \gamma(x;q)=\sqrt{x}(1+x(1-q))U_{k-3}\ttx-U_{k-2}\ttx. \end{array}$$ Then the ordinary generating function $F_k(x;q)$ is given by $$\frac{\gamma(x;q)}{\beta(x;q)} C\left(\frac{\alpha(x;q)\gamma(x;q)}{\beta^2(x;q)}\right),$$ where $U_j(t)$ is the $j$-th Chebyshev polynomial of the second kind and $C(x)$ is the ordinary generating function for the Catalan numbers. \end{theorem} \begin{proof} The generating function $F_0(x;q)$ satisfies the following equation $$F_{k-1}(x;q)=1+x(1-q)-x(1-q)F_{0}(x;q)+xF_{k-1}(x;q)F_0(x;q).$$ Using Lemma~\ref{lem11} for $j=k-1$ we get $$F_{k-1}(x;q)=\frac{\sqrt{x}U_{k-1}\ttx F_0(x;q)-U_{k-2}\ttx}{\sqrt{x}\left[\sqrt{x}U_{k-2}\ttx F_0(x;q)-U_{k-3}\ttx\right]}.$$ Substituting the expression for $F_{k-1}(x;q)$ in the above equation and using the recurrence relation $U_m(t)=2tU_{m-1}(t)-U_{m-2}(t)$ we obtain $$\alpha(x;q)F_0^2(x;q)-\beta(x;q)F_0(x;q)+\gamma(x;q)=0.$$ Hence, by solving the above equation we get the desired result. \end{proof} For example, Theorem~\ref{th12} for $k=1$ gives $F_1(x;q)=C\left(\frac{x}{1+x(1-q)}\right)$ (see~\cite[Equations~2.2 and 2.3]{Sun}). In particular, $F_1(x;0)=C(x/(1+x))$. This result can be generalized by using Theorem~\ref{th12} with $q=0$. \begin{corollary} The ordinary generating function for the number of Dyck paths of length $2n$ that avoid $\underbrace{uu\cdots u}_{k}du$ is given by $$\frac{U_{k}\ttx+\sqrt{x}U_{k-1}\ttx}{(1+x)U_{k}\ttx} C\left(\frac{xU_{k}\ttx+x\sqrt{x}U_{k-1}\ttx}{(1+x)^2U_{k}\ttx}\right),$$ where $U_j(t)$ is the $j$-th Chebyshev polynomial of the second kind and $C(x)$ is the ordinary generating function for the Catalan numbers. \end{corollary} For instance, the ordinary generating function for the number of Dyck paths of length $2n$ that avoid $uudu$ is given by $\frac{1}{1-x^2} C\left(\frac{x}{(1-x)(1+x)^2}\right)$ (see~\cite[A105633]{Sloane}). %======================== \subsection{Enumeration of Dyck paths according to number of $ud\cdots udu$'s} Let $\beta_i(D)$ be the number of occurrences of $\underbrace{udud\cdots ud}_{i}u$ in the Dyck path $D$, see Table~\ref{tab2}. Clearly, $\beta_1(D)=\alpha_1(D)$. \begin{table}[ht] \begin{center} \begin{tabular}{l|lllllll}\hline $n\backslash\beta_2$ & $0$ & $1$ & $2$ & $3$ & $4$& $5$ &$6$ \\ \hline $1$ & $1$ & & & & & &\\ $2$ & $2$ & & & & & &\\ $3$ & $4$ & $1$ & & & & &\\ $4$ & $11$& $2$ & $1$ & & & &\\ $5$ & $31$& $8$ & $2$& $1$ & & &\\ $6$ & $92$& $28$& $9$ & $2$ & $1$ & &\\ $7$ & $283$&$99$&$34$ &$10$ &$2$ & $1$&\\ \end{tabular} \vspace{10pt} \caption{Number of Dyck paths of length $2n$ according the statistic $\beta_2$.}\label{tab2} \end{center} \end{table} Define the ordinary generating function for the number of Dyck paths of length $2n$ according to the statistics $\beta_1,\beta_2,\ldots$ as $$G(x;q_1,q_2,\ldots)=\sum_{n\geq0}\sum_{D\in\DD_n}x^n\prod_{j\geq1}q_j^{\beta_j(D)}.$$ To study the above ordinary generating function we need the following notation $$B_k(x;q_1,q_2,\ldots)=\sum_{n\geq0}\sum_{D\in\DD_n}x^n\prod_{j\geq1}q_j^{\beta^k_j(D)},$$ where $\beta^k_j(D)=\beta_j\left(\underbrace{ud\cdots ud}_k D\right)$. These ordinary generating functions satisfy the following recurrence relations. \begin{proposition}\label{th21} For all $k\geq0$, $$\begin{array}{l} B_k(x;q_1,q_2,\ldots)=\prod\limits_{i=1}^{k}q_i^{k-i}+x\prod\limits_{i=1}^{k+1}q_i^{k+1-i} (B_0(x;q_1,q_2,\ldots)-1)B_0(x;q_1,q_2,\ldots)\\ \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+xB_{k+1}(x;q_1,q_2,\ldots).\end{array}$$ \end{proposition} \begin{proof} An equation for the generating function $B_k(x;q_1,q_2,\ldots)$ is obtained from the ``first return decomposition" of a Dyck paths $D$: $D=uPdQ$, where $P$ and $Q$ are Dyck paths. Then each Dyck path $D$ that starts with $\underbrace{udud\ldots ud}_k$ can be decomposed as either $D=\underbrace{udud\ldots ud}_k$, $D=\underbrace{udud\ldots ud}_kuPdQ$ with $P$ a nonempty Dyck path, or $D=\underbrace{udud\ldots ud}_{k+1}Q$ (see Figure~\ref{fig2} for $k=2$). \begin{figure}[ht] \begin{center} \begin{pspicture}(2,1) \psline[linewidth=.5pt]{->}(1.5,0)\psline[linewidth=.5pt]{->}(0,.5) \psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](.25,.25)(.5,0) \psline[linewidth=1pt](0.5,0)(.75,.25)\psline[linewidth=1pt](.75,.25)(1,0) \end{pspicture} \begin{pspicture}(4.5,1) \psline[linewidth=.5pt]{->}(4,0)\psline[linewidth=.5pt]{->}(0,1) \psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](.25,.25)(.5,0) \psline[linewidth=1pt](0.5,0)(.75,.25)\psline[linewidth=1pt](.75,.25)(1,0) \psline[linewidth=1pt](1,0)(1.25,.25)\psline[linewidth=1pt](2.25,.25)(2.5,0) \psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](2.25,.25)(1.25,.25)(1.5,.5)(1.75,.45)(2,.5)(2.25,.25) \psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](3.5,0)(2.5,0)(2.75,.25)(3,.2)(3.25,.25)(3.5,0) \rput(1.8,.7){\tiny$P\neq\emptyset$}\rput(3,.45){\tiny$Q$} \end{pspicture} \begin{pspicture}(4.5,1) \psline[linewidth=.5pt]{->}(4,0)\psline[linewidth=.5pt]{->}(0,1) \psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](.25,.25)(.5,0) \psline[linewidth=1pt](0.5,0)(.75,.25)\psline[linewidth=1pt](.75,.25)(1,0) \psline[linewidth=1pt](1,0)(1.25,.25)\psline[linewidth=1pt](1.25,.25)(1.5,0) \psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](2.5,0)(1.5,0)(1.75,.25)(2,.2)(2.25,.25)(2.5,0) \rput(2,.45){\tiny$Q$} \end{pspicture} \caption{First return decomposition of a Dyck path according the statistic $ududu$.}\label{fig2} \end{center} \end{figure} Thus, the ordinary generating function $B_k(x;q_1,q_2,\ldots)$ is given by $$\begin{array}{l} \prod\limits_{i=1}^{k}q_i^{k-i}+x\prod\limits_{i=1}^{k+1}q_i^{k+1-i} (B_0(x;q_1,q_2,\ldots)-1)B_0(x;q_1,q_2,\ldots)+xB_{k+1}(x;q_1,q_2,\ldots),\end{array}$$ for all $k\geq0$, as required. \end{proof} \begin{theorem}\label{th22} The generating function $G(x;q_1,q_2,\ldots)$ is given by $$G(x;q_1,q_2,\ldots)=C\left(\frac{x\sum_{m\geq0}x^m\prod_{i=1}^{m+1}q_i^{m+1-i}}{1+x\sum_{m\geq0}x^m\prod_{i=1}^{m+1}q_i^{m+1-i}}\right),$$ where $C(x)$ is the generating function for the Catalan numbers. \end{theorem} \begin{proof} We simply use the fact that $B_0(x;q_1,q_2,\ldots)=G(x;q_1,q_2,\ldots)$ and apply the recurrence relation $$\begin{array}{ll} B_k(x;q_1,q_2,\ldots)&=\prod\limits_{i=1}^{k}q_i^{k-i}+x\prod\limits_{i=1}^{k+1}q_i^{k+1-i} (B_0(x;q_1,q_2,\ldots)-1)B_0(x;q_1,q_2,\ldots)\\ &+xB_{k+1}(x;q_1,q_2,\ldots)\end{array}$$ an infinite number of times and in each step we perform some rather tedious algebraic manipulations. \end{proof} \begin{example} Let $q_{2i-1}=q$ and $q_{2i}=q^{-1}$ for all $i\geq1$. Then Theorem~\ref{th22} gives that $$\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\beta_1(D)-\beta_2(D)+\cdots}= C\left(\frac{x(1+xq)}{1+x}\right)$$ which is equivalent to $$\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\beta_1(D)-\beta_2(D)+\cdots}= 1+\sum_{n\geq1}x^n\sum_{i=0}^{n+1}\sum_{j=0}^{i+1}C_i\binom{i+1}{j}\binom{n-1-j}{i}q^j.$$ In particular, the ordinary generating function for the number of Dyck paths $D$ of length $2n$ with \begin{equation}\label{sbb} \sum_{i\geq1}\beta_{2i-1}(D)=\sum_{i\geq1}\beta_{2i}(D) \end{equation} is given by $C(x/(1+x))=M(x)$, that is, the number of Dyck paths $D$ of length $2n$ with (\ref{sbb}) is given by $M_n$, the $n$-th Mozkin number. \end{example} \begin{example} Let $q_i=q$ for all $i\geq1$. Then, similar to Example~\ref{exaaa}, we obtain from Theorem~\ref{th22} that $$\sum_{D\in\DD_n}(\beta_1(D)+\beta_2(D)+\cdots)=\sum_{j=0}^{n-2}\binom{2j+2}{j},$$ for all $n\geq2$. \end{example} Denote the ordinary generating function $G(x;q_1,q_2,\ldots)$ with $q_k=q$ and $q_i=1$ for all $i\neq k$ by $G_k(x;q)$. For example, if $q_1=q$ and $q_i=1$, $i=2,3,\ldots$, then Theorem~\ref{th22} gives $G_1(x;q)=C\left(\frac{x}{1+x(1-q)}\right)$ (see~\cite[Equations~2.2 and 2.3]{Sun}). In general, if $q_k=q$ and $q_i=1$ for all $i \neq k$, then Theorem~\ref{th12} gives an explicit formula for the ordinary generating function $G_k(x;q)$. \begin{corollary}\label{th23} The ordinary generating function for the Dyck paths of length $2n$ according to the statistic $\beta_k$ is given by $$G_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\beta_k}= C\left(\frac{x(1-xq-x^k(1-q))}{1-xq-x^{k+1}(1-q)}\right),$$ where $C(x)$ is the generating function for the Catalan numbers. \end{corollary} For instance, Corollary~\ref{th23} for $k=2$ and $q=0$ gives that the ordinary generating function for the number of Dyck paths of length $2n$ that avoid $UDUDU$ is given by $$C\left(\frac{x(1-x^2)}{1-x^3}\right)=1+\sum_{n\geq1}x^n\left(\sum_{i=1}^n\sum_{j=0}^{(n-m)/2} (-1)^{\frac{n-m+j}{3}}\binom{m}{j}\binom{\frac{n+2m-2j}{3}-1}{m-1}C_m\right).$$ \section{Enumeration of Dyck paths according to number of $uu\ldots udu$'s or number of $udud\ldots udu$'s at low and high levels} %We say that a $\underbrace{uu\ldots u}_kdu$ ($\underbrace{udud\ldots %ud}_ku$) is at low (resp. high) level if its peak is at level $k$ %exactly (resp. greater than level $k$). In this section we consider the following statistics on Dyck paths: number of low (high) level $uu\ldots udu$'s or number of low (high) level $udud\ldots udu$'s (for the case $k=1$, see \cite[Section 3]{Sun}). \subsection{Enumeration of Dyck paths according to number of $uu\ldots udu$'s at low and high levels} Let $\gamma_k$ (resp. $\gamma'_k$) be the number of occurrences of $\underbrace{uu\ldots u}_kdu$ at low (resp. high) level. Denote the ordinary generating function for the number of Dyck paths of length $2n$ according to the statistics $\gamma_k$ (resp. $\gamma'_k$) by $$L_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\gamma_k(D)}\quad \left(\mbox{resp.}\,\, H_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\gamma'_k(D)}\right).$$ \begin{theorem}\label{th31} Let $k\geq2$. Then the number of Dyck paths of length $2n$ with $\gamma_k=m$ is given by $$\sum_{j\geq0}(-1)^j\frac{(m+j)(k+1)+1}{2n+1-(m+j)(k+1)}\binom{m+j}{j}\binom{2n+1-(m+j)(k+1)}{n+1}.$$ \end{theorem} \begin{proof} Consider any Dyck path $D=uPdQ$, where $P$ and $Q$ are Dyck paths. So $D$ contains $a_k:=\underbrace{uu\ldots u}_kdu$ if either $P$ starts with $a_{k-1}$ or $Q$ contains $a_{k}$ (see Figure~\ref{fig3}). \begin{figure}[ht] \begin{center} \begin{pspicture}(3,1) \psline[linewidth=.5pt]{->}(3,0)\psline[linewidth=.5pt]{->}(0,1) \psline[linewidth=1pt](0,0)(.25,.25)\psline[linewidth=1pt](1.25,.25)(1.5,0) \psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](1.25,.25)(.25,.25)(.5,.5)(.75,.45)(1,.5)(1.25,.25) \psline[linewidth=.5pt,fillstyle=solid,fillcolor=black](2.5,0)(1.5,0)(1.75,.25)(2,.2)(2.25,.25)(2.5,0) \rput(.8,.7){\tiny$P$}\rput(2,.45){\tiny$Q$} \end{pspicture} \caption{First return decomposition of a Dyck path.}\label{fig3} \end{center} \end{figure} Thus, $L_k(x;q)=1+xt_1(x;q)L_k(x;q)$, where $t_j(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\gamma_k\left(\underbrace{uu\ldots u}\nolimits_jD\underbrace{dd\ldots d}\nolimits_j\right)}$ for all $j=1,2,\ldots k-1$. Again, using the first return decomposition of a Dyck path we obtain that the ordinary generating function $t_j(x;q)$ equals $1+xt_{j+1}(x;q)C(x)$, where $C(x)$ is the ordinary generating function for the Catalan numbers and $j=1,2,\ldots,k-2$. In addition, $t_{k-1}(x;q)=1+x+xC(x)(C(x)-1)+xq(C(x)-1)$. Therefore, it is easy to check that $$t_1(x;q)=(xC(x))^{k-2}t_{k-1}(x;q)+\sum_{j=0}^{k-3}(xC(x))^j.$$ This implies that the ordinary generating function $L_k(x;q)$ is given by $$L_k(x;q)=\frac{1}{1-x\left(\frac{1-(xC(x))^{k-2}}{1-xC(x)}+(xC(x))^{k-2}t_1(x;q))\right)}.$$ By using the identity $C(x)=\frac{1}{1-xC(x)}$ (see (\ref{eqcatalan})) we arrive at $$L_k(x;q)=\frac{C(x)}{1+(1-q)(xC(x))^{k+1}}=\sum_{m\geq0}\frac{x^{m(k+1)}C^{m(k+1)+1}(x)} {(1+(xC(x))^{k+1})^{m+1}},$$ which is equivalent to $$L_k(x;q)=\sum_{m\geq0}\sum_{j\geq0}(-1)^j\binom{m+j}{j}x^{(m+j)(k+1)}C^{(m+j)(k+1)+1}(x).$$ On other hand, by applying the Lagrange inversion formula in \cite{wilf}, we get that $$C^k(x)=\sum_{n\geq 0}\frac{k}{2n+k}\binom{2n+k}{n}x^n.$$ Hence, the $x^nq^m$ coefficient in the ordinary generating function $L_k(x;q)$ is given by $$\sum_{j\geq0}(-1)^j\frac{(m+j)(k+1)+1}{2n+1-(m+j)(k+1)}\binom{m+j}{j}\binom{2n+1-(m+j)(k+1)}{n+1},$$ as required. \end{proof} For example, Theorem~\ref{th31} for $k=2$ (for the case $k=1$ see~\cite[Theorem~3.1]{Sun}) gives that the number of Dyck paths of length $2n$ having $\gamma_2=m$ is given by $$\sum_{j\geq0}(-1)^j\frac{3(m+j)+1}{2n+1-3(m+j)}\binom{m+j}{j}\binom{2n+1-3(m+j)}{n+1}.$$ \begin{theorem}\label{th32} The ordinary generating function for the number of Dyck paths of length $2n$ according to the statistic $\gamma'_k$ is given by $$H_k(x;q)=\frac{1}{1-x\dfrac{1-x^k(1-q)F_k^{k-1}(x;q)(F_k(x;q)-1)}{1-xF_k(x;q)}},$$ where the explicit formula for the ordinary generating function $F_k(x;q)$ is given by Theorem~\ref{th12}. \end{theorem} \begin{proof} Again (see Theorem~\ref{th31}), by using the first return decomposition of a Dyck path $D$ ($D=uPdQ$ where $P$ and $Q$ are Dyck paths, see Figure~\ref{fig3}), we obtain that the ordinary generating function $H_k(x;q)$ satisfies $H_k(x;q)=1+xt_1(x;q)H_k(x;q)$, where $t_j(x;q)$ satisfies the recurrence relation $t_j(x;q)=1+xt_{j+1}(x;q)F_k(x;q)$, for $j=1,2,\ldots k$, and $t_{k}(x;q)=1+x+x(t_k(x;q)-1)F_k(x;q)+xq(F_k(x;q)-1)$. Solving the above system of equations we get the desired result. \end{proof} Theorems \ref{th31} and \ref{th32} give the following result. For $\gamma'_1=0$, we obtain that the number of Dyck paths of length $2n$ is given by the $n$-th Motzkin number (see \cite[Equation~3.6]{Sun}). For $\gamma'_2=0$, we obtain that the ordinary generating function for the number of Dyck paths of length $2n$ is given by $$\frac{2x^3+x^2-5x+3-(2x+1)\sqrt{x^4-2x^3-5x^2-2x+1}}{2(x^5+x^4+4x^3+5x^2-4x+1)}.$$ \subsection{Enumeration of Dyck paths according to number of $ud\ldots udu$'s at low and high levels} Let $\delta_k$ (resp. $\delta'_k$) be the number of occurrences of $\underbrace{udud\ldots ud}_ku$ at low (resp. high) level. Denote the ordinary generating function for the number of Dyck paths of length $2n$ according to the statistics $\delta_k$ (resp. $\delta'_k$) by $$L'_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\delta_k(D)}\quad \left(\mbox{resp.}\,\, H'_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\delta'_k(D)}\right).$$ Using the same techniques as in the previous subsection we obtain the following results. \begin{theorem}\label{th41} Let $k\geq1$. Then the ordinary generating function for the number of Dyck paths of length $2n$ according to the statistic $\delta_k$ is given by $$L'_k(x;q)=\frac{1-x^{k+1}-xq(1-x^k)}{1-x^{k+1}-x(1-x^k)C(x)-xq(1-x^k-x(1-x^{k-1})C(x))}.$$ Moreover, the ordinary generating function for the number of Dyck paths of length $2n$ with $\delta_k=m$ is $$\frac{x^{m+k}(1-x)^2C(x)(1-x^k-x(1-x^{k-1})C(x))^{m-1}}{(1-x^{k+1}-x(1-x^k)C(x))^{m+1}}$$ when $m\geq1$, and $\frac{1-x^{k+1}}{1-x^{k+1}-x(1-x^k)C(x)}$ when $m=0$. \end{theorem} For example, the number of Dyck paths of length $2n$ having $\delta_1=0$ is given by $\frac{1+x}{1+x-xC(x)}$ (see~\cite[Page~5]{Sun}), and having $\delta_2=0$ is given by $\frac{1+x+x^2}{1+x+x^2-x(1+x)C(x)}$. To enumerate the number of Dyck paths of length $2n$ according to the statistic $\delta'_k$ we use the first return decomposition of a Dyck path and Corollary~\ref{th23}. Thus we obtain the following result. \begin{theorem}\label{th42} Let $k\geq1$. Then the ordinary generating function for the number of Dyck paths of length $2n$ according to the statistic $\delta'_k$ is given by $$H'_k(x;q)=\frac{1}{1-xG_k(x;q)},$$ where $$G_k(x;q)=\sum_{n\geq0}\sum_{D\in\DD_n}x^nq^{\beta_k}= C\left(\frac{x(1-xq-x^k(1-q))}{1-xq-x^{k+1}(1-q)}\right).$$ \end{theorem} For example, the ordinary generating function for the number of Dyck paths of length $2n$ having $\delta'_1=0$ is given by $M(x)$ (see~\cite[Equation~3.6]{Sun}). %=========================================================================== \begin{thebibliography}{2} \bibitem{D2} E.~Deutsch, Dyck path enumeration, {\em Discr. Math.} {\bf 204} (1999), 167--202. \bibitem{K9} G. Kreweras, Joint distribution of three descriptive parameters of bridges, {\em Combinatoire \'Enum\'erative}, {\em Proc. (Montr\'eal, Que., 1985/Qu\'ebec, Que., 1985), Lec. Notes in Math.} {\bf 1234} (1986), 177--191. \bibitem{KM10} G. Kreweras and P. Moszkowski, A new enumerative property of the Narayana numbers, {\em J. Statist. Plann. and Infer.} {\bf 14} (1986), 63--67. \bibitem{KP11} G. Kreweras and Y. Poupard, Subdivision des nombres de Narayana suivant deux param\'etres suppl\'ementaires, {\em Europ. J. Combin.} {\bf 7} (1986), 141--149. \bibitem{M} T. Mansour, Counting peaks at height $k$ in a Dyck path, {\em Journal of Integer Sequences} {\bf 5} (2002), Article 02.1.1. \bibitem{MRSV12} D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, {\em Canad. J. Math.} {\bf 49:2} (1997), 301--320. \bibitem{MSV13} D. Merlini, R. Sprugnoli, and M. C. Verri, Some statistics on Dyck paths, {\em J. Statist. Plann. and Infer.} {\bf 101} (2002), 211--227. \bibitem{Sloane} N. J. A.~Sloane and S.~Plouffe, The Encyclopedia of Integer Sequences, Academic Press, New York (1995). \bibitem{Sun} Y. Sun, The statistic ``number of $udu$'s" in Dyck paths, {\em Discr. Math.} {\bf 287} (2004), 177--186. \bibitem{wilf} H. Wilf, {\it Generatingfunctionology}, Academic Press, New York, 1990. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: 05A05, 05A15, 42C05.\\ \noindent {\it Keywords}: Chebyshev polynomials, Dyck paths, Generating functions. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000108}, \seqnum{A001006}, \seqnum{A002054}, \seqnum{A078481}, and \seqnum{A105633}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 2 2005; revised version received January 16 2006. Published in {\it Journal of Integer Sequences}, January 17 2006. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}