\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} \newcommand{\pat}{2--13~} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \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 Lattice Path Enumeration of Permutations \\ \vskip .1in with $k$ Occurrences of the Pattern \pat } \vskip 1cm \large Robert Parviainen\\ ARC Centre of Excellence for Mathematics \\ and Statistics of Complex Systems \\ The University of Melbourne\\ 139 Barry Street\\ 3010 Victoria\\ Australia \\ \href{mailto:robertp@ms.unimelb.edu.au}{\tt robertp@ms.unimelb.edu.au} \end{center} \vskip .2 in \begin{abstract} We count the number of permutations with $k$ occurrences of the pattern \pat in permutations by lattice path enumeration. We give closed forms for $k\leq 8$, extending results of Claesson and Mansour. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{proposition}{Proposition} \newtheorem{corollary}{Corollary} \newtheorem{lemma}{Lemma} %\documentclass[oneside,a4paper,12pt,reqno]{article} %\usepackage{array,latexsym,amsfonts,amsmath,amsthm,fullpage} %\usepackage[pdftex]{graphicx} %\usepackage[usenames]{color} %\definecolor{webgreen}{rgb}{0,.5,0} %\definecolor{webbrown}{rgb}{.6,0,0} %\usepackage[colorlinks=true, % linkcolor=webgreen, % filecolor=webbrown, % citecolor=webgreen]{hyperref} %\newtheorem{theorem}{Theorem} %\newtheorem{lemma}[theorem]{Lemma} \newtheorem{prop}[theorem]{Proposition} %\newtheorem{cor}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} %\newtheorem{ex}[theorem]{Example} %\newcommand{\seqnum}[1]{\href{http://www.research.att.com/~njas/sequences/#1}{#1}} %\setlength{\textwidth}{6.5in} %\setlength{\oddsidemargin}{.1in} %\setlength{\evensidemargin}{.1in} %\setlength{\topmargin}{-.5in} %\setlength{\textheight}{8.9in} \section{Introduction} Let $\mathcal{S}_{n}$ denote the set of permutations of $\{1,2,\dots, n\}$. A \emph{pattern} in a permutation $\pi\in \mathcal{S}_{n}$ is a permutation $\sigma\in\mathcal{S}_{k}$ and an occurrence of $\sigma$ as a subword of $\pi$; there should exist $i_{1}<\dots < i_{k}$ such that $\pi(i_{1})\cdots\pi({i_{k}})$ is order equivalent to $\sigma$. (So $\pi(i_{1})$ is the $\sigma (1)$:th smallest of the subword, and so on.) For example, an occurrence of the pattern 3--2--1 in $\pi\in \mathcal{S}_{n}$ means that there exists $1\leq i\pi({j})>\pi({k})$. We further consider \emph{restricted} patterns, introduced by Babson and Steingr{\'\i}msson \cite{BS2000}. The restriction is that two specified adjacent elements in the pattern \emph{must be adjacent} in the permutation as well. The position of the restriction in the pattern is indicated by \emph{an absence} of a dash (--). Thus, an occurrence of the pattern 3--21 in $\pi\in \mathcal{S}_{n}$ means that there exists $1\leq i\pi({j})>\pi({j+1})$. Here we are interested in patterns of the type 2--13. We remark that it is shown by Claesson \cite{Clas2001} that the occurrences of \pat are equidistributed with the occurrences of the pattern 2--31, as well as with 13--2 and with 31--2. \begin{definition} Let $\phi_{k}(n)$ denote the number of permutations of length $n$ with exactly $k$ occurrences of the pattern 2--13. \end{definition} Claesson \cite{Clas2001} showed that $\phi_{0}(n)$ is given by the the $(n+1)$th Catalan number, $\frac{1}{n+1}\binom{2n}{n}$ (\seqnum{A000108}\footnote{Six-digit numbers prefixed by `A' indicate the corresponding entry in The On-Line Encyclopedia of Integer Sequences \cite{OEIS}.}). It was further shown that \begin{align} \phi_{1}(n)&=\binom{2n}{n-3}\label{eq:comb}\quad\mbox{(\seqnum{A002696})},\\ \phi_{2}(n)&=\frac{n}{2}\binom{2n}{n-4}\quad\mbox{(\seqnum{A094218})},\\ \phi_{3}(n)&=\frac{(n+1)(n+2)}{6}\binom{2n}{n-5}\quad\mbox{(\seqnum{A094219}}). \end{align} The authors commented that \emph{``$\ldots$ [the above result] obviously is in need of a combinatorial proof,''} referring in particular to Equation \ref{eq:comb}. In this paper we give such a combinatorial proof of all the above results, as well as formulae for $\phi_{4}(n),\ldots, \phi_{8}(n)$. We show how to count occurrences of \pat in permutations via lattice paths; bi-coloured Motzkin paths to be precise. \begin{definition} A \emph{Motzkin path} of length $n$ is a sequence of vertices $p = (v_0,v_1,\dots,v_n)$, with $v_i \in \mathbb{N}^2$ (where $\mathbb{N} = \{0,1,\dots\}$), with steps $v_{i+1}-v_i \in \{ (1,1), (1,-1), (1,0)\}$ and $v_0 = (0,0)$ and $v_n=(n,0)$. A \emph{bicoloured Motzkin path} is a Motzkin path in which each east, $(1,0)$, step is labelled by one of two colours. We say that the path is \emph{$q$-weighted} if the weight of steps ending at height $h$ is given by $[h]_{q}:=\sum_{k=0}^{h-1}q^{k}$. \end{definition} We will use $N$ ($S$) to denote a north, $(1,1)$, step (resp., south, $(1,-1)$, step), and $E$ and $F$ to denote the two different coloured east steps. %%% %%% %%% \subsection{Main Theorem} \begin{theorem}\label{th:1} The number of permutations of length $m+1$ with exactly $n$ occurrences of the pattern \pat is given by the coefficient of $q^{n}t^{m}$ in the generating function for $q$-weighted bi-coloured Motzkin paths. \end{theorem} \begin{remark} It follows from a result of Brak, et al., \cite{BCEPR2006}, that the number of permutations of length $m+1$ with exactly $n$ occurrences of the pattern \pat is given by the coefficient of $q^{n}$ in the normalisation $Z_{m}$ for the stationary distribution of the $\alpha=\beta=\eta=1$, $\gamma=\delta=0$ partially asymmetric exclusion process --- a Markov process widely studied in both mathematics and physics. \end{remark} We first give an almost trivial proof, based on generating functions, which are known in continued fraction form for both problems. In the next section we give a more interesting, bijective proof. \begin{proof} Claesson and Mansour \cite{CM2002} give the generating function $P(q;t)$ for the distribution of occurrences of the pattern \pat in permutations as a Stieltjes continued fraction: \[P(q;t)=\cfrac{1}{1-\cfrac{[1]_{q}t}{1-\cfrac{[1]_{q}t}{1-\cfrac{[2]_{q}t}{1-\cfrac{[2]_{q}t}{\ddots}}}}}. \] The generating function $M(q;t)$ for $q$-weighted bi-coloured Motzkin paths is well known (\cite{Flaj1980}, Theorem 1) to be given by the Jacobi continued fraction \[M(q;t)=\cfrac{1}{1-2[1]_{q}t-\cfrac{[1]_{q}[2]_{q}t^{2}}{1-2[2]_{q}t-\cfrac{[2]_{q}[3]_{q}t^{2}}{1-2[3]_{q}t-\cfrac{[3]_{q}[4]_{q}t^{2}}{\ddots}}}}. \] Applying the contraction formula from Stieltjes to Jacobi continued fractions, we find that indeed $P(q;t)=1+t M(q;t)$. \end{proof} %%% %%% %%% \section{Bijective proof} We will define three mappings: two bijections $\mathcal{B}$ and $\mathcal{T}$, and a projection $\mathcal{P}$. They will have the property that the composition $\mathcal{T}\circ\mathcal{P}\circ\mathcal{B}$ is a surjection from the set of permutations weighted by occurrences of the pattern 2--13, to the set of $q$-weighted bi-coloured Motzkin paths. Theorem \ref{th:1} will follow. \begin{definition} A bi-coloured \emph{vertex-weighted} Motzkin path is a bi-coloured Motzkin path in which vertex $k$, at height $h$, is given a weight from the set $\{1,q,\dots, q^{h}\}$ if step $k$ is $E$ or $N$, and from the set $\{1,q,\dots, q^{h-1}\}$ otherwise. Let $\mathcal{M}^{\ast}_{n}$ denote the set of bi-coloured {vertex-weighted} Motzkin paths of length $n$. \end{definition} We now define a bijection (of Foata and Zeilberger \cite{FZ1990}) $\mathcal{B}$ from $\mathcal{S}_{n}$ to $\mathcal{M}^{\ast}_{n}$. Let step $i$ in $p=\mathcal{B}(\pi)$ be \begin{align*} E& \mbox{ if } {\pi}(i)\geq i \geq {\pi^{-1}}(i),\\ F& \mbox{ if } {\pi}(i)< i <{\pi^{-1}}(i),\\ N& \mbox{ if } {\pi}(i)>i<{\pi^{-1}}(i),\\ S& \mbox{ if } {\pi}(i){\pi^{-1}}(i). \end{align*} Let vertex $n+1$ have weight 1, and vertex $k$, $1\leq k \leq n$, weight $q^{m(k)}$, where $m(k)$ is the number of occurrences of the pattern \pat in $\pi$ in which $k$ takes the role of 2. \begin{theorem}[\cite{FZ1990}] The mapping $\mathcal{B}$ is a weight preserving bijection between permutations and bi-coloured vertex-weighted Motzkin paths, such that the weight of $p=\mathcal{B}(\pi)$ equals the number of occurrences of \pat in $\pi$. \end{theorem} Next we define a projection $\mathcal{P}$ from bi-coloured vertex-weighted Motzkin paths to a slightly different set of vertex-weighted Motzkin paths, $\mathcal{M}^\prime$. \begin{definition} For $p\in\mathcal{M}$, let $p^{\prime}=\mathcal{P} (p)$ have the same steps. If step $k$ is $E$ or $N$, let vertex $k$, at height $h$, have weight $1+\dots+q^{h}$, and weight $1+\dots+q^{h-1}$ otherwise. \end{definition} The final step is to define a bijection $\mathcal{T}$ from $\mathcal{M}_{n+1}^{\prime}$ to $\mathcal{M}_{n}$. \begin{definition} For $p$ in $\mathcal{M}_{n+1}^{\prime}$ and for $k\in [n]$, if steps $k$ and $k+1$ is $x$ and $y$, let step $k$ in $\mathcal{T}(p)$ be given by\\ \begin{center} \begin{tabular}{c||c|c|c|c}$x\backslash y$ & $E$ & $F$ & $N$ & $S$ \\\hline\hline $E$ & $E$ & $S$ & $E$ & $S$ \\\hline $F$ & $N$ & $F$ & $N$ & $F$ \\\hline $N$ & $N$ & $F$ & $N$ & $F$ \\\hline $S$ & $E$ & $S$ & $E$ & $S$\end{tabular} \end{center} and have the same weight as vertex $k+1$ in $p$. \end{definition} \begin{theorem} The mapping $\mathcal{T}$ is a weight preserving bijection from $\mathcal{M}_{n+1}^{\prime}$ to $\mathcal{M}_{n}$. \end{theorem} \begin{proof} We will describe the inverse mapping. Append an $E$ step at both the start and the end of a walk $r\in\mathcal{M}_{n}$ to give a walk $r^{\prime}$ of length $n+2$. If steps $k$ and $k+1$ in $r^{\prime}$ are $x$ and $y$, respectively, step $k$ of $\mathcal{T}^{-1}(r)$ is given by \begin{center} \begin{tabular}{c||c|c|c|c}$x\backslash y$ & $E$ & $F$ & $N$ & $S$ \\\hline\hline $E$ & $E$ & $N$ & $N$ & $E$ \\\hline $F$ & $S$ & $F$ & $F$ & $S$ \\\hline $N$ & $E$ & $N$ & $N$ & $E$ \\\hline $S$ & $S$ & $F$ & $F$ & $S$\end{tabular} \end{center} Further, vertex $k$ in $s=\mathcal{T}^{-1}(r)$ has the same weight as step $k$ in $r^{\prime}$. That $\mathcal{T}^{-1}$ indeed is the inverse of $\mathcal{T}$ follows easily from the definition of $\mathcal{T}$. \end{proof} %%% %%% %%% \section{Application} Let $C(x)$ be the Catalan function, $C(x)=\frac{1-\sqrt{1-4x}}{2x}$. As is well known, \begin{equation*} g_{1}(x_{1};t)=\frac{C(x_{1} t)-1}{x_{1} t}=C^{2}(x_{1} t) \end{equation*} is the generating function for bi-coloured Motzkin paths in which each step has weight $x_{1}$. More generally, let $g_{k}(t)=g_{k}(x_{1}, x_{2}, \dots, x_{k};t)$ be the generating function for bi-coloured weighted Motzkin walks in which steps ending at height $h\leq k$ have weight $x_{k-h+1}$, and steps ending at height $h\geq k$ have weight $x_{1}$. \begin{lemma} \begin{equation*} g_{k}(t)=\frac{1}{1-2x_{k}t-x_{k-1}x_{k}t^{2}g_{k-1}(t)}. \end{equation*} \end{lemma} \begin{proof} Considering the first return to height 0 (where a step $E$ or $F$ is considered a return), we find $g_{k}(t)=1+(x_{k}t+x_{k}t+x_{k-1}t g_{k-1}(t)x_{k}t )g_{k}(t)$. \end{proof} The function $g_{k}([q]_{k},[q]_{k-1},\dots,[q]_{0};t)$ obviously agrees with the full generating function for $q-$coloured Motzkin paths for powers of $q$ less than $k$, and consequently we get the following proposition. \begin{prop} For $n< k$ the number of permutations of length $m$ with exactly $n$ occurrences of the pattern \pat is given by \begin{equation*} [q^{n}t^{m}] t g_{k}([q]_{k},[q]_{k-1},\dots,[q]_{0};t). \end{equation*} \end{prop} The following lemma is useful for extracting coefficients from the generating functions. \begin{lemma}\label{lemma:coef} Let $S(t)=\sqrt{1-4t}$. For $l\leq m$ we have \begin{equation*} [t^{n}] \frac{C^{m}(t)}{(2-C(t))^{l}}=[t^{n}]\frac{C^{m-l}(t)}{S^{l}(t)}=\frac{1}{2^{m-l}}\sum_{k=0}^{m-l}\binom{m-l}{k}(-1)^{k}[t^{n+m-l}]S^{k-l}. \end{equation*} \end{lemma} \begin{proof} The first equality holds since $S(t)C(t)=2-C(t)$; the second since $C(t)=(1-S(t))/2t$. \end{proof} Note that finding $[t^{n}]S^{k}$ is but an application of the binomial theorem. Let $\Phi_{k}(t)$ be the generating function for the sequence $\phi_{k}(m)$. We have $g_{1}(1;t)=C^{2}(t)$. Thus, the number of permutations of length $m$ with 0 occurrences of \pat is given by the $m$:th Catalan number. Next, we have \begin{equation*} g_{2}(1+q,1;t)=\frac{1}{1-t-tC((1+q)t)}, \mbox{ and} \end{equation*} \begin{equation*} \frac{\partial}{\partial q} g_{2}(1+q,1;t)=\frac{t^{2} C^{\prime} ((1+q)t)}{(1-t-t C^{2}((1+q)t)}, \end{equation*} where $C^{\prime} (x)=\frac{\partial}{\partial x} C(x)$. Setting $q=0$, and applying the transformation rules $t C^{2}(t)=C(t)-1$ and $C^{\prime}(t)=C^{3}(t)/(2-C(t))$, we find that \begin{prop}[\cite{CM2002}] \begin{equation*} \Phi_{1}(t)=t^{3}C^{7}(t)\frac{1}{2-C(t)}. \end{equation*} Applying Lemma \ref{lemma:coef} we get \begin{equation*} \phi_{1}(m)= \binom{2m}{m-3}\quad\mbox{\rm(\seqnum{A002696})}. \end{equation*} \end{prop} Similarly we derive expressions for $\Phi_{k}$ and $\phi_{k}$ for $k\leq 8$. The calculations can be summarised as follows. \begin{enumerate} \item Find $g_{k+1}$. \item Differentiate to get $\frac{\partial}{\partial q^{k}} g_{k+1}|_{q=0}$. \item Apply the transformation rules $t=(C-1)C^{-2}$, $C^{\prime}=C^{3}(2-C)^{-1}$, $C^{\prime\prime}=2C^5(3 - C)(2 - C)^{-3}, \ldots, C^{(k)}=\cdots$ to get a an expression of the form $t^{a}C^{b}P(C)(2-C)^{-c}$ where $a, b$ and $c$ are positive integers and $P$ is a polynomial. \item Apply Lemma \ref{lemma:coef} and the binomial theorem to extract coefficients. \item\label{step:bin} Use standard binomial coefficient identities to simplify. \end{enumerate} We note that all steps may, with some programming, be fully automated in a package such as Mathematica (used here). The bottleneck in this procedure is the differentiation (step 2), which in the straightforward implementation is quite memory consuming. This is also the main reason for us to restrict to $k\leq 8$ in this work --- step 2 required almost 1GB of RAM. \begin{prop}[\cite{CM2002}] \begin{equation*} \Phi_{2}(t)=\frac{\partial^{2}}{\partial^{2} q} g_{3}([q]_{3},[q]_{2},[q]_{1};t)|_{q=0}=t^{4}C^{9}(t)\frac{-1+5C(t)-2C^{2}(t)}{(2-C(t))^{3}}, \end{equation*} \begin{equation*} \phi_{2}(m)= \frac{m}{2} \binom{2m}{m-4}\quad\mbox{\rm(\seqnum{A094218})}. \end{equation*} \end{prop} \begin{prop}[\cite{CM2002}] \begin{equation*} \Phi_{3}(t)=\frac{\partial^{3}}{\partial^{3} q} g_{4}(t)|_{q=0}=t^{5}C^{11}(t)\frac{2 +6C(t)+5C(t)^2 - 8 C(t)^3 +2 C(t)^4}{(2-C(t))^{5}} \end{equation*} \begin{equation*} \phi_{3}(m)=\frac{(m+1)(m+2)}{6}\binom{2m}{m-5}\quad\mbox{\rm(\seqnum{A094219})}. \end{equation*} \end{prop} \begin{prop} \begin{equation*} \Phi_{4}(t)=\frac{\partial^{4}}{\partial^{4} q} g_{5}(t)|_{q=0}= t^5 C^{11} \frac{5-118 C+259 C^2-240 C^3+142 C^{4}-62 C^5+17 C^6-2 C^7}{(2-C)^{7}}, \end{equation*} \begin{equation*} \phi_{4}(m)=\frac{-36 - 100 m - 13 m^2 + 4 m^3 + m^4}{24(m+6)}\binom{2m}{m-5}\quad\mbox{\rm(\seqnum{A120812})}. \end{equation*} \end{prop} \begin{prop} \begin{multline*} \Phi_{5}(t)=\frac{\partial^{5}}{\partial^{5} q} g_{6}(t)|_{q=0}\\ =t^6 C^{13} \frac{-14 - 540 C + 1519 C^2 - 1517 C^3 + 616 C^4 + 70 C^5 - 199 C^6 + 97 C^7 - 22 C^8 + 2 C^9}{(2-C)^{9}}, \end{multline*} \begin{equation*} \phi_{5}(m)=\frac{(m+4)(-108 - 192 m +3 m^2 + 8 m^3 + m^4)}{120(m+7)}\binom{2m}{m-6}\quad\mbox{\rm(\seqnum{A120813})}. \end{equation*} \end{prop} \begin{prop} \begin{multline*} \Phi_{6}(t)=\frac{\partial^{6}}{\partial^{6} q} g_{7}(t)|_{q=0}\\ =\frac{t^6 C^{13}}{(2-C)^{11}} \big(-42 + 4054 C - 18354 C^2 + 36038 C^3 - 40660 C^4 + 30080 C^{5} - 16090 C^6 + 6914 C^7\\ - 2604 C^8 + 840 C^9 - 202 C^{10} + 30 C^{11} - 2C^{12}\big), \end{multline*} \begin{multline*} \phi_{6}(m)=\frac{\binom{2m}{m-6}}{720(m+7)(m+8)}\big(20160 + 44448 m + 548 m^2 - 4196 m^3 - 565 m^4 + 67 m^5 + 17 m^6 + m^7\big)\\ \mbox{\rm(\seqnum{A120814})}. \end{multline*} \end{prop} \begin{prop} \begin{multline*} \Phi_{7}(t)=\frac{\partial^{7}}{\partial^{7} q} g_{8}(t)|_{q=0}\\ =\frac{t^7 C^{15}}{(2-C)^{13}} \big( 132 + 16516 C - 92666 C^2 + 215944 C^3 - 281094 C^4 + 225628 C^5 - 110922 C^6 + 25360 C^7\\ + 7066 C^8 - 9364 C^9 + 4622 C^{10} - 1440 C^{11} + 294 C^{12} - 36 C^{13} + 2 C^{14} \big), \end{multline*} \begin{multline*} \phi_{7}(m)=\frac{\binom{2m}{m-7}}{5040(m+8)(m+9)}\big((m+5)(40320 + 67824 m - 20180 m^2 - 7556 m^3 - 5 m^4 + 211 m^5 \\+ 25 m^6 + m^7\big) \quad\mbox{\rm(\seqnum{A120815})}. \end{multline*} \end{prop} \begin{prop} \begin{multline*} \Phi_{8}(t)=\frac{\partial^{8}}{\partial^{8} q} g_{9}(t)|_{q=0}\\ =\frac{t^7 C^{15}}{(2-C)^{15}} \big( 429 - 65536 C + 499576 C^2 - 1679496 C^3 + 3298054 C^4 - 4270444 C^5 + 3911698 C^6\\ - 2671744 C^7 + 1439239 C^8 - 659504 C^9 + 279446 C^{10} - 112922 C^{11} + 41165 C^{12}\\ - 12362 C^{13} + 2816 C^{14} - 448 C^{15} + 44 C^{16} - 2 C^{17} \big), \end{multline*} \begin{multline*} \phi_{8}(m)=\frac{\binom{2m}{m-7}}{40320(m+8)(m+9)(m+10)}\big( -7983360 - 12956832 m + 10475400 m^2 + 3647724 m^3\\ - 416326 m^4 - 249417 m^5 - 19971 m^6 + 2646 m^7 + 576 m^8 + 39 m^9 + m^{10} \big)\quad\mbox{\rm(\seqnum{A120816})} \end{multline*} \end{prop} \bibliographystyle{abbrv} \begin{thebibliography}{1} \bibitem{BS2000} E.~Babson and E.~Steingr{\'\i}msson, \newblock \href{http://www.emis.de/journals/SLC/wpapers/s44stein.html}{Generalized permutation patterns and a classification of the {M}ahonian statistics}, \newblock {\em S{\'e}m. Lothar. Combin.}, Art.\ B44b (2000), electronic. \bibitem{BCEPR2006} R.~Brak, S.~Corteel, J.~Essam, R.~Parviainen, and A.~Rechnitzer, \newblock A combinatorial derivation of the {PASEP} stationary state. \newblock Submitted for publication. \bibitem{Clas2001} A.~Claesson, \newblock Generalized pattern avoidance, \newblock {\em European J. Combin.}, {\bf 22} (2001), 961--971. \bibitem{CM2002} A.~Claesson and T.~Mansour, \newblock Counting patterns of type (1,2) and (2,1) in permutations, \newblock {\em Adv. in Appl. Math.}, {\bf 29} (2002), 293--310. \bibitem{Flaj1980} P.~Flajolet. \newblock Combinatorial aspects of continued fractions. \newblock {\em Discrete Math.}, {\bf 2} (1980), 125--161. \bibitem{FZ1990} D.~Foata and D.~Zeilberger, \newblock Denert's permutation statistic is indeed {E}uler-{M}ahonian, \newblock {\em Stud. Appl. Math.}, {\bf 83} (1990), 31--59. \bibitem{OEIS} N. J. A. Sloane, \newblock {\em The On-Line Encyclopedia of Integer Sequences}, published electronically at \href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/$\sim$njas/sequences/}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: 05A05, 05A15.\\ \noindent {\it Keywords}: Permutations, restricted pattern, Motzkin paths, generating functions. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000108}, \seqnum{A002696}, \seqnum{A094218}, \seqnum{A094219}, \seqnum{A120812}, \seqnum{A120813}, \seqnum{A120814}, \seqnum{A120815}, and \seqnum{A120816}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received July 6 2006; revised version received July 11 2006. Published in {\it Journal of Integer Sequences}, July 19 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}