\documentclass[finalversion]{FPSAC2020-136}
\articlenumber{95}
\addbibresource{abr.bib}

\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{microtype}
\usepackage{footnote}
\usepackage{comment}
\usepackage[english]{babel}  
%\usepackage{cmbright}
\usepackage{enumitem} \setlist[itemize]{noitemsep, topsep=0pt}
%\usepackage{lmodern}
\definecolor{darkgreen}{rgb}{0,0.4,0}
\definecolor{BrickRed}{rgb}{0.65,0.08,0}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{remark}[thm]{Remark}

%
\title[Lattice paths with several forbidden patterns]{Generating functions for lattice paths\\ with several forbidden patterns}
\newcommand{\addorcid}[1]{\protect\includegraphics[height=3mm]{orcid} \url{https://orcid.org/#1}}
\author{Andrei Asinowski\thanks{\url{https://me.aau.at/~anasinowski} \hfill \addorcid{0000-0002-0689-0775}}\addressmark{1},  Cyril Banderier\thanks{\url{https://lipn.fr/~banderier} \hfill \addorcid{0000-0003-0755-3022}}\addressmark{2}, 
 \and Valerie Roitner\thanks{\url{https://dmg.tuwien.ac.at/fb5} \hfill \addorcid{0000-0002-2621-431X}\newline
Andrei Asinowski is supported by the Austrian Science Fund (FWF), 
project \href{https://www.math.aau.at/P28466/}{\textit{Analytic Combinatorics: Digits, Automata and Trees} (P 28466-N35)}.
}\addressmark{3}
}

\address{\addressmark{1} Department of Mathematics, 
University of Klagenfurt, Klagenfurt, Austria\\
\addressmark{2} LIPN, University Sorbonne Paris Nord, Villetaneuse, France\\
\addressmark{3} Institute of Disctere Mathematics and Geometry, 
TU Wien, Vienna, Austria
}	

\received{\today}

\abstract{
This work studies directed lattice paths on $\mathbb{Z}^2$, constrained to avoid a set of given patterns.
We give the corresponding generating functions,
for walks, meanders (walks additionally constrained to be above the $x$-axis), 
and excursions (meanders constrained to end on the $x$-axis).
Our method relies on a vectorial generalization of the classical kernel method,
and on a matricial generalization of the autocorrelation polynomial.
We apply our approach on more than 512 different models, thus unifying/extending many previous works.}
\resumeIL{\textrm{.}gyrs ylwlsmb twrws' twynbt Myrqwx wnxn'w hqyrw.tnybmwq Mybhw' wnxn'}

\keywords{Lattice path, pushdown automaton, forbidden pattern, vectorial kernel method}
\newcommand{\U}{\mathsf{U}}
\renewcommand{\H}{\mathsf{H}} 
\newcommand{\h}{\mathsf{H}}
\newcommand{\D}{\mathsf{D}}
\newcommand{\B}{\mathsf{B}}
\newcommand{\R}{\mathsf{R}}
\newcommand{\UU}{\mathsf{UU}}
\newcommand{\UD}{\mathsf{UD}}
\newcommand{\HH}{\mathsf{HH}}
\newcommand{\bb}{\mathsf{H}_B\mathsf{H}_B}
\newcommand{\rr}{\mathsf{H}_R\mathsf{H}_R}
\newcommand{\DU}{\mathsf{DU}}
\newcommand{\DD}{\mathsf{DD}}
\newcommand{\M}{\vec{\mathbf{M}}}
\newcommand{\ONE}{\vec{\mathbf{1}}} 
\newcommand{\vv}{\vec{\mathbf{v}}} 
\newcommand{\F}{\vec{\mathbf{F}}} 
\newcommand{\WW}{{W}}
\newcommand{\BB}{{B}}
\newcommand{\MM}{{M}}
\newcommand{\EE}{{E}}
\newcommand{\EH}{{E}_{\mathsf{H}}}
\newcommand{\ED}{{E}_{\mathsf{D}}}
\newcommand{\NN}{{N}}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\Q{{\mathbb Q}}
\def\alt{\operatorname{alt}}
\def\C{{\mathcal C}}
\def\W{{\mathcal W}}
\def\SS{{\mathcal S}}
\newcommand{\oeis}[1]{\text{\href{https://oeis.org/#1}{{\small \tt #1}}}}
\def\P{{S}} 
\begin{document}
\maketitle
\section{Definitions and notations}
Let $\SS$, the \textit{set of steps}, be some finite subset of $\mathbb{Z}$
that contains at least one negative and at least one positive number.
A \textit{lattice path with steps from $\SS$} is a 
finite word $w=(s_1, s_2, \ldots, s_n)$ in which all letters belong to $\SS$, 
visualized as a directed polygonal line in the plane, 
which starts at the origin and is formed by successive appending of vectors 
$(1, s_1), (1, s_2), \ldots, (1, s_n)$.
The $n$ letters that form the path $w=(s_1, s_2, \ldots, s_n)$ are referred to as its \textit{steps}. 
The \textit{length} of $w$,
denoted by $|w|$, is the number of steps in $w$.
The \textit{final altitude} of $w$, denoted by $h(w)$, is the sum of all steps in $w$, 
that is $s_1 + s_2 + \ldots + s_n$. Visually, 
$(|w|, h(w))$ is the point where $w$ terminates.
A \textit{pattern} is a fixed word with letters form $\SS$. 
In this article and the companion article~\cite{AsinowskiBanderier20}, we consider lattice paths in which we 
forbid or mark occurrences of \textit{several patterns} seen as factors in the word representation of the paths
(the case of \textit{one pattern} was studied in~\cite{AsinowskiBacherBanderierGittenberger19}).

Under this setting, it is usual to consider two restrictions:
that the whole path is (weakly) above the $x$-axis, 
and that it has final altitude $0$ (equivalently, terminating at the $x$-axis). 
Consequently, one considers four classes of lattice paths:
\begin{enumerate}[topsep=0pt,partopsep=0pt,parsep=0pt,itemsep=0pt,leftmargin=*]
\item A \textit{walk} is any path as described above.
\item A \textit{bridge} is a path that terminates at the $x$-axis.
\item A \textit{meander} is a path that stays (weakly) above the $x$-axis.
\item An \textit{excursion} is a path that stays (weakly) above the $x$-axis
and terminates at the $x$-axis. 
\end{enumerate}
\begin{table*}[ht!]
\addtolength{\belowcaptionskip}{-14pt}
 \small
 \centering
 \renewcommand{\tabcolsep}{1pt}
 \scalebox{0.9}{
 \begin{tabular}{|c|c|c|}
 \hline
 & ending anywhere & ending at 0\\
 \hline &&\\[-1.0em]
\ on~$\Z$ \
 & \begin{tabular}{c} 
 {\includegraphics[width=45mm]{Zche}} 
\\ 
 walks\\ $\displaystyle{W(t,u)=\frac{\Delta(t,u)}{K(t,u)}}$ 
 \end{tabular}
 & \begin{tabular}{c} 
 {\includegraphics[width=45mm]{Zexc}} 
\\
 bridges\\ 
$\displaystyle{
B(t)=
- \sum_{i=1}^e
\frac{u_i'}{u_i}
\frac{\Delta(t,u_i)}{K_t(t,u_i)}
}$
 \end{tabular} \\ &&\\[-1.0em] 
 \hline &&\\[-1.0em]
\ on $\N$ \
 & \begin{tabular}{c} 
\includegraphics[width=45mm]{Nche} 
\\ 
 meanders\\ $\displaystyle{M(t,u)=\frac{\Delta(t,u)}{u^eK(t,u)} \prod_{i=1}^e (u-u_i(t))}$\\ 
 \end{tabular}
 & \begin{tabular}{c} 
 {\includegraphics[width=45mm]{Nexc}} 
\\ 
 excursions\\ $\displaystyle{E(t)=\frac{(-1)^{e+1}}{t} \prod_{i=1}^e u_i(t)}$ \\ 
 \end{tabular}\\
 \hline
 \end{tabular}
 }
 \caption{For  the four types of paths
 and for any set of steps encoded by $\P(u)$, we give the corresponding generating function of such lattice paths
avoiding a set of patterns $p_1,\dots,p_m$.
The formulas involve the $e$ small roots $u_i$ (i.e.~$u_i(t)\sim 0$ for $t\sim 0$) 
of the kernel $K(t,u):= (1- t\P(u)) \Delta + \Delta'$,
where $\Delta$ and $\Delta'$ are determinants related to the mutual correlation matrix of the patterns. (See \cref{thm:W,thm:B,thm:M}) 
}
\label{fig-4types} 
\end{table*}
For each of these classes (when no pattern is forbidden),
Banderier and Flajolet~\cite{BanderierFlajolet02} gave general expressions
for the corresponding generating functions and the asymptotics of their coefficients.
This study was generalized by Asinowski et al.~\cite{AsinowskiBacherBanderierGittenberger19}
to the case where the paths are constrained to avoid one single pattern.
In this article, we further generalize this last work 
to the case where the paths are constrained to avoid several patterns.
While it was expected that the generating functions would be algebraic,
it is a pleasant surprise that they have a nice closed-form, involving some combinatorial determinants, and 
directly generalizing/unifying all our previous results (and the easier cases of the rational world: patterns 
in regular expressions, etc.).
Throughout our article, in the generating functions, 
the variable $t$ encodes the length of paths,
and the variable~$u$ their final altitude.
$\P(u)$ is the \textit{step polynomial} associated to the set of steps $\SS$,
defined by ${\P(u) = \sum_{s\in {\mathcal S}}u^{s}}$.
Without loss of generality, we also assume that none of the forbidden patterns $p_i$
is a substring of another pattern $p_j$.

\section{Generating function for walks with forbidden patterns}\label{sec2}
\begin{thm}\label{thm:W}
The generating function of walks with steps encoded by $\P(u)$ and
avoiding the patterns $p_1, \dots , p_m$ is given by
\begin{equation}\label{eq:Walks}
W(t,u)= \frac{\Delta(t,u)}{(1-t\P(u)) \Delta(t,u) + \sum_{k=1}^m  t^{|p_i|}   u^{\alt(p_i)} \Delta_i(t,u) },
\end{equation}
where $\Delta$ is the determinant of the {\bf mutual correlation matrix}~$C$ defined in~\eqref{CorrelationMatrix},
and $\Delta_i$ is defined in~\eqref{CorrelationMatrix_i}.
\end{thm}
\begin{proof}
Let $\W$ be the set of walks avoiding the patterns $p_1,\dots,p_m$.
Further, let $\W_i$ be the set of all walks that have one occurrence 
of $p_i$ at the end, but no occurrence of $p_i$ before, as well as no occurrence of any of the other patterns $p_j$.  Let $W(t,u)$ and  $W_i(t,u)$ be the corresponding generating functions.
If we append one step from $\mathcal{S}$ to a walk from~$\W$, 
we either obtain another walk in~$\W$, 
or a walk with one single occurrence of 
a (uniquely determined) pattern $p_i$ at the end, 
thus
counted by~$W_i$. In terms of generating functions, this means 
\begin{equation}
\label{eq:W}
1+W(t,u) t\P(u) = W(t,u)+\sum_{j=1}^m  W_j(t,u).
\end{equation}
Now we take a walk $w\in \W$ and append a pattern $p_i$ to it.
Let $q$ be the maximal (possibly empty) suffix of $w.p_i$
such that $w.p_i=w'.p_j.q$, where $w'\in W$ and $p_j$ is one of the forbidden patterns (possibly $p_j=p_i$). Then $q$ is the complement 
(in $p_i$) of an \textit{overlap} of~$p_j$ and~$p_i$, as~shown:
\begin{center}
\includegraphics[scale=0.63]{overlap}
\end{center} 
For each pair $p_i, p_j$, let $\C_{ij}$ be the set\footnote{For example, for the patterns $p_1=aabb$ and $p_2=bba$,
we have $\C_{12}=\{abb\}$ and $\C_{21}=\{a,ba\}$.} of such words $q$.
Associated to these sets $\mathcal{C}_{ij}$, we define the \textit{mutual correlation polynomials}
\begin{center}
$C_{ij}(t,u):=\sum_{q\in\mathcal{C}_{ij}} t^{|q|}u^{\text{alt}(q)}.$
\end{center}
Note that $C_{ii}(t,u)$ is the classical {\em autocorrelation polynomial} of $p_i$, 
as introduced in the case of one single pattern  
by Sch\"utzenberger~\cite{Schuetzenberger64} for prefix codes
and by Guibas and Odlyzko~\cite{GuibasOdlyzko81} in the context of text searching and string overlaps. Equipped with these notations, we have
\begin{align}
\label{eq:Wj}
Wt^{|p_1|} u^{\text{alt}(p_1)}=\sum_{j=1}^m W_j \, C_{1j}, \quad \dots, \quad
Wt^{|p_m|} u^{\text{alt}(p_m)}=\sum_{j=1}^m W_j \, C_{mj}.
\end{align}
A key role is thus played by what we call the (combinatorial) {\em mutual correlation matrix}~$C$,
\begin{equation}\label{CorrelationMatrix}
C:=\begin{pmatrix}
C_{11} & \dots & C_{1m}\\
\vdots & \vdots  & \vdots \\
C_{m1} & \dots  & C_{mm}
\end{pmatrix}.
\end{equation}
By \eqref{eq:W} we have
$W=\frac{1- \sum W_i}{1-tS}$ where
the sum $\sum W_i$ is determined from~\eqref{eq:Wj} by 
Cramer's rule\footnote{
We use the fact: 
If $Cx=d$ and $C^\top y = \ONE$
(where $\ONE$ is the all-$1$'s column vector), 
then $x^\top \ONE = d^\top y$,
and we apply Cramer's rule on the latter system.}: it is equal to
$\frac{W}{\Delta}\big(\sum_{k=1}^m  t^{|p_i|} u^{\alt(p_i)} \Delta_i \big)$,
where $\Delta(t,u):=\det(C)$ and 
\begin{equation}\label{CorrelationMatrix_i}
\Delta_i(t,u):= \det(C \text{ with all the polynomials $\{C_{ij}\}_{j=1,\dots, m}$ replaced by 1}).
\end{equation}
Putting everything together, we obtain 
the formula given in the theorem.
\end{proof}
\begin{remark}
These walks with forbidden patterns can also be encoded by a Markov chain
 or, equivalently, by a finite automaton. To obtain the generating function with those approaches 
 would typically require the inversion of a $\ell\times\ell$ matrix with symbolic coefficients, which is costly in time and in memory
 ($\ell:=\sum_{i=1}^m |p_i|$  is the sum of the lengths of the $m$ forbidden patterns). 
It is nice that the formula based on the mutual correlation sets is algorithmically much more efficient, 
and directly gives the generating function, avoiding those larger costs. 
Note that this formula can also be established via Goulden and Jackson's \textit{cluster method}, 
e.g.~used in~\cite{AsinowskiBacherBanderierGittenberger19,NoonanZeilberger99}. 
\smallskip
In addition to the mutual correlation matrix, an object which plays a fundamental role 
for any lattice path enumeration is the denominator of $W$, which we call the \textit{kernel} of the model:
\begin{equation}\label{eqK}
K(t,u):= \operatorname{denom}(W(t,u))= (1-t\P(u)) \Delta(t,u) + \sum_{k=1}^m  t^{|p_i|}   u^{\alt(p_i)} \Delta_i(t,u).
\end{equation}
It has $e$ distinct simple roots $u_1,\dots,u_e$ satisfying $u_i(z)\sim0$ for $z\sim0$, 
which we call the \textit{small roots} of the kernel.
Similarly to 
classical directed lattice paths, we shall see that 
the generating functions of our pattern constrained lattice paths
are algebraic and expressible in terms of these small roots. 
The following theorem states what it gives for bridges.
\end{remark}
\begin{thm}\label{thm:B}
The generating function for bridges avoiding the patterns $p_1,\dots,p_m$ is
\begin{equation}
B(t)=
- \sum_{i=1}^e
\frac{u_i'}{u_i}
\frac{\Delta(t,u_i)}{K_t(t,u_i)}
\end{equation}
\end{thm}
\begin{proof}
The generating function for bridges is obtained from $W(t,u)$ via a residue computation
\begin{equation*}
B(t) = [u^0] W(t,u) = \frac{1}{2 \pi i } \int_{|u|=\varepsilon} \frac{W(t,u)}{u} \, du =
\sum_i^e \mathrm{Res}_{u=u_i(t)} \frac{W(t,u)}{u}.
\end{equation*}
The residues inside the small circle $|u|=\varepsilon$ are exactly 
the $e$ small roots $u_i(t)$ of $K(t,u)$. This leads to the theorem.
\end{proof}

\section{Generating function for meanders with forbidden patterns}\label{sec3}
\begin{thm}\label{thm:M}
The generating function for meanders avoiding the patterns $p_1,\dots,p_m$ is
\begin{equation}\label{eq:M2}
M(t,u) = \frac{G(t,u)}{u^eK(t,u)} \prod_{i=1}^e(u-u_i(t)),
\end{equation}
where $u_1(t), \ldots, u_e(t)$ are all the small roots of the kernel $K(t,u)$ (defined in Formula~\eqref{eqK}),
and $G(t,u)$ is some formal power series in $t$ and polynomial in $u$ (defined in~\eqref{eq:PHI}).
\end{thm}
\begin{proof}[Proof (sketch).]
Lattice paths with forbidden patterns can be encoded by an automaton: 
its states $X_1, X_2, \ldots$ 
are labelled by prefixes of the patterns 
such that a walk $w$ is in a state labelled $\sigma$
if and only if $\sigma$ is the longest label which is a suffix of $w$.  
(See the illustration in \cref{sec5.2x}).
We denote the transition matrix of this automaton by $A$. 
Moreover we denote by $M_i$ the generating function for meanders that terminate in state $X_i$, and 
let $ \M =(M_1, M_2, \ldots)$.
Then we have 
\begin{equation}\label{eq:M}
 \M  = (1, 0, \ldots) + t \M A - \{u^{<0}\}(t \M A),
\end{equation} 
where $\{u^{<0}\}(t \M A)$ is the generating function for paths obtained from a meander
by adding a step that makes them cross the $x$-axis. 
Such a matricial functional equation can be solved by the 
\textit{vectorial kernel method} developed in~\cite{AsinowskiBacherBanderierGittenberger19}.
First, \eqref{eq:M} is conveniently rewritten as $\M  (I-tA)  = \F$,
and multiplying by $\vv:=\mathrm{adj}(I-tA) \vec{\mathbf{1}}$,
one gets $ \M \det(I-tA)= \F \cdot \vv$. 
Here, it is legitimate to substitute $u$ by any small root $u_i$ of $\det(I-tA)=K(t,u)$, the kernel from the 
previous section\footnote{
Notice that the equation for \textit{walks} similar to~\eqref{eq:M}
reads $\vec{\mathbf{W}}  = (1, 0, \ldots) + t \vec{\mathbf{W}} A$.
We can solve it and compare 
$W(t,u) = \vec{\mathbf{W}} \vec{\mathbf{1}} = (1, 0, \ldots) \mathrm{adj}(I-tA) \vec{\mathbf{1}} / \mathrm{det}(I-tA)$
with~\eqref{eq:Walks}. In both expressions,
the denominator is a polynomial with constant term $1$.
Hence $\mathrm{det}(I-tA)=K(t,u)$ and 
$(1,0,\dots) \mathrm{adj}(I-tA) \vec{\mathbf{1}} = \Delta(t,u)$.}.
The $u_i$'s are therefore also roots of the polynomial $\Phi(t,u) := u^e \F \cdot \vv$;
this yields the following factorisation 
\begin{equation}\label{eq:PHI}
\Phi(t,u) = G(t,u) \prod_{i=1}^e(u-u_i),
\end{equation} 
and leads to Formula~\eqref{eq:M2} for $M(t,u)$. The factor $G(t,u)$ has some case dependent combinatorial interpretations, on which we comment later.
\end{proof} 
If $\Phi(t,u)$ is a monic polynomial of degree $e$, then we have the complete factorisation
$\Phi(t,u) = \prod_{i=1}^e(u-u_i)$ and thus $G(t,u)=1$: 
this yields an explicit formula for $M(t,u)$ in terms of 
$K(t,u)$ and its small roots. It is shown in~\cite[Section~5]{AsinowskiBacherBanderierGittenberger19}
that this happens for some natural cases of a single forbidden pattern.
When one has several patterns, it is generically not the case that $G(t,u)=1$.
In the next sections, we show how, in many cases, 
one can determine a non-trivial ``extra factor'' $G(t,u)$.
We  also show how to obtain the formula for $E(t)$ without computing first $M(t,u)$. 

\subsection{Dyck paths avoiding $\U\D\U$ and $\D\U\D$}\label{sec5.2x}
We illustrate the procedure outlined above 
by the example of Dyck paths avoiding 
$\U\D\U$ and $\D\U\D$. 
These walks are encoded by the following automaton:
\begin{center}
\begin{tabular}{ccc}
\raisebox{-0.5\height}{\includegraphics[scale=0.6]{dyck_UDU_DUD.pdf}}
&
&\scalebox{0.9}{\begin{tabular}{c}
Corresponding adjacency matrix\\
(the states are ordered 
$X_{\epsilon}, X_{\U}, X_{\U\D}, X_{\D}, X_{\D\U}$):\\
$A=\begin{pmatrix}
0 & u & 0 & u^{-1} & 0\\
0 & u & u^{-1} & 0 & 0\\
0 & 0 & 0 & u^{-1} & 0\\
0 & 0 & 0 & u^{-1} & u\\
0 & u & 0 & 0 & 0\\
\end{pmatrix}.$
\end{tabular}}
\end{tabular}
\end{center}
The kernel $K(t,u)=-u^{-1}(tu^2-(1+t^2-t^4)u+t)$ can be calculated directly as 
$\det(I-tA)$, but also by \eqref{eq:W}
with the mutual correlation matrix 
$\Big(\begin{smallmatrix}1+t^2&tu\\t/u&1+t^2\end{smallmatrix}\Big)$.
$K(t,u)$ has a unique small root, 
$u_1(t)=\Big(1+t^2-t^4-\sqrt{(1+t+t^2)(1+t-t^2)(1-t+t^2)(1-t-t^2)}\Big)/(2t)$.
The functional \eqref{eq:M} has the form
\begin{equation*}
(M_1,M_2,M_3,M_4,M_5)(I-tA)=(1,0,0,0,0)-\big(\{u^{<0}\}t(M_1,M_2,M_3,M_4,M_5)A\big).
\end{equation*}
It is easy to see that $\big(\{u^{<0}\}t(M_1,M_2,M_3,M_4,M_5)A\big)
=
\frac{t}{u}(0, 0, 0, E(t), 0)$
because a path $w.a$
(where $w$ is a meander and $a$ a step)
goes below the $x$-axis if and only if $w$
is an excursion and $a$ is a $\D$-step,
and upon making this step the path enters the 4th state~$X_{\D}$. 
Therefore, the needed components of $\vv=\text{adj}(I-tA) \ONE $
are $\vv_1=1+t^2+t^4$ and $\vv_4=1+t^3u$.
Thus, the equation $\Phi(t,u)=0$
has the form 
\begin{equation}\label{eq:PHI_5.2}
(1+t^2+t^4)u - tE(t)(1+t^3u) = 0.
\end{equation}
Solving it for $E(t)$ and keeping in mind that $u=u_1(t)$
is a root of $\Phi(t,u)$, we obtain 
{\small
\begin{equation*}
E(t)=\frac{u_1(t)(1+t^2+t^4)}{t(1+t^3u_1(t))}
=\frac{1+t^2+t^4-\sqrt{(1+t+t^2)(1+t-t^2)(1-t+t^2)(1-t-t^2)}}{2t^2}.
\end{equation*}
}
Finally, $G(t,u)$ is simply the leading coefficient of $\Phi(t,u)$ (as polynomial in $u$),
and we can now find it from~\eqref{eq:PHI_5.2}.
Putting everything together we obtain by \cref{thm:M}
the bivariate generating function for meanders, 
which in its turn gives the univariate generating function 
\[
M(t)=
-
\Bigg(\frac
{1-t^3}
{2t}
-
\frac
{(1+t)\sqrt{(1+t+t^2)(1+t-t^2)(1-t+t^2)(1-t-t^2)}}
{2t(1-t-t^2)}\Bigg).
\]
The enumerating sequence for meanders is the sequence~\oeis{A329703} from the 
On-Line Encyclopedia of Integer Sequences,
and the one for excursions (counted by semilength) is~\oeis{A004148}, 
which also counts
some other constrained paths (like peakless Motzkin paths -- see below), 
but also some classes of RNA structures, ordered trees,  
permutations, etc.; see~\cite{BarilKirgizovPetrossian18,DeutschShapiro02,JinReidys08}.

\section{A multi-multivariate generating function for Motzkin paths with any set of forbidden patterns of length two}\label{sec4}
There is a vast amount of literature on Dyck or Motzkin lattice paths in which 
some combinations of patterns (like valleys or peaks) are considered. These works often rely 
on some ad-hoc context-free grammar decompositions; see e.g.~\cite{BrennanMavhungu12,EuLiuYeh03,MansourShattuck13}.
Here, we show how our approach can extend and unify such results
by directly finding a generating function with many variables.
For example, for Motzkin paths avoiding any combination of forbidden patterns of length~$2$,
one introduces $9$ \textit{markers} -- auxiliary variables $v_p$
that encode occurrences of all possible patterns $p$ of length~$2$
(marker $v_{\U\D}$ for the pattern ${\U\D}$, etc.). 
This leads to the following theorem.
\begin{thm}\label{GF2}
The generating function $E(t)$ of Motzkin excursions,
where $v_p$ counts the number of occurrences of the pattern $p$, is
\begin{equation}\label{eq:ME}
\resizebox{.92\hsize}{!}{$\frac{
(v_{\D\D}-1)
-t
((v_{\D\D}-1)v_{\H\H}-(v_{\D\H}-1) v_{\H\D}-v_{\D\D}+v_{\D\H})
+
\big(
1+t(v_{\D\H}-v_{\H\H})
\big)
\frac{u\vv_1}{t\vv_4} \big|_{u=u_1(t)}}
{v_{\D\D}+t(v_{\D\H}v_{\H\D}-v_{\D\D}v_{\H\H})},$}
\end{equation}
where 
$u_1(t)$ is the unique small solution of $\mathrm{det}(I-tA)=0$ for the matrix $A$
defined below, and $\vv_1$ and $\vv_4$ are the $1$st and the $4$th components of $\vv:=\mathrm{adj}(I-tA)\vec{\mathbf{1}} $.
\end{thm}
\begin{remark}
It is striking that 
all the $v_p$ involving the step $\U$ are hidden in $\vv_1, \vv_4$, and $u_1$.
\end{remark}
\begin{proof}
Such paths are encoded by the following automaton and the corresponding adjacency~matrix:
\begin{center}
\begin{tabular}{ccc}
\raisebox{-0.5\height}{\includegraphics[scale=0.5]{motzkin75.pdf}}
&
&
\scalebox{1.1}{
$A=
\left( \begin {array}{cccc} 
0&u&1&{u}^{-1}\\ 
\noalign{\medskip}
0&v_{\U\U}u&v_{\U\H}& v_{\U\D}{u}^{-1}\\
\noalign{\medskip} 
0&v_{\H\U}u&v_{\H\H}&v_{\H\D}{u}^{-1}\\ 
\noalign{\medskip}
0&v_{\D\U}u&v_{\D\H}&v_{\D\D}{u}^{-1}\end {array} \right)
$}
\end{tabular}
\end{center}
From this matrix we compute $K(t,u)=\det(I-tA)$.
Generically, $uK(t,u)$ is a polynomial of degree $2$ in $u$, 
and has one small root, $u_1(t)$.
Since a path can cross the $x$ axis only by reading $\D$ -- hence, entering the $4$th state, --
only the fourth component of $t\M(t) A$ has terms with negative powers of $u$.
Therefore, one has 
\begin{equation}\label{eq:PHIx}
\Phi(t,u):=\vv_1(t,u) - \vv_4(t,u)  \NN(t,u) =0,
\end{equation}
where $\vv_1(t,u)$ and $\vv_4(t,u)$ are the first and the fourth components of
$\mathrm{adj}(I-tA) \ONE$, 
 and $\NN(t)$ is the generating function for the terms
with negative powers of $u$
in the fourth component of $t\M(t) A$.
In order to use~\eqref{eq:PHIx} for computing $\EE(t)$, 
we find an equation which relates $\NN(t,u)$ to $\EE(t)$.
Let $\EH(t)$ and $\ED(t)$ be the generating functions for excursions whose last step
is $\sf{H}$ resp.~$\sf{D}$. Then we have
$\NN(t,u) = \frac{t}{u} \big(1+v_{\H\D}\EH(t)+v_{\D\D}\ED(t)\big).$
Further we have
$\EE(t) = 1 + \EH(t) + \ED(t)$ 
and 
$\EH(t) = t\big(1 + v_{\H\H} \EH(t) + v_{\D\H} \ED(t)\big)$.
This allows us to express $\NN$ in terms of $\EE$.
Finally, since $u_1$ is a root of
$\Phi$, the substitution of $u=u_1(t)$ into~\eqref{eq:PHIx} 
gives the formula for $\EE(t)$.
\end{proof}
In~\eqref{eq:ME}, setting $v_p=1$ allows the pattern $p$, while setting $v_p=0$ forbids it. 
We ran an exhaustive analysis of all the $2^9=512$ cases; this leads to the $75$ distinct sequences in Table 2.
\vspace{3mm}

\noindent\resizebox{\textwidth}{!}{
\noindent\begin{tabular}{|cccc|cccc|cccc|} \hline
\begin{tabular}{c}Allowed set\\of patterns \end{tabular}&  
\begin{tabular}{c}OEIS\footnotemark\\ entry \end{tabular} &  GF & \begin{tabular}{c}Growth\\ rate \end{tabular}  & \begin{tabular}{c}Allowed set\\ of patterns \end{tabular} &  \begin{tabular}{c}OEIS\\ entry \end{tabular}  &  GF &  \begin{tabular}{c}Growth\\ rate \end{tabular} & \begin{tabular}{c}Allowed set\\ of patterns \end{tabular} &  \begin{tabular}{c}OEIS\\ entry \end{tabular}  &  GF &  \begin{tabular}{c}Growth\\ rate \end{tabular} \\ \hline
000000000 & \oeis{A019590}  & pol & $0$ & 010011100 & \oeis{A020711}$^\dagger$  & rat& $\approx 1.466$  & 101010101 & \oeis{A329696}  & alg& $2$\\ \hline
010001000 & \oeis{A329670}  & pol & $0$ & 010011110 & \oeis{A000930}  & rat& $\approx 1.466$  & 011110101 & \oeis{A329695}$^\dagger$ & alg& $2$\\ \hline
010001010 & \oeis{A329677} & pol & $0$ & 011110001 & \oeis{A020711}$^\dagger$  & rat& $\approx 1.466$  & 101010111 & \oeis{A110199}  & alg& $2$\\ \hline
001000000 & \oeis{A130716}  & pol & $0$ & 001110010 & \oeis{A068921}  & rat& $\approx 1.466$  & 011110011 & \oeis{A216604}$^\dagger$  & alg& $2$\\ \hline
001000010 & \oeis{A329678} & pol & $0$ & 010101101 & \oeis{A329687}  & alg& $\approx 1.587$  & 101110011 & \oeis{A329698} & alg& $2$\\ \hline
011001010 & \oeis{A329679} & pol & $0$ & 011100011 & \oeis{A329688}  & alg& $\approx 1.587$  & 010111011 & \oeis{A023432}$^\dagger$  & alg& $\approx 2.148$ \\ \hline
010001100 & \oeis{A329680}  & rat& $1$  & 010101011 & \oeis{A329689} & alg& $\approx 1.618$  & 011111010 & \oeis{A023432}$^\dagger$  & alg& $\approx 2.148$ \\ \hline
110001001 & \oeis{A135528}  & rat& $1$ & 110011011 & \oeis{A324969}  & rat& $\approx 1.618$  & 101001111 & \oeis{A329699} & alg& $\approx 2.206$ \\ \hline
010001110 & \oeis{A011655}$^\dagger$ & rat& $1$ & 011101010 & \oeis{A320690} & alg& $\approx 1.618$  & 101100111 & \oeis{A329700} & alg& $\approx 2.206$ \\ \hline
001000100 & \oeis{A266591}  & rat& $1$ & 011011100 & \oeis{A001611}$^\dagger$  & rat& $\approx 1.618$  & 110011111 & \oeis{A217282}$^\dagger$ & alg& $\approx 2.241$ \\ \hline
011100001 & \oeis{A329682} & rat& $1$ & 011011110 & \oeis{A000045}$^\dagger$  & rat& $\approx 1.618$  & 101111011 & \oeis{A217282} & alg& $\approx 2.241$ \\ \hline
000010000 & \oeis{A000012} & rat& $1$ & 110001101 & \oeis{A329691} & alg& $\approx 1.755$  & 110101111 & \oeis{A329676} & alg& $\approx 2.247$\\ \hline
001100010 & \oeis{A100063} & rat& $1$ & 011100101 & \oeis{A329692} & alg& $\approx 1.755$  & 011101111 & \oeis{A329666} & alg& $\approx 2.247$ \\ \hline
010011000 & \oeis{A329683} & rat& $1$ & 101100011 & \oeis{A329693} & alg& $\approx 1.755$  & 010111111 & \oeis{A023431}  & alg& $\approx 2.315$ \\ \hline
110011001 & \oeis{A065033} & rat& $1$ & 010101111 & \oeis{A248100}  & alg& $\approx 1.835$  & 011111011 & \oeis{A023431}$^\dagger$  & alg& $\approx 2.315$ \\ \hline
010011010 & \oeis{A000027}$^\dagger$ & rat& $1$  & 011101011 & \oeis{A329694} & alg& $\approx 1.835$  & 101011111 & \oeis{A329701} & alg& $\approx 2.325$ \\ \hline
001010000 & \oeis{A329684} & rat& $1$ & 110001111 & \oeis{A025250}$^\dagger$  & alg& $\approx 1.947$  & 101110111 & \oeis{A329702} & alg& $\approx 2.325$ \\ \hline
001010100 & \oeis{A040001}  & rat& $1$ & 011100111 & \oeis{A166289}  & alg& $\approx 1.947$  & 101101111 & \oeis{A007477}  & alg& $\approx 2.383$ \\ \hline
001010011 & \oeis{A046698}$^\dagger$ & rat& $1$ & 110101011 & \oeis{A329664} & alg& $2$ & 110111011 & \oeis{A004149}$^\dagger$  & alg& $\approx 2.414$ \\ \hline
001010110 & \oeis{A008619}  & rat& $1$  & 101000101 & \oeis{A126120}$^\dagger$  & alg& $2$ & 011111110 & \oeis{A004149}$^\dagger$  & alg& $\approx 2.414$ \\ \hline
011011010 & \oeis{A028310} & rat& $1$  & 101000111 & \oeis{A208355}$^\dagger$  & alg& $2$ & 101111111 & \oeis{A090344}  & alg& $\approx 2.562$ \\ \hline
110001011 & \oeis{A000931}$^\dagger$  & rat& $\approx 1.325$  & 110011101 & \oeis{A329695} & alg& $2$ & 110111111 & \oeis{A004148}  & alg& $\approx 2.618$ \\ \hline
011001100 & \oeis{A000931}$^\dagger$  & rat& $\approx 1.325$  & 010111101 & \oeis{A216604} & alg& $2$ & 011111111 & \oeis{A004148}$^\dagger$  & alg& $\approx 2.618$ \\ \hline
001100110 & \oeis{A000931}$^\dagger$  & rat& $\approx 1.325$  & 010111010 & \oeis{A023426}$^\dagger$  & alg& $2$ & 111101111 & \oeis{A104545}  & alg& $\approx 2.732$ \\ \hline
010101010 & \oeis{A329686}  & alg& $\approx 1.414$  & 011101110 & \oeis{A329671} & alg& $2$ & 111111111 & \oeis{A001006}  & alg& $3$\\ \hline
\end{tabular}
}
\begin{center}\begin{minipage}{.8\textwidth}
\begingroup 
\footnotesize
{\bf Table 2:} Motzkin excursions avoiding a set of patterns of length 2.
Allowed sets of patterns are here indicated via a binary word of length 9,
whose bits correspond to the allowance (or not) of $\U\U$, $\U\H$, $\U\D$, $\H\U$, $\H\H$, $\H\D$, $\D\U$, $\D\H$, $\D\D$
(in this order). The column GF indicates whether the generating function is 
polynomial (pol), rational 
(rat), or algebraic 
(alg).
\endgroup
\end{minipage}
\end{center}
\footnotetext{All the sequences labelled A329xxx are entries that we added to the On-Line Encyclopedia of Integer Sequences (OEIS), 
available at \href{https://oeis.org/}{https://oeis.org/}.The sequences marked by {$^\dagger$} are in the OEIS, but with a few terms of offset.\label{footnote4}}

Our exhaustive analysis also shows that the 512 cases
lead to 158 distinct sequences for meanders. 
We give more details 
at the address \url{https://lipn.fr/~cb/KernelMethod}.
Note the same list for all set of patterns of length 5 
would have more entries than the estimated number of atoms in the galaxy!

Via our approach, 
it is thus not difficult to get the explicit formulas for $E(t)$ and $M(t)$.
These generating functions with all the markers $v_p$ are however quite lengthy.
So, we now give these explicit formulas when the set of patterns is included in $\{\UU, \HH, \DD\}$ or in $\{\UD, \HH, \DU\}$. 

\begin{savenotes} \hspace{-2mm} 
\def\alphaa{A_{\U\U,\H\H}}
\begin{center}
\resizebox{.99\textwidth}{!}{
\setlength\tabcolsep{3pt}
\begin{tabular}{|c|c|c|c|} 
\hline
\begin{tabular}{c}Forbidden \\ patterns \end{tabular}& Generating functions of meanders and excursions & OEIS\footnote{See footnote~\ref{footnote4} on previous page for the $^\dagger$ symbol. Also, the sequences marked by~$^*$ are bisections of \oeis{A088518}
that enumerates ``symmetric secondary structures of RNA molecules with $n$ nucleotides'';  see~\cite{JinReidys08}.}
& Growth rate
\footnote{The notation $\rho(P)$  used for some growth rates stands for the largest positive root of the polynomial $P$.}
\\
\hline \hline $\UU, \HH, \DD$  & 
$\begin{array}{c}
\MM=-(1+t)\Big((1+t)(1-2t)-\sqrt{1-2t+t^2-4t^3+4t^4}\Big)/\big(2t^2(1-2t)\big)\\
\EE=(1+t)\Big(1-t^2-2t^3-(1+t)\sqrt{1-2t+t^2-4t^3+4t^4}\Big)/(2t^4)\end{array}$
& \begin{tabular}{c}\oeis{A329665} \\ \oeis{A329671} \end{tabular} 
& $2$ \\
\hline $\UU, \HH$ & 
$\begin{array}{c}
{\MM=- (1+t)\Big(1-3t^2-t^3-\sqrt{1-2t^2-6t^3-3t^4+2t^5+t^6}\Big)/\big(2t^2(1-2t-t^2)\big)}\\
{\EE= \Big(1-t^2-t^3-\sqrt{1-2t^2-6t^3-3t^4+2t^5+t^6}\Big) /(2t^3).}\end{array}$
& \begin{tabular}{c} \oeis{A329667} \\ \oeis{A329666} \end{tabular}
& \begin{tabular}{c} $\alphaa:=$   \\ $\rho(1-t-2 t^2+t^3)$ \end{tabular} 
\\
\hline $\UU, \DD$  & 
$\begin{array}{c}
{\MM=- \Big((1+t)(1-2t-t^2)-\sqrt{1-2t-t^2-t^4+2t^5+t^6}\Big) /\big(2t^2(1-2t-t^2)\big)}\\
{\EE=\Big( 1-t-t^2-t^3-\sqrt{1-2t-t^2-t^4+2t^5+t^6}\Big) /(2t^4)}\end{array}$
& \begin{tabular}{c} \oeis{A308435} \\ \oeis{A004149}$^\dagger$  \end{tabular}
& $1+\sqrt{2}$\\
\hline $\HH, \DD$  &
$\begin{array}{c}
{\MM=-
\Big( 1-2t-3t^2-t^3-\sqrt{1-2t^2-6t^3-3t^4+2t^5+t^6} \Big) /\big( 2t(1+t)(1-2t-t^2) \big)}\\
{\EE=\Big( 1-t^2-t^3-\sqrt{1-2t^2-6t^3-3t^4+2t^5+t^6} \Big) /(2t^3)}\end{array}$
& \begin{tabular}{c} \oeis{A329669} \\ \oeis{A329666} \end{tabular}
&  $\begin{array}{c} 1+\sqrt{2} \\ \alphaa   \end{array}$  \\
\hline $\UU$  &
$\begin{array}{c}
{\MM= -(1+t)\Big(1-t-3t^2-\sqrt{1-2t-t^2-2t^3+t^4}\Big) / \big(2t^2(1-2t-2t^2)\big)}\\
{\EE=\Big(1-t-t^2-\sqrt{1-2t-t^2-2t^3+t^4}\Big) /(2t^3)}\end{array}$
&\begin{tabular}{c} \oeis{A329672} \\ \oeis{A004148}$^\dagger$ \end{tabular}
& $(3+\sqrt{5})/2$ \\
\hline $\HH$ &
$\begin{array}{c}
{\MM=-\Big(1-2t-2t^2-\sqrt{1-4t^2-8t^3-4t^4}\Big) /\big(2t(1-2t-2t^2)\big)}\\
{\EE=\Big(1-\sqrt{1-4t^2-8t^3-4t^4}\Big) /\big(2t^2(1+t)\big)}\end{array}$
&\begin{tabular}{c} \oeis{A329673} \\ \oeis{A104545}  \end{tabular}
& $1+\sqrt{3}$  \\ 
\hline $\DD$ &
$\begin{array}{c}
{\MM=-\Big( 1-3t-t^2-\sqrt{1-2t-t^2-2t^3+t^4}\Big) /\big( 2t(1-2t-2t^2) \big)}\\
{\EE= \Big(1-t-t^2-\sqrt{1-2t-t^2-2t^3+t^4}\Big) /(2t^3)}\end{array}$
& \begin{tabular}{c} \oeis{A329674} \\ \oeis{A004148}$^\dagger$  \end{tabular}
& $\begin{array}{c} 1+\sqrt{3} \\  (3+\sqrt{5})/2 \end{array}$ \\
\hline $\UD, \HH, \DU$  & 
$\begin{array}{c}\MM=- (1+t) \Big((1+t)(1-2t) - \sqrt{1-2t+t^2-4t^3+4t^4} \Big) /\big( 2t^2(1-2t) \big) \\
\EE={(1+t)\Big(1-t-\sqrt{1-2t+t^2-4t^3+4t^4}\Big)} /(2t^3)
\end{array}$
&\begin{tabular}{c}\oeis{A329665} \\ \oeis{A329664} \end{tabular}
& $2$ \\
\hline $\UD, \HH$ & 
$\begin{array}{c}
\MM=- \Big(1-2t-t^2+t^3-\sqrt{1-2t^2-6t^3-3t^4+2t^5+t^6}\Big) / \big(2t(1-2t-t^2+t^3)\big) \\
\EE= \Big(1+t^2+t^3-\sqrt{1-2t^2-6t^3-3t^4+2t^5+t^6}\Big) / \big(2t^2(1+t)\big) \end{array}$
& \begin{tabular}{c}\oeis{A329675} \\ \oeis{A329676} \end{tabular}
& $\alphaa$ \\ 
\hline $\UD, \DU$  & 
$\begin{array}{c}
{\MM=-\Big((1+t)(1-2t-t^2)-\sqrt{1-2t-t^2-t^4+2t^5+t^6}\Big) / \big(2t^2(1-2t-t^2)\big)}\\
{\EE=\Big( 1-t-t^2-t^3-\sqrt{1-2t-t^2-t^4+2t^5+t^6}\Big) / (2t^4)}\end{array}$
& 
\begin{tabular}{c}\oeis{A308435} \\ \oeis{A004149}$^\dagger$  \end{tabular}
& $1+\sqrt{2}$ \\ 
\hline $\HH, \DU$  &
$\begin{array}{c}
\MM= -(1+t)\Big( 1-t-3t^2+t^4 - (1-t)\sqrt{1-2t^2-6t^3-3t^4+2t^5+t^6}  \Big) / \big(2t^2(1-2t-t^2+t^3)\big)\\
\EE=\Big(1-t^2-t^3-\sqrt{1-2t^2-6t^3-3t^4+2t^5+t^6}\Big) /(2t^3) \end{array}$
&\begin{tabular}{c} \oeis{A329668} \\ \oeis{A329666}\end{tabular}
&  $\alphaa$
\\
\hline $\UD$ &
$\begin{array}{c}
\MM=-\Big(1-3t+t^2-\sqrt{1-2t-t^2-2t^3+t^4}\Big) /\big(2t(1-3t+t^2)\big)\\
\EE=\Big(1-t+t^2-\sqrt{1-2t-t^2-2t^3+t^4}\Big) /(2t^2)
\end{array}$
& \begin{tabular}{c}\oeis{A088518}$^*$ \\ \oeis{A004148}$^\dagger$\end{tabular}
& $(3+\sqrt{5})/2$
\\
\hline $\DU$  &
$\begin{array}{c}
\MM=-\Big((1+t)(1-3t+t^2)-(1-t)\sqrt{1-2t-t^2-2t^3+t^4}\Big) /\big(2t^2(1-3t+t^2)\big)\\
\EE=\Big(1-t-t^2-\sqrt{1-2t-t^2-2t^3+t^4}\Big) /(2t^3)
\end{array}$
&\begin{tabular}{c}\oeis{A088518}$^*$ \\ \oeis{A004148}$^\dagger$\end{tabular}
& $(3+\sqrt{5})/2$ \\
\hline none & 
$\begin{array}{c}
{\MM=-\Big(1-3t-\sqrt{1-2t-3t^2}\Big) /\big(2t(1-3t)\big)}\\
{\EE=\Big(1-t-\sqrt{1-2t-3t^2}\Big) /(2t^2).}\end{array}$
& \begin{tabular}{c}\oeis{A005773}$^\dagger$ \\ \oeis{A001006} \end{tabular}
&  $3$ \\
\hline
\end{tabular}
} 
\end{center}
\end{savenotes}
The asymptotics of these sequences is $\frac{C}{\sqrt \pi} A^n n^\alpha$, 
where the constant $C$ and the growth rate~$A$ are algebraic numbers which depend on the model.

As explained in~\cite{AsinowskiBacherBanderierGittenberger19,BanderierDrmota15,BanderierFlajolet02}, the exponent $\alpha$ is universal: 
\begin{itemize}[leftmargin=*]
\item $\alpha=-3/2$ for meanders with negative drift  (above, when $\{\U\U, \H\H\}$ or $\{\U\U\}$ are forbidden)
 and for excursions,
\item $\alpha=0$ for meanders with positive drift  (above, when $\{\H\H, \D\D\}$   or   $\{\D\D\}$ are forbidden),
\item $\alpha=-1/2$ for meanders with zero drift. 
\end{itemize}
\noindent  The \textit{drift} is the quantity 
\begin{equation*} 
\delta:= \lim_{n\to \infty} \frac{\text{average final altitude of walks on $\Z$ of length $n$}}{n}\,.
\end{equation*}
Unlike in the article~\cite{BanderierFlajolet02}, it is no more the case that $\delta=S'(1)$:
there is a more subtle interplay between the forbidden patterns and the allowed steps $\SS$.
In the long version of our article, we comment more on the link between the drift 
and a weighted variant of the stationary distribution of the automaton~$A$.
\smallskip
Another interesting feature of the above tables is 
that they suggest there could be natural bijections between different classes of pattern-avoiding Motzkin paths. 
Some of them are easily seen (for example by mirroring paths), others are less 
trivial -- for example, bijections between $\UU$-avoiding, $\DU$-avoiding, and (with a shift) $\UD$-avoiding Motzkin excursions. 
We end this section by mentioning some models involving some patterns of length 3, 
some appear to be in bijection with some of the previous models.  
For example, the automaton of Motzkin paths avoiding $\U\D$ and $\U\H\D$ is
\begin{center}
\begin{tabular}{ccc}
\raisebox{-0.5\height}{\includegraphics[scale=0.6]{motzkin_UD_UHD.pdf}}
&
&
\begin{tabular}{c}
Corresponding adjacency matrix:\\
\qquad\\
\scalebox{1.1}{
$A=\begin{pmatrix}
1+u^{-1} & u & 0\\
0 & u & 1\\
1 & u & 0
\end{pmatrix}.$}
\end{tabular}
\end{tabular}
\end{center}
Our vectorial kernel method then leads to the fact that the meanders are counted 
by the ``generalized Catalan numbers'' \oeis{A004149}, defined by 
\begin{equation*}
a(n+1) = a(n) + \sum_{k=2}^{n-1} a(k)a(n-1-k),  \qquad a(0)=1.
\end{equation*}
It is noteworthy that it also counts
\begin{itemize}
\item Motzkin excursions of length $n-1$ avoiding peaks ($\U\D$) and valleys ($\D\U$),
\item Motzkin excursions of length $n-2$ avoiding $\U\U$ and $\U\H\U$.
\end{itemize}
We leave to the reader the pleasure to find bijective proofs of these facts!\footnote{See the PhD thesis (in preparation) of the third author for several possible bijections.}

\section{Beyond rational and algebraic cases}
In~\cite{BacherBerniniFerrariGunbyPinzaniWest14},
the authors introduced a notion of patterns in lattice paths 
similar to the one frequently used for forbidden patterns in permutations: 
one forbids a sequence of letters which are not necessarily contiguous.
Such a notion is in fact also accessible with our pushdown automaton approach:
to forbid a noncontiguous pattern $\U\D$ is equivalent 
to avoid the regular expression $\U \SS^* \D$.
This is achieved by first constructing
the automaton for the (contiguous) pattern $\U\D$,
and then adding a transition labelled by each step from $\SS$ to the state $X_\U$.
This automaton is then easily determinized (to avoid any ambiguity in the transitions),
and our vectorial kernel method then handles the additional 
positivity constraints (meanders, excursions, etc.).
Note that it is a priori not possible to generate (or to forbid) 
via a finite automaton a pattern which would require 
the memory of a counter (for example $\U^n \H^n \D^n$). 
However, we can enumerate such paths by first getting the generating function 
associated to $\U^i \H^j \D^k$-avoiding paths, and then by taking the diagonal $i=j=k$,
at the level of the algebraic generating function (this leads to a D-finite generating function).
The same idea allows us to enumerate paths 
avoiding an infinite set of noncontiguous patterns like e.g.~$\{\U^k\D^k  \U \D\}_{k\in \N}$. 
We present more examples of this type in the long version of our article.
\section{Conclusion and further works}
To summarize, in this article we introduced/presented the following:
\begin{itemize}[leftmargin=*]
\item the mutual correlation matrix, an extension of the notion of autocorrelation polynomial, which has its own interest
and which offers several algorithmic advantages,
\item closed-forms for all the main generating function of constrained  lattice paths (\cref{sec2,sec3}),
 generalizing the previous works~\cite{AsinowskiBacherBanderierGittenberger19,BanderierFlajolet02},
\item new ways to apply the vectorial kernel method, bypassing the obstacle of the determination of the prefactor~$G$ from \eqref{eq:PHI},
\item new sources for enriched bijections between different types of paths, and the classification of more than 512 models (\cref{sec4}).
\end{itemize}
This will allow us to tackle further questions, such as:
\begin{itemize}[leftmargin=*]
\item faster uniform random generation of constrained paths of length $n$ 
(Note that the detailed analysis of the  Boltzmann method done in~\cite{BodiniPonty10} 
is not holding here, because paths with forbidden patterns do not have generically a strongly connected grammar.), 
\item to mix the analysis of patterns with some additional parameters (like the area below the path~\cite{BanderierGittenberger06})
or under further constraints (like to be below a line of rational slope), 
\item the asymptotics and the Gaussian limit law for the number of occurrences of the patterns 
(another instance of Borges's theorem, see~\cite{AsinowskiBacherBanderierGittenberger19,AsinowskiBanderier20,BertoniChoffrutGoldwurmLonati03}).
\end{itemize}

\clearpage \linespread{1.03}
\printbibliography
\end{document}
