\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} \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}}} %\usepackage{epsfig} %\usepackage{algorithm} %\usepackage{algorithmic} \usepackage{array} \usepackage{tikz}\usetikzlibrary{patterns} \def\scale{0.3} \setlength\extrarowheight{4pt} \def\A{0.5cm} \def\B{1.5cm} \def\C{2.5cm} \def\D{3.5cm} \def\E{4.5cm} \def\F{5.5cm} \def\G{6.5cm} \def\H{7.5cm} \def\I{8.5cm} \def\J{9.5cm} \def\K{10.5cm} \def\L{11.5cm} \def\M{12.5cm} \def\N{13.5cm} \def\O{14.5cm}\def\P{15.5cm}\def\Q{16.5cm}\def\R{17.5cm}\def\S{18.5cm}\def\T{19.5cm} \def\U{20.5cm}\def\V{21.5cm}\def\W{22.5cm}\def\Y{24.5cm}\def\ZZ{26.5cm}\def\Za{28.5cm}\def\Zb{30.5cm}\def\Zc{32.5cm}\def\Zd{34.5cm}\def\Ze{36.5cm} \def\sizePoint{6pt} \def\sizePointv{9pt} \def\sizeCircle{10pt} \newcommand{\pointr}[2]{\fill [color=red] (canvas cs:x=#1,y=#2) circle (\sizePointv); } \newcommand{\pointv}[2]{\fill [color=green] (canvas cs:x=#1,y=#2) circle (\sizePoint); } \newcommand{\point}[2]{\fill (canvas cs:x=#1,y=#2) circle (\sizePoint); } \newcommand{\pointVide}[2]{\fill [color=white] (canvas cs:x=#1,y=#2) circle (\sizePoint); \draw (canvas cs:x=#1,y=#2) circle (\sizePoint); } \newcommand{\pointCercle}[2]{\point{#1}{#2} \draw (canvas cs:x=#1,y=#2) circle (\sizeCircle); } \renewcommand{\arraystretch}{1} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two \\ } \vskip 1cm \large Jean-Luc Baril and Armen Petrossian\\ LE2I UMR CNRS 6306\\ University of Bourgogne\\ 21078 Dijon \\ France \\ \href{mailto:barjl@u-bourgogne.fr}{\tt barjl@u-bourgogne.fr}\\ \href{mailto:armen.petrossian@u-bourgogne.fr}{\tt armen.petrossian@u-bourgogne.fr} \end{center} \vskip .2 in \begin{abstract} For any pattern $\alpha$ of length at most two, we enumerate equivalence classes of Motzkin paths where two paths of the same length are equivalent whenever they coincide on all occurrences of the pattern $\alpha$. \end{abstract} \section{Introduction and notation} A {\it Motzkin path} of length $n$, $n\geq 0$, is a lattice path starting at point $(0,0)$, ending at $(n,0)$, and never going below the $x$-axis, consisting of up steps $U=(1,1)$, down steps $D=(1,-1)$ and flat steps $F=(1,0)$. See Figure \ref{fig1} for an illustration of a Motzkin path of length 18. Let $\mathcal{M}$ be the set of all Motzkin paths. A {\it pattern} of length one (resp., two) in $M\in\mathcal{M}$ consists of one step (resp., two consecutive steps). We will say that an {\it occurrence} of a pattern is at position $i$, $i\geq 1$, in $M$ whenever the first step of this occurrence appears at the $i$-th step of the path. The {\it height} of this occurrence is the minimal ordinate reached by its points. For instance, the path $M=UUFDDFFUDUFUDDFFUD$ (see Figure \ref{fig1}) contains three occurrences of the pattern $FU$ at positions $7$, $11$ and $16$, respectively at heights $0$, $1$ and $0$. A Motzkin path will be called {\it Dyck path} when it does not contain any flat step $F$. Let $\mathcal{D}$ be the set of all Dyck paths. \begin{figure}[h] \begin{center} $\begin{tabular}{c}\begin{tikzpicture}[scale=0.2] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\E) -- (\I,\C) -- (\K,\A) -- (\M,\A) -- (\O,\A) -- (\Q,\C) -- (\S,\A) -- (\U,\C) -- (\W,\C) --(\Y,\E) -- (\ZZ,\C) --(\Za,\A) -- (\Zb,\A) -- (\Zc,\A) -- (\Zd,\C) -- (\Ze, \A); \end{tikzpicture} \end{tabular}$ \end{center} \caption{A Motzkin path $M=UUFDDFFUDUFUDDFFUD$.} \label{fig1} \end{figure} Many statistics on Motzkin and Dyck paths have been studied. Almost always, it is shown how we can enumerate these paths according to several parameters, such as length, number of occurrences of a pattern, number of returns to the $x$-axis (see, for instance, \cite{Deu, Man1,Man2,Man3,Mer,Pan,Pea,Sap,Sap1,Sun} for Dyck paths and \cite{Barc,Bre,Don,Dra,Man4,Pro,Sap2} for Motzkin paths). Recently in \cite{Bar}, the authors investigate equivalence relations on the set $\mathcal{D}$ of Dyck paths where two Dyck paths of the same length are equivalent whenever they coincide on all occurrences of a given pattern. In this paper, we study these equivalence relations on the set $\mathcal{M}$ of Motzkin paths for any pattern $\alpha$ of length at most two, i.e., {\it two Motzkin paths of the same length are $\alpha$-equivalent whenever all occurrences of the pattern $\alpha$ appear at the same positions in the two paths.} For instance, $UDUFDF\mathbf{FU}UF\mathbf{FU}DDD\mathbf{FU}D$ is $FU$-equivalent to the path in Figure \ref{fig1} since all occurrences of the pattern $FU$ (in boldface) appear at the same positions in the two paths. For any pattern $\alpha$ of length at most two, we provide generating functions for the number of $\alpha$-equivalence classes in $\mathcal{M}$, with respect to the length (see Table \ref{tab1}). The general method used consists of exhibiting one-to-one correspondences between some subsets of Motzkin paths and the different sets of equivalence classes by using combinatorial reasonings, and then, evaluating algebraically the generating functions for these subsets. \vskip1cm \begin{table}[h]\label{tab1} \begin{center} \scalebox{1}{$\begin{array}{|c|c|c|c|}\hline \mbox{ Pattern }&\mbox{ Sequence }&\mbox{ Sloane }& a_{n}, 1\leq n\leq 10\\\hline \{U\},\{D\}& \frac{2}{1-2x+\sqrt{1-4x^2}}& \seqnum{A001405}&1,2,3,6,10,20,35,70,126,252\\ \hline \{F\}&2^n & \seqnum{A000079}&1,2,4,8,16,32,64,128,256,512\\ \hline \{UU\},\{DD\}&\frac{(x-1)^2-\sqrt{(1-3x^2)(x^2+1)} }{2x(x^3-(1-x)^2)}&\seqnum{A191385}& 1,1,1,2,3,5,7,12,18,31\\ \hline \{DU\}& \mbox{Shift of Fibonacci} &\seqnum{A132916} &1, 1, 1, 2, 3, 5, 8, 13, 21,34\\ \hline \{UD\}&\mbox{Fibonacci}&\seqnum{A000045} &1, 2, 3, 5, 8, 13, 21, 34, 55,89\\ \hline \begin{array}{c}\{UF\},\{DF\}, \\ \{FU\},\{FD\}\end{array}&\frac{2}{1 - 2x - \sqrt{1-4x^3}}&\seqnum{A165407} &1,1,2, 3, 4, 7, 11, 16, 27, 43\\ \hline \{FF\}& \scriptstyle{\frac{x(1-x-x^2+3x^3-5x^4+3x^5-2x^6-x^7-x^9)}{(1-x-2x^4-x^6-x^7)(1-2x+x^2-x^3)}}&\mbox{New} &1, 2, 2, 5, 9, 17, 29, 53, 94,168\\ \hline \end{array}$} \caption{Number of $\alpha$-equivalence classes for Motzkin paths.} \end{center} \end{table} \section{Equivalence classes modulo a pattern of length one} Throughout this section, we study the $\alpha$-equivalence in $\mathcal{M}$ for $\alpha\in \{U,D,F\}$. \subsection{Modulo $\alpha=F$} Let $\mathcal{A}$ be the set of Motzkin paths without any points of ordinate greater than one. For instance, we have $UFDUDF\in\mathcal{A}$ and $UUDDUD\notin\mathcal{A}$. \begin{lemma}\label{le1} There is a bijection between $\mathcal{A}$ and the set of $F$-equivalence classes of $\mathcal{M}$. \end{lemma} \begin{proof} Let $M$ be a Motzkin path in $\mathcal{M}\backslash\mathcal{A}$. Let us prove that there exists $M'\in\mathcal{A}$ (with the same length as $M$) such that $M$ and $M'$ belong to the same class. Since $M$ does not belong to $\mathcal{A}$, we can write $M=RUQD S$, where $R$ is of maximal length so that it does not contain any point of ordinate two, and $Q$ is a (possibly empty) Motzkin path. Now, we define a sequence of Motzkin paths $M_0=M, M_1,M_2,\ldots , M_{k-1},M_k=M'$, $k\geq 1$, where for any $i$, $1\leq i\leq k$, the Motzkin path $M_i$ is obtained from $M_{i-1}$ by performing the following process. \medskip \noindent {\it Let $M_{i-1}=RUQDS$ be the above decomposition. Then, $M_i=RDQUS$ is obtained from $M_{i-1}$ by swapping the two steps $U$ and $D$ contiguous to $Q$.} \medskip The process finishes because it decreases the number of points of ordinate greater than one. All Motzkin paths $M_0=M,M_1,\ldots , M_k=P'$ belong to the same equivalence class. So, at the end of the process $M_k$ belongs to $\mathcal{A}$. For instance, if $$M=UUUDUFDFUFFDFFDDUD,$$ then we obtain $M_1=M'=UDUDUFDFUFFDFFUDUD$. See Figure \ref{fig2} for an illustration of this example. Now we will prove that any $F$-equivalence class contains at most one element in $\mathcal{A}$. For a contradiction, let $M$ and $M'$ be two different Motzkin paths in $\mathcal{A}$ belonging to the same class. We write $M=QR$ and $M'=QS$ where $R$ and $S$ start with two different steps. Since $M$ and $M'$ lie in the same class, these steps cannot be $F$. Without loss of generality, let us assume that the first step of $R$ is an up step $U$ and then, the first step of $S$ is a down step $D$. This means that the last point of $Q$ has its ordinate equal to zero (otherwise, $R$ would contain a point of ordinate at least two). As $S$ starts with a down step, $S$ has its second point (from the left) with an ordinate equal to $-1$, which gives a contradiction. \end{proof} \medskip \begin{figure} \begin{center} $M=$ \begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[solid,line width=0.4mm,color=cyan] (\C,\C)--(\E,\E); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C); \draw[solid,line width=0.4mm](\E,\E) -- (\G,\G) -- (\I,\E) -- (\K,\G) -- (\M,\G) -- (\O,\E) -- (\Q,\E) -- (\S,\G) -- (\U,\G) -- (\W,\G) --(\Y,\E) -- (\ZZ,\E) --(\Za,\E) -- (\Zb,\C); \draw[solid,line width=0.4mm,color=cyan] (\Za,\E)-- (\Zb,\C); \draw[solid,line width=0.4mm] (\Zb,\C)--(\Zc,\A)-- (\Zd,\C) -- (\Ze, \A); \end{tikzpicture}\\ \end{tabular} $\longrightarrow$ $M'=$\begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[line width=0.3mm,color=red] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\G) -- (\I,\E) -- (\K,\G) -- (\M,\G) -- (\O,\E) -- (\Q,\E) -- (\S,\G) -- (\U,\G) -- (\W,\G) --(\Y,\E) -- (\ZZ,\E) --(\Za,\E) -- (\Zb,\C) -- (\Zc,\A) -- (\Zd,\C) -- (\Ze, \A); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C); \draw[solid,line width=0.4mm,color=cyan] (\C,\C) -- (\E,\A); \draw[solid,line width=0.4mm] (\E,\A) -- (\G,\C) -- (\I,\A) -- (\K,\C) -- (\M,\C) -- (\O,\A) -- (\Q,\A) -- (\S,\C) -- (\U,\C) -- (\W,\C) --(\Y,\A) -- (\ZZ,\A) --(\Za,\A); \draw[solid,line width=0.4mm,color=cyan] (\Za,\A) -- (\Zb,\C); \draw[solid,line width=0.4mm] (\Zb,\C) -- (\Zc,\A) -- (\Zd,\C) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular} \end{center} \caption{Illustration of the example described in the proof of Lemma \ref{le1}.} \label{fig2} \end{figure} \begin{theorem}\label{thm1} The generating function for the set of $F$-equivalence classes in $\mathcal{M}$ with respect to the length is given by $$\frac{1-x}{1-2x}.$$\end{theorem} \begin{proof} Using Lemma \ref{le1}, it suffices to obtain the generating function $A(x)$ for the set $\mathcal{A}$. A non-empty Motzkin path $M\in\mathcal{A}$ can be written either $M=FQ$ where $Q\in \mathcal{A}$ or $M=UF^rDQ$ where $r\geq 0$ and $Q\in\mathcal{A}$. Then, we deduce the functional equation $A(x)=1+xA(x)+\frac{x^2}{1-x}A(x)$ which implies that $A(x)=\frac{1-x}{1-2x}$. \end{proof} \subsection{Modulo $\alpha=U$ or $\alpha=D$} The result for the case $\alpha=D$ is deduced from $\alpha=U$ using a simple symmetry (the mirror transformation on Motzkin paths). So, we set $\alpha=U$ in this part. Let $\mathcal{B}$ be the set of Motzkin paths without any flat steps at positive height. For instance, we have $UDFUD\in\mathcal{B}$ and $UFDUD\notin\mathcal{B}$. \begin{lemma}\label{le2} There is a bijection between $\mathcal{B}$ and the set of $U$-equivalence classes of $\mathcal{M}$. \end{lemma} Let $M$ be a Motzkin path in $\mathcal{M}\backslash\mathcal{B}$. Let us prove that there exists a Motzkin path $M'\in\mathcal{B}$ (with the same length as $M$) such that $M$ and $M'$ belong to the same class. Since $M$ does not belong to $\mathcal{B}$, there exists a Motzkin path $Q$ (possibly empty) such that $M=RFQD S$ where $R$ is maximal so that it does not contain any flat step at positive height, its last point has an ordinate of at least one, and $Q$ is a Motzkin path. Now, we define a sequence of Motzkin paths $M_0=M, M_1,M_2,\ldots , M_{k-1},M_k=M'$, $k\geq 1$, where for any $i$, $1\leq i\leq k$, the Motzkin path $M_i$ is obtained from $M_{i-1}$ by performing the following process. \medskip \noindent {\it Let $M_{i-1}=RFQDS$ be the above decomposition. Then, we define the Motzkin path $M_i=RDQFS$ obtained from $M_{i-1}$ by swapping the two steps $F$ and $D$ contiguous to $Q$.} \medskip The process finishes because it decreases the height of the leftmost flat step having a positive height. All Motzkin paths $M_0=M,M_1,\ldots , M_k=M'$ belong to the same equivalence class. So, at the end of the process, $M_k$ belongs to $\mathcal{B}$. For instance, if we perform the above process on $M=UUUDFFFFUUDDFFDDFF$, then we obtain $M_1=UUUDDFFFUUDDFFFDFF$ and $M_2=M'=UUUDDDFFUUDDFFFFFF$ (see Figure \ref{fig3} for an illustration of this example). Now we will prove that any $U$-equivalence class contains at most one element in $B$. For a contradiction, let $M$ and $M'$ be two different Motzkin paths in $\mathcal{B}$ belonging to the same class. We write $M=QR$ and $M'=QS$ where $R$ and $S$ start with two different steps. Since $M$ and $M'$ lie in the same class, these steps cannot be $U$. Without loss of generality, let us assume that the first step of $R$ is a down step $D$ and then, the first step of $S$ is a flat step $F$. This means that the last point of $Q$ has its ordinate equal to zero (otherwise $M'$ could not belong to $\mathcal{B}$). As the first step of $R$ is $D$, the second point of $R$ has an ordinate equal to -1 which gives a contradiction.\hfill $\Box$ \medskip \begin{figure} \begin{center} $M=M_0=$\begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\G) -- (\I,\E); \draw[solid,line width=0.4mm,color=cyan] (\I,\E) -- (\K,\E); \draw[solid,line width=0.4mm] (\K,\E) -- (\M,\E) -- (\O,\E) -- (\Q,\E) -- (\S,\G) -- (\U,\I) -- (\W,\G) --(\Y,\E) -- (\ZZ,\E) --(\Za,\E); \draw[solid,line width=0.4mm,color=cyan] (\Za,\E) -- (\Zb,\C); \draw[solid,line width=0.4mm] (\Zb,\C) -- (\Zc,\A) -- (\Zd,\A) -- (\Ze, \A); \end{tikzpicture}\\ \end{tabular} $\longrightarrow M_1=$ \begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[line width=0.3mm,color=red] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\G) -- (\I,\E) -- (\K,\E) -- (\M,\E) -- (\O,\E) -- (\Q,\E) -- (\S,\G) -- (\U,\I) -- (\W,\G) --(\Y,\E) -- (\ZZ,\E) --(\Za,\E) -- (\Zb,\C) -- (\Zc,\A) -- (\Zd,\A) -- (\Ze, \A); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\G) -- (\I,\E) -- (\K,\C); \draw[line width=0.3mm,color=cyan] (\K,\C)-- (\M,\C); \draw[solid,line width=0.4mm] (\M,\C)-- (\O,\C) -- (\Q,\C) -- (\S,\E) -- (\U,\G) -- (\W,\E) --(\Y,\C) -- (\ZZ,\C) --(\Za,\C) -- (\Zb,\C); \draw[line width=0.3mm,color=cyan] (\Zb,\C)-- (\Zc,\A); \draw[solid,line width=0.4mm] (\Zc,\A) -- (\Zd,\A) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular} \end{center} \begin{center}$\longrightarrow M_2=M'= $ \begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[line width=0.3mm,color=red] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\G) -- (\I,\E) -- (\K,\C) -- (\M,\C) -- (\O,\C) -- (\Q,\C) -- (\S,\E) -- (\U,\G) -- (\W,\E) --(\Y,\C) -- (\ZZ,\C) --(\Za,\C) -- (\Zb,\C) -- (\Zc,\A) -- (\Zd,\A) -- (\Ze, \A); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\G) -- (\I,\E) -- (\K,\C); \draw[solid,line width=0.4mm] (\K,\C)-- (\M,\A); \draw[solid,line width=0.4mm] (\M,\A)-- (\O,\A) -- (\Q,\A) -- (\S,\C) -- (\U,\E) -- (\W,\C) --(\Y,\A) -- (\ZZ,\A) --(\Za,\A) -- (\Zb,\A); \draw[solid,line width=0.4mm] (\Zb,\A)-- (\Zc,\A); \draw[solid,line width=0.4mm] (\Zc,\A)-- (\Zd,\A) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular}\\ \end{center} \caption{Illustration of the example described in the proof of Lemma \ref{le2}.} \label{fig3} \end{figure} \begin{theorem}\label{thm2} The generating function for the set of $U$-equivalence (resp., $D$-equivalence) classes in $\mathcal{M}$ with respect to the length is given by $$\frac{2}{1-2x+\sqrt{1-4x^2}}.$$\end{theorem} \begin{proof} Using Lemma \ref{le2}, it suffices to obtain the generating function $B(x)$ for the set $\mathcal{B}$. A non-empty Motzkin path $M\in\mathcal{B}$ can be written either $M=FQ$ where $Q\in \mathcal{B}$ or $M=UQDQ'$ where $Q$ is a Dyck path in $\mathcal{D}$ and $Q'\in \mathcal{B}$. Then, we deduce the functional equation $B(x)=1+xB(x)+x^2C(x^2)B(x)$ where $C(x)=\frac{1-\sqrt{1-4x}}{2x}$ is the generating function for the set $\mathcal{D}$ of Dyck paths. A simple calculation gives the result. \end{proof} \section{Equivalence classes modulo a pattern of length two} Throughout this section, we study the $\alpha$-equivalence in $\mathcal{M}$ for any pattern $\alpha$ of length two. By considering the mirror transformation of Motzkin paths, it suffices to examine the cases where $\alpha\in\{UU,UD,UF,FU, DU, FF\}$. \subsection{Modulo $\alpha=UU$} Let $\mathcal{E}$ be the set of Motzkin paths without any flat steps at positive height and having no ascents of length one, i.e., no maximal consecutive up steps of length one. For instance, we have $UUDDF\in\mathcal{E}$ and $FUDFF\notin\mathcal{E}$. \begin{lemma}\label{le3} There is a bijection between $\mathcal{E}$ and the set of $UU$-equivalence classes of $\mathcal{M}$. \end{lemma} \begin{proof} Let $M$ be a Motzkin path in $\mathcal{M}\backslash\mathcal{E}$. Let us prove that there exists a Motzkin path $M'\in \mathcal{E}$ of the same length as $M$ such that $M$ and $M'$ belong to the same class. We define a sequence of Motzkin paths $M_0=M,M_1,M_2,\ldots , M_{k-1},M_k=M'$, $k\geq 1$, where for any $i$, $1\leq i\leq k$, the Motzkin path $M_{i}$ is obtained from $M_{i-1}$ by performing the following process. \medskip {\it \noindent (1) If there is an ascent of length one in $M_{i-1}$, then we write $M_{i-1}=RUQDS$ where $R$ is of maximal length so that it does not contains any ascent of length one, $R$ does not finish with $U$, and $Q$ is a Motzkin path (possibly empty) that does not start with an up step. So, we set $M_i=RFQFS$; \medskip \noindent (2) Otherwise, if there is a flat step at positive height, then we perform the process described in the proof of Lemma \ref{le2}. } \medskip This process finishes because part (1) of the process decreases by one the number of ascents of length one, and part (2) decreases the height of the leftmost flat step having a positive height (see the proof of Lemma \ref{le2}). All Motzkin paths $M_0=M,M_1,\ldots,M_k=M'$ belong to the same class. At the end of the process, $M_k$ belongs to $\mathcal{E}$. For instance, if we perform the above process on $M=M_0=UUUDUFDFUUDDUDDDUD$ then we obtain $M_3=UUUDFFFFUUDDFFDDFF$ after three runs of (1), and we obtain $M_5=UUUDDDFFUUDDFFFFFF$ after two runs of (2) (see Figure \ref{fig4} for an illustration of this example). \begin{figure} \begin{center} $M=M_0=$\begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\G) -- (\I,\E) -- (\K,\G) -- (\M,\G) -- (\O,\E) -- (\Q,\E) -- (\S,\G) -- (\U,\I) -- (\W,\G) --(\Y,\E) -- (\ZZ,\G) --(\Za,\E) -- (\Zb,\C) -- (\Zc,\A) -- (\Zd,\C) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular} $\stackrel{(1),(1),(1)}{\longrightarrow} M_3$ \begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[line width=0.3mm,color=red] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\G) -- (\I,\E) -- (\K,\G) -- (\M,\G) -- (\O,\E) -- (\Q,\E) -- (\S,\G) -- (\U,\I) -- (\W,\G) --(\Y,\E) -- (\ZZ,\G) --(\Za,\E) -- (\Zb,\C) -- (\Zc,\A) -- (\Zd,\C) -- (\Ze, \A); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\G) -- (\I,\E) -- (\K,\E) -- (\M,\E) -- (\O,\E) -- (\Q,\E) -- (\S,\G) -- (\U,\I) -- (\W,\G) --(\Y,\E) -- (\ZZ,\E) --(\Za,\E) -- (\Zb,\C) -- (\Zc,\A) -- (\Zd,\A) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular}\\ \end{center} \begin{center} $\stackrel{(2),(2)}{\longrightarrow} M_5=M'= $ \begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[line width=0.3mm,color=red] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\G) -- (\I,\E) -- (\K,\E) -- (\M,\E) -- (\O,\E) -- (\Q,\E) -- (\S,\G) -- (\U,\I) -- (\W,\G) --(\Y,\E) -- (\ZZ,\E) --(\Za,\E) -- (\Zb,\C) -- (\Zc,\A) -- (\Zd,\A) -- (\Ze, \A); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C) -- (\E,\E) -- (\G,\G) -- (\I,\E) -- (\K,\C) -- (\M,\A) -- (\O,\A) -- (\Q,\A) -- (\S,\C) -- (\U,\E) -- (\W,\C) --(\Y,\A) -- (\ZZ,\A) --(\Za,\A) -- (\Zb,\A) -- (\Zc,\A) -- (\Zd,\A) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular}\\ \end{center} \caption{Illustration of the example described in the proof of Lemma \ref{le3}.} \label{fig4} \end{figure} \bigskip For a contradiction, let $M$ and $M'$ be two different Motzkin paths in $\mathcal{E}$ belonging to the same class. We write $M=QR$ and $M'=QS$ where $R$ and $S$ start with two different steps, and $R$ and $S$ cannot start with $UU$. We distinguish two cases. If the last step of $Q$ is a down step $D$ or a flat step $F$, then $R$ and $S$ cannot start with $UF$ and $UD$ (and also with $U$) because an ascent of length one would be created; if the last step of $Q$ is an up step $U$, then $R$ and $S$ cannot start with $U$ because a pattern $UU$ would be created. Without loss of generality, we can assume (for the two last cases) that $R$ (resp., $S$) starts with $D$ (resp., with $F$); so, the last point of $Q$ has a positive ordinate that implies that the first step of $S$ is a flat step of positive height, which is a contradiction. \end{proof} \begin{theorem}\label{thm3} The generating function for the set of $UU$-equivalence classes of $\mathcal{M}$ with respect to the length is given by $$\frac{(x-1)^2-\sqrt{(1-3x^2)(x^2+1)} }{2x(x^3-(1-x)^2)}.$$\end{theorem} \begin{proof} Using Lemma \ref{le3}, it suffices to give the generating function for the set $\mathcal{E}$, which is already known (see \seqnum{A191385} in \cite{Sloa}).\end{proof} \subsection{Modulo $\alpha=DU$} Let $\mathcal{F}$ be the set of Motzkin paths without any points of ordinate greater than one, and without any flat steps at height zero. For instance, we have $UFDUFFDUD\in\mathcal{F}$ and $UDFUUDD\notin\mathcal{F}$. \begin{lemma}\label{le4} There is a bijection between $\mathcal{F}\cup\{F\}$ and the set of $DU$-equivalence classes of $\mathcal{M}$. \end{lemma} \begin{proof} Let $M\neq F$ be a Motzkin path in $\mathcal{M}\backslash\mathcal{F}$ (the case where $M=F$ is clear). Let us prove that there exists a Motzkin path $M'\in \mathcal{F}$ of the same length as $M$ such that $M$ and $M'$ belong to the same class. Any Motzkin path $M\in\mathcal{M}$ can be uniquely written either $$M=\beta_0 \qquad\mbox{ or } \qquad M=\beta_0(DU\beta_1)\cdots(DU\beta_{r}),$$ where $r\geq 1$, and $\beta_i$, $0\leq i\leq r$, (possibly empty) does not contain any pattern $DU$. If $M=\beta_0$ then we set $M'=UF^{s_0-2}D$ where $s_0\geq 2$ is the length of $M$; otherwise, we set $M'=UF^{s_0-1}(DUF^{s_1})\cdots (DUF^{s_{r-1}})(DUF^{s_r-1})D$ where $s_i$, $0\leq i\leq r$, is the length of $\beta_i$. By construction, $M$ and $M'$ belong to the same equivalence class and $M'$ lies in $\mathcal{F}$. For instance, if $M=FUFDUUUDUDDUUFFDDD$ then we obtain $M'=UFFDUFFDUFFDUFFFFD$ (see Figure \ref{fig5} for an illustration of this example). \begin{figure}[h] \begin{center} $M=$\begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\A) -- (\E,\C) -- (\G,\C); \draw[solid,line width=0.4mm,color=cyan] (\G,\C)-- (\I,\A) -- (\K,\C); \draw[solid,line width=0.4mm] (\K,\C) -- (\M,\E) -- (\O,\G); \draw[solid,line width=0.4mm,color=cyan] (\O,\G) -- (\Q,\E) -- (\S,\G); \draw[solid,line width=0.4mm] (\S,\G)-- (\U,\E); \draw[solid,line width=0.4mm,color=cyan] (\U,\E)-- (\W,\C) --(\Y,\E); \draw[solid,line width=0.4mm] (\Y,\E) -- (\ZZ,\G) --(\Za,\G) -- (\Zb,\G) -- (\Zc,\E) -- (\Zd,\C) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular} $\longrightarrow M'=$\begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C) -- (\E,\C) -- (\G,\C) -- (\I,\A) -- (\K,\C) -- (\M,\C) -- (\O,\C) -- (\Q,\A) -- (\S,\C) -- (\U,\C) -- (\W,\C) --(\Y,\A) -- (\ZZ,\C) --(\Za,\C) -- (\Zb,\C) -- (\Zc,\C) -- (\Zd,\C) -- (\Ze, \A); \draw[line width=0.3mm,color=red] (\A,\A)--(\C,\A) -- (\E,\C) -- (\G,\C) -- (\I,\A) -- (\K,\C) -- (\M,\E) -- (\O,\G) -- (\Q,\E) -- (\S,\G) -- (\U,\E) -- (\W,\C) --(\Y,\E) -- (\ZZ,\G) --(\Za,\G) -- (\Zb,\G) -- (\Zc,\E) -- (\Zd,\C) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular}\\ \end{center} \caption{Illustration of the example in the proof of Lemma \ref{le5}.} \label{fig5} \end{figure} Any Motzkin path $M\in\mathcal{F}$ is characterized by the positions of its pattern $DU$. So, two different Motzkin paths in $\mathcal{F}$ cannot belong to the same class, which completes the proof. \end{proof} \begin{theorem}\label{thm4} The generating function for the set of $DU$-equivalence classes of $\mathcal{M}$ with respect to the length is given by $F(x)=\frac{1-x^2-x^3}{1 - x - x^2}$, that corresponds to a shift of the Fibonacci sequence. \end{theorem} \begin{proof} Using Lemma \ref{le4}, it suffices to provide the generating function $F(x)$ for the set $\mathcal{F}\cup\{F\}$. Let $M$ be a non-empty Motzkin path in $\mathcal{F}$. It can be written $M=UF^rDQ$ where $r\geq 0$ and $Q\in\mathcal{F}$. So, we have the functional equation $F(x)=1+x+\frac{x^2}{1-x}(F(x)-x)$ which implies the result.\end{proof} \subsection{Modulo $\alpha=UD$} Let $\mathcal{G}$ be the set of Motzkin paths without any points of ordinate greater than one, and without any flat steps at positive height. For instance, we have $FUDFUD\in\mathcal{G}$ and $UFDUUDD\notin\mathcal{G}$. \begin{lemma}\label{le5} There is a bijection between $\mathcal{G}$ and the set of $UD$-equivalence classes of $\mathcal{M}$. \end{lemma} \begin{proof} Let $M$ be a Motzkin path in $\mathcal{M}\backslash\mathcal{G}$. Let us prove that there exists a Motzkin path $M'\in \mathcal{G}$ of the same length as $M$ such that $M$ and $M'$ belong to the same class. Any Motzkin path $M\in\mathcal{M}$ can be uniquely written either $$M=\beta_0 \qquad\mbox{ or } \qquad M=\beta_0(UD\beta_1)\cdots(UD\beta_{r}),$$ where $r\geq 1$, and $\beta_i$, $0\leq i\leq r$, (possibly empty) does not contain any pattern $UD$. If $M=\beta_0$ then we set $M'=F^{s_0}$ where $s_0\geq 0$ is the length of $M$; otherwise, we set $M'=F^{s_0}(UDF^{s_1})\cdots (UDF^{s_r})$ where $s_i$, $0\leq i\leq r$, is the length of $\beta_i$. Obviously, $M$ and $M'$ belong to the same equivalence class and $M'$ lies in $\mathcal{G}$. For instance, if $M=FUFDUUUDUDDUUUDDDD$ then we obtain $M'=FFFFFFUDUDFFFUDFFF$ (see Figure \ref{fig6} for an illustration of this example). \begin{figure}[h] \begin{center} $M=$\begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\A) -- (\E,\C) -- (\G,\C) -- (\I,\A) -- (\K,\C) -- (\M,\E); \draw[solid,line width=0.4mm,color=cyan] (\M,\E) -- (\O,\G) -- (\Q,\E) -- (\S,\G) -- (\U,\E); \draw[solid,line width=0.4mm] (\U,\E) -- (\W,\C) --(\Y,\E) -- (\ZZ,\G); \draw[solid,line width=0.4mm,color=cyan] (\ZZ,\G)--(\Za,\I) -- (\Zb,\G); \draw[solid,line width=0.4mm] (\Zb,\G)-- (\Zc,\E) -- (\Zd,\C) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular} $\longrightarrow M'=$\begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\A) -- (\E,\A) -- (\G,\A) -- (\I,\A) -- (\K,\A) -- (\M,\A) -- (\O,\C) -- (\Q,\A) -- (\S,\C) -- (\U,\A) -- (\W,\A) --(\Y,\A) -- (\ZZ,\A) --(\Za,\C) -- (\Zb,\A) -- (\Zc,\A) -- (\Zd,\A) -- (\Ze, \A); \draw[line width=0.3mm,color=red] (\A,\A)--(\C,\A) -- (\E,\C) -- (\G,\C) -- (\I,\A) -- (\K,\C) -- (\M,\E) -- (\O,\G) -- (\Q,\E) -- (\S,\G) -- (\U,\E) -- (\W,\C) --(\Y,\E) -- (\ZZ,\G) --(\Za,\I) -- (\Zb,\G) -- (\Zc,\E) -- (\Zd,\C) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular}\\ \end{center} \caption{Illustration of the example in the proof of Lemma \ref{le5}.} \label{fig6} \end{figure} Any Motzkin path $M\in\mathcal{G}$ is characterized by the positions of its pattern $UD$. So, two different Motzkin paths in $\mathcal{G}$ cannot belong to the same class, which completes the proof.\end{proof} \begin{theorem}\label{thm5} The generating function for the set of $UD$-equivalence classes of $\mathcal{M}$ with respect to the length is given by $F(x)=\frac{1}{1 - x - x^2}$, that corresponds to the Fibonacci sequence. \end{theorem} \begin{proof} Using Lemma \ref{le5}, it suffices to provide the generating function $G(x)$ for the set $\mathcal{G}$. Let $M$ be a non-empty Motzkin path in $\mathcal{G}$. It can be written either $M=FQ$ or $M=UDQ$ where $Q\in\mathcal{G}$ which implies that $G(x)=\frac{1}{1-x-x^2}$.\end{proof} \subsection{Modulo $\alpha=UF$} Let $\mathcal{H}$ be the set of Motzkin paths without any patterns $UD$ and $UU$, and such that all patterns $FF$ and $DF$ appear at height zero. For instance, we have $FFUFUFDDF\in\mathcal{H}$ and $UDUFUFDDF\notin\mathcal{H}$. \begin{lemma}\label{le6} There is a bijection between $\mathcal{H}$ and the set of $UF$-equivalence classes of $\mathcal{M}$. \end{lemma} \begin{proof} Let $M$ be a Motzkin path in $\mathcal{M}\backslash\mathcal{H}$. Let us prove that there exists a Motzkin path $M'\in \mathcal{H}$ of the same length as $M$ such that $M$ and $M'$ belong to the same class. Any Motzkin path $M\in\mathcal{M}$ can be uniquely written either $$M=\beta_0 \qquad\mbox{ or } \qquad M=\beta_0\Pi_{i=1}^r(UF)^{k_i}\beta_i,$$ where $r\geq 1$, $k_i\geq 1$ for $1\leq i\leq r$ and $\beta_i$, $0\leq i\leq r$, (non-empty) does not contain any pattern $UF$. If $M=\beta_0$ then we set $M'=F^{s_0}$ where $s_0\geq 0$ is the length of $M$; since an element in $\mathcal{H}$ avoids $UU$ and $UD$, $M'$ is the only one element in $\mathcal{H}$ lying in the class of $M$ (that avoids $UF$). Otherwise, we set $M'=F^{s_0}\Pi_{i=1}^r(UF)^{k_i}\beta'_i$ with $\beta'_i=D^{t_i}F^{s_i-t_i}$ for $1\leq i\leq r$, where $s_i$, $0\leq i\leq r$, is the length of $\beta_i$ and $t_i$, $i\geq 1$, is recursively defined by the equation $$t_i=\min(s_i,\sum_{j=1}^{i}k_j-\sum_{j=1}^{i-1}t_{j}).$$ It is worth noticing that $\sum_{j=1}^ik_j$ (resp., $\sum_{j=1}^{i-1}t_j$) is the number of up steps (resp., down steps) before $\beta'_i$ in $M'$. So, setting $t_i=\min(s_i,\sum_{j=1}^{i}k_j-\sum_{j=1}^{i-1}t_{j})$ means that $\beta'_i$ consists of the maximum possible of down steps, eventually completed with some flat steps at height zero. Then, $M$ and $M'$ belong to the same equivalence class and $M'$ lies in $\mathcal{G}$. For instance, if we have $M=UUUFDFDUFUFFFDUDDD$ then we obtain $M'=FFUFDFFUFUFDDFFFFF$ (see Figure \ref{fig7} for an illustration of this example). Moreover, $M'$ is the unique element in $\mathcal{H}$ in the same class as $M=\beta_0\Pi_{i=1}^r(UF)^{k_i}\beta_i$. Indeed, $\beta_i$, $i\geq 1$, does not contains any pattern $UU$, $UF$ and $UD$ implies that $\beta_i$ does not contain any up steps; $M$ does not contains $FF$ and $DF$ at positive height implies that $\beta_i=D^{k_i}F^{s_i-k_i}$ where $k_i$ is either the length $s_i$ of $\beta_i$ or the difference between the numbers of up steps and down steps before $\beta_i$, that is precisely $\sum_{j=1}^{i}k_j-\sum_{j=1}^{i-1}t_{j}$. Thus, we necessarily have $M=M'$ which completes the proof. \begin{figure}[h] \begin{center} $M=$\begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C)--(\E,\E); \draw[solid,line width=0.4mm,color=cyan] (\E,\E) -- (\G,\G) --(\I,\G); \draw[solid,line width=0.4mm] (\I,\G) -- (\K,\E) -- (\M,\E) --(\O,\C); \draw[solid,line width=0.4mm,color=cyan] (\O,\C) -- (\Q,\E) -- (\S,\E)--(\U,\G)--(\W,\G); \draw[solid,line width=0.4mm] (\W,\G)-- (\Y,\G)--(\ZZ,\G)--(\Za,\E) -- (\Zb,\G)-- (\Zc,\E) -- (\Zd,\C) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular} $\longrightarrow M'=$\begin{tabular}{c}\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[line width=0.3mm,color=red] (\A,\A)--(\C,\C)--(\E,\E)-- (\G,\G) --(\I,\G) -- (\K,\E) -- (\M,\E) --(\O,\C) -- (\Q,\E) -- (\S,\E)--(\U,\G) -- (\W,\G)-- (\Y,\G)--(\ZZ,\G)--(\Za,\E) -- (\Zb,\G)-- (\Zc,\E) -- (\Zd,\C) -- (\Ze, \A); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\A) -- (\E,\A) -- (\G,\C) -- (\I,\C) -- (\K,\A) -- (\M,\A) -- (\O,\A) -- (\Q,\C) -- (\S,\C) -- (\U,\E) -- (\W,\E) --(\Y,\C) -- (\ZZ,\A) --(\Za,\A) -- (\Zb,\A) -- (\Zc,\A) -- (\Zd,\A) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular}\\ \end{center} \caption{Illustration of the example in the proof of Lemma \ref{le6}.} \label{fig7} \end{figure} \end{proof} \begin{theorem}\label{thm6} The generating function for the set of $UF$-equivalence classes of $\mathcal{M}$ with respect to the length is given by $H(x)=\frac{2}{1 - 2x - \sqrt{1-4x^3}}$. \end{theorem} \begin{proof} Using Lemma \ref{le6}, it suffices to provide the generating function $H(x)$ for the set $\mathcal{H}$. Let $M$ be a non-empty Motzkin path in $\mathcal{H}$. It can be written either $M=FQ$ or $M=UQDR$ where $Q$ and $R$ are two Motzkin paths. If we have $M=FQ$, then $M$ belongs to $\mathcal{H}$ if and only if $Q\in \mathcal{H}$. Otherwise, $M=UQDR$ belongs to $\mathcal{H}$ if and only if $R\in \mathcal{H}$ and $Q\in\mathcal{H}$ such that $Q=F\Pi_{i=1}^r (UF)^{k_i}D^{\ell_i}$ for some $k_i$ and $\ell_i$, with $1\leq i\leq r$. Since $Q$ is a Motzkin path of length $n=1+3\sum_{i=1}^r k_i$, this implies that $Q'=\Pi_{i=1}^r U^{k_i}D^{\ell_i}$ is a Dyck path of semilength $\sum_{i=1}^r k_i=\frac{n-1}{3}$. Conversely, any Dyck path can be associated to a Motzkin path of the form of $Q$. So we deduce the functional equation $H(x)=1+xH(x)+x^3C(x^3)H(x)$ where $C(x)=\frac{1-\sqrt{1-4x}}{2x}$ is the generating function for the set $\mathcal{D}$ of Dyck paths, which completes the proof.\end{proof} \subsection{Modulo $\alpha=FU$} Let $\mathcal{I}$ be the set of Motzkin paths starting with a flat step, without any patterns $DU$, $UU$, $FD$ and such that all patterns $FF$ appear at height zero. For instance, we have $FFUFUDFUDD\in\mathcal{I}$ and $FFUFUFDDFUD\notin\mathcal{I}$. \begin{lemma}\label{le7} There is a bijection between $\mathcal{I}$ and the set of $FU$-equivalence classes of $\mathcal{M}$. \end{lemma} \begin{proof} This is a simple adaptation of the proof of Lemma \ref{le6} by replacing $UF$ with $FU$ in the decomposition $M=\beta_0\Pi_{i=1}^r(UF)^{k_i}\beta_i$. So, we do not present this proof here.\end{proof} \begin{theorem}\label{thm7} The generating function for the set of $FU$-equivalence classes of $\mathcal{M}$ with respect to the length is given by $I(x)=\frac{2}{1 - 2x - \sqrt{1-4x^3}}$. \end{theorem} \begin{proof} Using Lemma \ref{le7}, it suffices to provide the generating function $I(x)$ for the set $\mathcal{I}$. Let $M$ be a non-empty Motzkin path in $\mathcal{I}$. It can be uniquely decomposed $M'=F^{s_0}\Pi_{i=1}^r(FU)^{k_i}\beta'_i$ with $\beta'_i=D^{t_i}F^{s_i-t_i}$ for $1\leq i\leq r$, where $s_i$, $0\leq i\leq r$, is the length of $\beta_i$ and $t_i$ is recursively defined by $t_i=\min(s_i,\sum_{j=1}^{i}k_j-\sum_{j=1}^{i-1}t_{j})$. The transformation that consists of replacing all occurrence $FU$ into an occurrence $UF$, induces a one-to-one correspondence between $\mathcal{I}$ and $\mathcal{H}$. Therefore, the generating function $I(x)$ for $\mathcal{I}$ verifies $I(x)=H(x)$. Using Theorem \ref{thm6}, we complete the proof.\end{proof} \subsection{Modulo $\alpha=FF$} Let $M\in\mathcal{M}$ be a Motzkin path. A {\it long flat} in $M$ is a maximal sequence of at least two consecutive flat steps in $M$. An {\it isolate flat step} is a flat step which is not contiguous to another flat step. Let $\mathcal{J}$ be the set of Motzkin paths without any points of ordinate greater than one, without any isolate flat steps, such that two long flats are separated by at most two steps, and at most one step precedes (resp., follows) the first (resp., last) long flat. For instance, there are five Motzkin paths in $\mathcal{J}$ of length $6$: $FFFFFF$, $FFUFFD$, $UFFDFF$, $UFFFFD$ and $FFUDFF$. For $r,s\in\{0,1\}$, we define the set $\mathcal{J}_r^s$ of elements of $\mathcal{J}$ such that the height of the leftmost long flat is $r$ and the height of the rightmost long flat is $s$. Obviously, we have $\mathcal{J}=\cup_{r,s\in\{0,1\}}\mathcal{J}_r^s$. Let $M$ be a Motzkin path without any points of ordinate greater than one. We denote by $|M|$ its length, i.e., the number of the steps in $M$. \medskip \noindent{\bf Fact 1:} There is a unique decomposition of the form $$M=\beta_0\Pi_{i=1}^k (Q_i\beta_i)$$ with $Q_i$ of maximal length in $\mathcal{J}$ for all $1\leq i\leq k$ and where $\beta_i\in\mathcal{M}$, $0\leq i\leq k$, does not contain any long flat, and only $\beta_0$ and $\beta_k$ can possibly be empty. \medskip \noindent{\bf Fact 2:} If $M=\beta_0\Pi_{i=1}^k (Q_i\beta_i)$ is the decomposition obtained in Fact 1, then there exists $M'$ in the same class as $M$ such that $M'=\beta'_0\Pi_{i=1}^k (Q_i\beta'_i)$ with $\beta'_i=F$ if $|\beta_i|=1$, $\beta'_i=(UD)^\frac{|\beta_i|}{2}$ if $|\beta_i|\geq 2$ is even and $\beta'_i=UFD(UD)^\frac{|\beta_i|-3}{2}$ if $|\beta_i|\geq 3$ is odd. In the following, a Motzkin path $\beta'_i$ of the previous form will be called a {\it hinge}. It is worth noticing that any hinge is entirely characterized by its length. \medskip Let $\mathcal{K}$ be the set of Motzkin paths $M=\beta_0\Pi_{i=1}^k (Q_i\beta_i)$ verifying the conditions described in Fact 2, and such that all $Q_i$ starts with $FF$ whenever $\beta_{i-1}$ and $\beta_i$ are non-empty. For instance, the third Motzkin path $UDUDUDFFUFFDUDFFUD$ in Figure \ref{fig9} belongs to $\mathcal{K}$. Its decomposition provides $\beta_0=UDUDUD$, $Q_1=FFUFFD$, $\beta_1=UD$, $Q_2=FF$ and $\beta_2=UD$. \begin{lemma}\label{le8} There is a bijection between $\mathcal{K}$ and the set of $FF$-equivalence classes of $\mathcal{M}$. \end{lemma} \begin{proof} For any Motzkin path in $\mathcal{M}\backslash\mathcal{K}$, the process described in the proof of Lemma \ref{le1} ensures that there is a Motzkin path $M\in \mathcal{A}$ in the same $F$-equivalence class, and thus in the same $FF$-equivalence class. Let $M=\beta_0\Pi_{i=1}^k (Q_i\beta_i)$ be the decomposition described in Fact 2. We define a sequence of Motzkin path $M_0=M,M_1,M_2,\ldots,M_{k-1},M_k=M'$, $k\geq 1$. For any $i$, $1\leq i\leq k$, the Motzkin path $M_i$ is obtained from $M_{i-1}$ by performing the following process. \medskip \noindent (a) If $\beta_{i-1}$ and $\beta_i$ are non-empty and $Q_i=UWD$, then we replace $Q_i$ with $ \bar{W}$ where $\bar{W}$ is obtained from $W$ by exchanging $U$ and $D$, and we replace $\beta_{i-1}$ (resp., $\beta_i$) with a hinge of length $|\beta_{i-1}|+1$ (resp., of length $|\beta_i|+1$); \medskip \noindent (b) If $\beta_{i-1}$ and $\beta_i$ are non-empty and $Q_i=UWF$, then we replace $Q_i$ with $\bar{W} FD$ where $\bar{W}$ is obtained from $W$ by exchanging $U$ and $D$, and we replace $\beta_{i-1}$ (resp., $\beta_i$) with a hinge of length $|\beta_{i-1}|+1$ (resp., of length $|\beta_i|-1$). \medskip By construction, all Motzkin paths $M_0=M,M_1,M_2,\ldots,M_{k-1},M_k=M'$, belong to the same class and $M'$ belongs to $\mathcal{K}$. Moreover, $M'$ is the unique element in $\mathcal{K}$ in the same class as $M$; indeed, let $M=\beta_0\Pi_{i=1}^k (Q_i\beta_i)$ and $M'=\beta'_0\Pi_{i=1}^{k'} (Q'_i\beta'_i)$ two different elements in $\mathcal{K}$ lying in the same class. \medskip -- From the definition of the sets $\mathcal{K}$ and $\mathcal{J}$, it is clear that $k=k'$. \medskip -- If the long steps in $M$ appear in $M'$ with the same height as in $M$, then we necessarily have $Q_i=Q'_i$ for $1\leq i\leq k$. Thus, we deduce $|\beta_i|=|\beta'_i|$ for $i\geq 0$, and with the last remark of Fact 1, $\beta_i=\beta'_i$ for all $i\geq 0$, which is a contradiction with $M\neq M'$. \medskip -- If there is a long flat in $M$ with height $h\in[0,1]$ and such that it appears in $M'$ at height $1-h$. We choose the leftmost long flat with this property. Let $i\geq 1$ be the integer such that this long flat of $M$ appears in $Q_i$. Since any element in $\mathcal{J}$ has at most two steps between two long flats, and at most one step before (resp., after) the first (resp., the last) long flat step, any long flat step of height $h'\in[0,1]$ in $Q_i$ appears at height $1-h'$ in $Q'_i$. Since $Q_i\in\mathcal{J}$, we have either $Q_i=FFWFF$ and $Q'_i=UFF\bar{W}FFD$, or $Q_i=FFWFFD$ and $Q'_i=UFF\bar{W}FF$, or $Q_i=UFFWFF$ and $Q'_i=FF\bar{W}FFD$, or $Q_i=UFFWFFD$ and $Q'_i=FF\bar{W}FF$. \medskip Observing these four cases, $Q_i$ cannot be a prefix nor a suffix of $M$ (otherwise $M'$ could not have the leftmost $FF$ at the same position as $M$). This means that $\beta_{i-1}$ and $\beta_i$ are non-empty. Thus, there is an element among $M$ and $M'$ where there is $i$ such that $Q_i$ whenever the element is $M$, $Q'_i$ whenever the element is $M'$, is contiguous with two non-empty hinges and such that the first long flat is of height zero. We obtain a contradiction with the fact that $M$ and $M'$ belong to $\mathcal{K}$ which completes the proof. \begin{figure}[h] \begin{center} \begin{tabular}{l} \begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C)--(\E,\E)-- (\G,\G) --(\I,\G)--(\K,\E)-- (\M,\C) --(\O,\C) -- (\Q,\C) -- (\S,\E)--(\U,\E) -- (\W,\E)-- (\Y,\G)--(\ZZ,\E)--(\Za,\C) -- (\Zb,\C)-- (\Zc,\C) -- (\Zd,\A) -- (\Ze, \A); \end{tikzpicture} $\stackrel{\mbox{Lemma 1}}{\longrightarrow}$ $M=$\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[line width=0.3mm,color=red] (\A,\A)--(\C,\C)--(\E,\E)-- (\G,\G) --(\I,\G)--(\K,\E)-- (\M,\C) --(\O,\C) -- (\Q,\C) -- (\S,\E)--(\U,\E) -- (\W,\E)-- (\Y,\G)--(\ZZ,\E)--(\Za,\C) -- (\Zb,\C)-- (\Zc,\C) -- (\Zd,\A) -- (\Ze, \A); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C)--(\E,\A)-- (\G,\C) --(\I,\C)--(\K,\A)-- (\M,\C) --(\O,\C) -- (\Q,\C) -- (\S,\A)--(\U,\A) -- (\W,\A)-- (\Y,\C)--(\ZZ,\A)--(\Za,\C) -- (\Zb,\C)-- (\Zc,\C) -- (\Zd,\A) -- (\Ze, \A); \end{tikzpicture} \\ $\stackrel{(b),(a)}{\longrightarrow} \qquad$ $M_2=$\begin{tikzpicture}[scale=0.15] \draw (\A,\A)-- (38,\A); \draw (\A,\E)-- (\Ze,\E); \draw (\A,\C)-- (\Ze,\C); \draw (\A,\G)-- (\Ze,\G); \draw (\A,\I)-- (\Ze,\I); \draw (\A,\K)-- (\Ze,\K); \draw (\A,\M)-- (\Ze,\M); \draw (\A,\A) -- (\A,\O); \draw (\C,\A) -- (\C,\M);\draw (\E,\A) -- (\E,\M);\draw (\G,\A) -- (\G,\M); \draw (\I,\A) -- (\I,\M);\draw (\K,\A) -- (\K,\M);\draw (\M,\A) -- (\M,\M); \draw (\O,\A) -- (\O,\M);\draw (\Q,\A) -- (\Q,\M);\draw (\S,\A) -- (\S,\M); \draw (\U,\A) -- (\U,\M);\draw (\W,\A) -- (\W,\M);\draw (\Y,\A) -- (\Y,\M); \draw (\ZZ,\A) -- (\ZZ,\M); \draw (\Za,\A) -- (\Za,\M); \draw (\Zb,\A) -- (\Zb,\M); \draw (\Zc,\A) -- (\Zc,\M); \draw (\Zd,\A) -- (\Zd,\M); \draw (\Ze,\A) -- (\Ze,\M); \draw[line width=0.3mm,color=red] (\A,\A)--(\C,\C)--(\E,\A)-- (\G,\C) --(\I,\C)--(\K,\A)-- (\M,\C) --(\O,\C) -- (\Q,\C) -- (\S,\A)--(\U,\A) -- (\W,\A)-- (\Y,\C)--(\ZZ,\A)--(\Za,\C) -- (\Zb,\C)-- (\Zc,\C) -- (\Zd,\A) -- (\Ze, \A); \draw[solid,line width=0.4mm] (\A,\A)--(\C,\C)--(\E,\A)-- (\G,\C) --(\I,\A)--(\K,\C)-- (\M,\A) --(\O,\A) -- (\Q,\A) -- (\S,\C)--(\U,\C) -- (\W,\C)-- (\Y,\A)--(\ZZ,\C)--(\Za,\A) -- (\Zb,\A)-- (\Zc,\A) -- (\Zd,\C) -- (\Ze, \A); \end{tikzpicture} \\ \end{tabular} \end{center} \caption{Illustration of the example in the proof of Lemma \ref{le8}.} \label{fig9} \end{figure} For instance, if $M=UFDUDUFFDFFUDUFFDF$ then the decomposition in Fact 2 implies $\beta_0=UFDUD$, $Q_1=UFFDFF$, $\beta_1=UD$, $Q_2=UFFD$ and $\beta_2=F$. For $i=1$, $\beta_0$ and $\beta_1$ are non-empty and $Q_1=UWF$ with $W=FFDF$; the process (b) creates $M_1=UDUDUDFFUFFDFUFFDF$ where $\beta_0$ (resp., $\beta_1$ and $Q_1$) is replaced with $UDUDUD$ (resp., $F$ and $FFUFFD$). For $i=2$, $\beta_1=F$ and $\beta_2=F$ are non-empty and $Q_2=UFFD$; the process (a) creates $M_2=UDUDUDFFUFFDUDFFUD$ where $\beta_1$ (resp., $\beta_2$ and $Q_2$) is replaced with $UD$ (resp., $UD$ and $FF$). See Figure \ref{fig9} for an illustration of this example.\end{proof} \begin{lemma}\label{le9} The generating function for the set $\mathcal{J}$, with respect to the length is given by $J(x)=\frac{x^4-x^2+x-1}{x^7+x^6+2x^4+x-1}$. \end{lemma} \begin{proof} In order to obtain the generating function $J(x)$ for the set $\mathcal{J}$, we calculate the generating functions $J_r^s(x)$ for the set $\mathcal{J}_r^s$ with $r,s\in\{0,1\}$. \medskip -- If $M$ is a Motzkin path in $\mathcal{J}_0^0$. We have either $M=F^k$ or $M=WF^k$ or $M=W'UDF^k$ with $k\geq 2$, $W\in \mathcal{J}_0^1$ and $W'\in \mathcal{J}_0^0$; \medskip -- if $M$ is a Motzkin path in $\mathcal{J}_1^0$. We have either $M=WF^k$ or $M=W'UDF^k$ with $k\geq 2$, $W\in \mathcal{J}_1^1$ and $W'\in \mathcal{J}_1^0$; \medskip -- If $M$ is a Motzkin path in $\mathcal{J}_0^1$. We have either $M=W UF^kD$ or $M=W'UF^kD$ with $k\geq 2$, $W\in \mathcal{J}_0^0$ and $W'\in \mathcal{J}_0^1$; \medskip -- If $M$ is a Motzkin path in $\mathcal{J}_1^1$. We have either $M=UF^kD$ or $M=WUF^kD$ or $M=W'UF^kD$ with $k\geq 2$, $W\in \mathcal{J}_1^0$ and $W'\in \mathcal{J}_1^1$. \medskip We deduce the following system of functional equations: $$\left\{\begin{array}{ll} J_0^0(x)=&\frac{x^2}{1-x}(J_0^1(x)+x^2J_0^0(x)+1)\\ J_1^0(x)=&\frac{x^2}{1-x}(J_1^1(x)+x^2J_1^0(x))\\ J_1^1(x)=&\frac{x^4}{1-x}(J_0^0(x)+J_0^1(x))\\ J_1^0(x)=&\frac{x^4}{1-x}(J_1^0(x)+J_1^1(x)+1).\\ \end{array}\right. $$ A simple calculation (with Maple for instance) provides the generating functions for the four sets $\mathcal{J}_0^0, \mathcal{J}_0^1, \mathcal{J}_1^1$ and $\mathcal{J}_1^0$, and thus for the set $\mathcal{J}=\cup_{r,s\in\{0,1\}}\mathcal{J}_r^s$ which completes the proof.\end{proof} \begin{theorem}\label{thm8} The generating function for the set of $FF$-equivalence classes of $\mathcal{M}$ with respect to the length is given by $$\frac{x(1-x-x^2+3x^3-5x^4+3x^5-2x^6-x^7-x^9)}{(1-x-2x^4-x^6-x^7)(1-2x+x^2-x^3)}.$$ \end{theorem} \begin{proof} With Lemma \ref{le8}, it suffices to obtain the generating function $K(x)$ for the set $\mathcal{K}$. First, we calculate the generating functions for the sets $\mathcal{K}_r$ with $r,s\in\{0,1,2\}$, where $\mathcal{K}_0$ (resp., $\mathcal{K}_1$, resp., $\mathcal{K}_2$) is the subset of $\mathcal{K}$ of Motzkin path starting by $FF$ (resp., $UFF$, resp., a hinge). Let $J_r^s(x)$, $r,s\in\{0,1\}$, be the generating function obtained in the proof of Lemma \ref{le9}. We set $J_1(x)=J_1^0(x)+J_1^1(x)$ and $J_0(x)=J_0^0(x)+J_0^1(x)$. \medskip -- Let $M$ be a Motzkin path in $\mathcal{K}_0$. We discuss on the number of hinges in $M$. \medskip If $M$ does not contains any hinge, then this means that $M\in\mathcal{J}_0$; If $M$ has only one hinge, then either $M=QH_kS$, $k\geq 2$, or $M=QH_kT$, $k\geq 3$, or $M=RH_kS$, $k\geq 1$, or $M=RH_kT$, $k\geq 2$ with $Q\in \mathcal{J}_0^0$, $R\in \mathcal{J}_0^1$, $S\in \mathcal{J}_1^0\cup\mathcal{J}_1^1\cup\{\epsilon\}$, $T\in \mathcal{J}_0^0\cup \mathcal{J}_0^1$ and $H_k$ is a hinge of length at least $k$; If $M$ has at least two hinge, then either $M=QH_kW$, $k\geq 3$, or $M=RH_kW$, $k\geq 2$, with $Q\in \mathcal{J}_0^0$, $R\in \mathcal{J}_0^1$ and $W\in \mathcal{K}_0\backslash \mathcal{J}_0$. Thus we have the functional equation: $$\begin{array}{ll}K_0(x)=&J_0(x)+J_0^0(x)\frac{x^2}{1-x}(J_1(x)+1)+J_0^0(x)\frac{x^3}{1-x}J_0(x)+J_0^1(x)\frac{x}{1-x}(J_1(x)+1)+\\ &J_0^1(x)\frac{x^2}{1-x}J_0(x)+J_0^0(x)\frac{x^3}{1-x}(K_0(x)-J_0(x))+J_0^1(x)\frac{x^2}{1-x}(K_0(x)-J_0(x))\\\end{array}.$$ \medskip -- Let $M$ be a Motzkin path in $\mathcal{K}_1$. We discuss on the number of hinges in $M$. If $M$ does not contain any hinge, then this means that $M\in\mathcal{J}_1$; If $M$ has only one hinge, then either $M=Q'H_kS$, $k\geq 2$, or $M=Q'H_kT$, $k\geq 3$, or $M=R'H_kS$, $k\geq 1$, or $M=R'H_kT$, $k\geq 2$ with $Q'\in \mathcal{J}_1^0$, $R'\in \mathcal{J}_1^1$, $S\in \mathcal{J}_1^0\cup\mathcal{J}_1^1\cup\{\epsilon\}$, $T\in \mathcal{J}_0^0\cup \mathcal{J}_0^1$ and $H_k$ is a hinge of length at least $k$; If $M$ has at least two hinges, then either $M=Q'H_kW$, $k\geq 3$, or $M=R'H_kW$, $k\geq 2$, with $Q'\in \mathcal{J}_1^0$, $R'\in \mathcal{J}_1^1$ and $W\in \mathcal{K}_1\backslash\mathcal{J}_1$. \medskip Thus we have the functional equation: $$\begin{array}{ll}K_1(x)=&J_1(x)+J_1^0(x)\frac{x^2}{1-x}(J_1(x)+1)+J_1^0(x)\frac{x^3}{1-x}J_0(x)+J_1^1(x)\frac{x}{1-x}(J_1(x)+1)+\\ &J_1^1(x)\frac{x^2}{1-x}J_0(x)+J_1^0(x)\frac{x^3}{1-x}(K_0(x)-J_0(x))+J_1^1(x)\frac{x^2}{1-x}(K_0(x)-J_0(x))\\\end{array}.$$ \medskip -- Let $M$ be a Motzkin path in $\mathcal{K}_2$. We have either $M=H_kS$, $k\geq 1$, or $M=H_kT$, $k\geq 2$ with $S\in \mathcal{J}_1^0\cup\mathcal{J}_1^1$, $T\in \mathcal{J}_0^0\cup \mathcal{J}_0^1\cup\{\epsilon\}$ and $H_k$ is a hinge of length at least $k$. \medskip Thus we have the functional equation: $$K_2(x)=J_1(x)\frac{x}{1-x}+(K_0(x)+1)\frac{x^2}{1-x}.$$ Using the Lemma \ref{le9}, a simple calculation with Maple gives the generating function $K(x)=K_0(x)+K_1(x)+K_2(x)$ for the set $\mathcal{K}$. \end{proof} \begin{thebibliography}{10} \bibitem{Bar} J.-L. Baril and A. Petrossian, Equivalence of Dyck paths modulo some statistics, {\it Discrete Math.} {\bf 338} (2015), 655--660. \bibitem{Barc} E. Barcucci, R. Pinzani and R. Sprugnoli, The Motzkin family, {\it Pure Math. Appl. Ser. A} {\bf 2} (1991), 249--279. \bibitem{Bre} C. Brennan and S. Mavhungu, Peaks and valleys in Motzkin paths, {\it Quaest. Math.} {\bf 33} (2010), 171--188. \bibitem{Deu} E. Deutsch, Dyck path enumeration, {\it Discrete Math.} {\bf 204} (1999), 167--202. \bibitem{Don} R. Donaghey and L. W. Shapiro, Motzkin numbers, {\it J. Combin. Theory Ser. A} {\bf 23} (1977), 291--301. \bibitem{Dra} D. Drake and R. Gantner, Generating functions for plateaus in Motzkin paths, {\it J. Chungcheong Math. Society} {\bf 25} (2012), 475--489. \bibitem{Man1} T. Mansour, Statistics on Dyck paths, {\it J. Integer Sequences} {\bf 9} (2006), \href{https://cs.uwaterloo.ca/journals/JIS/VOL9/Mansour/mansour86.html}{Article 06.1.5}. \bibitem{Man2} T. Mansour, Counting peaks at height $k$ in a Dyck path, {\it J. Integer Sequences} {\bf 5} (2002), \href{https://cs.uwaterloo.ca/journals/JIS/VOL5/Mansour/mansour6.html}{Article 02.1.1}. \bibitem{Man3} T. Mansour and M. Shattuck, Counting Dyck paths according to the maximum distance between peaks and valleys, {\it J. Integer Sequences} {\bf 15} (2012), \href{https://cs.uwaterloo.ca/journals/JIS/VOL15/Shattuck/shattuck5.html}{Article 12.1.1}. \bibitem{Man4} T. Mansour, M. Schork and Y. Sun, Motzkin numbers of higher rank: Generating function and explicit expression, {\it J. Integer Sequences} {\bf 10} (2007), \href{https://cs.uwaterloo.ca/journals/JIS/VOL10/Schork/schork3.html}{ Article 07.7.4}. \bibitem{Mer} D. Merlini, R. Sprugnoli and M. C. Verri, Some statistics on Dyck paths, {\it J. Statis. Plann. Inference} {\bf 101} (2002), 211--227. \bibitem{Pan} A. Panayotopoulos and A. Sapounakis, On the prime decomposition of Dyck paths, {\it J. Combin. Math. Combin. Comput.} {\bf 40} (2002), 33--39. \bibitem{Pea} P. Peart and W. J. Woan, Dyck paths with no peaks at height $k$, {\it J. Integer Sequences} {\bf 4} (2001), \href{https://cs.uwaterloo.ca/journals/JIS/VOL4/PEART/pwatjis2.html}{Article 01.1.3}. \bibitem{Pro} H. Prodinger and S. Wagner, Minimal and maximal plateau lengths in Motzkin paths, 2007 Conference on Analysis of Algorithms, {\it Discrete Math. Theor. Comput. Sci. Proc.}, AH (2007), 353--364. \bibitem{Sap} A. Sapounakis, I. Tasoula and P. Tsikouras, Counting strings in Dyck paths, {\it Discrete Math.} {\bf 307} (2007), 2909--2924. \bibitem{Sap1} A. Sapounakis, I. Tasoulas and P. Tsikouras, Some strings in Dyck paths, {\it Australasian J. Combin.} {\bf 39} (2007), 49--72. \bibitem{Sap2} A. Sapounakis and P. Tsikouras, Couting peaks and valleys in $k$-colored Motzkin words, {\it Electron. J. Comb.} {\bf 12} (2005), Article 12. \bibitem{Sloa} N. J. A. Sloane: The On-line Encyclopedia of Integer Sequences, available electronically at \url{http://oeis.org}. \bibitem{Sun} Y. Sun, The statistic ``number of udu's'' in Dyck paths, {\it Discrete Math.} {\bf 287} (2004), 177--186. \bibitem{Sta} R. P. Stanley, {\it Enumerative Combinatorics}, Vol.~2, Cambridge University Press, 1999. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 68R15. \noindent \textit{Key words:} Motzkin path, equivalence relation, statistics. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A001405}, \seqnum{A000079}, \seqnum{A191385}, \seqnum{A132916}, \seqnum{A000045}, \seqnum{A165407}, and \seqnum{A191385}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 12 2015; revised versions received May 20 2015; June 4 2015. Published in {\it Journal of Integer Sequences}, June 16 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}