\documentclass[11pt]{amsart}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{amssymb,latexsym,cite,longtable,url,array,booktabs}
%\usepackage[linguistics]{forest}
\usepackage{multicol}
\usepackage{arydshln,pstricks}
\newcolumntype{L}{>{\raggedright\arraybackslash}p{5cm}}
\newcolumntype{R}{>{\raggedright\arraybackslash}p{8cm}}
\newcolumntype{T}{>{\raggedright\arraybackslash}p{8cm}}
%\usepackage{auto-pst-pdf}

\setlength{\unitlength}{1mm} \topmargin 0 pt \textheight 46\baselineskip
\advance\textheight by \topskip \setlength{\parindent}{0pt} \setlength{\parskip}{3pt plus
2pt minus 1pt} \setlength{\textwidth}{155mm} \setlength{\oddsidemargin}{5.6mm}
\setlength{\evensidemargin}{5.6mm} \numberwithin{equation}{section}


\usepackage{amsmath,amsthm}
\usepackage{amssymb}
\usepackage{color}
\usepackage{xspace}
% load hyperref last
%\usepackage[colorlinks=true,
%linkcolor=green,
%filecolor=brown,
%citecolor=green]{hyperref}
\def\red{\textcolor{red} }
\def\blue{\textcolor{blue} }
\def\v{\vert}
\def\as{\textrm{asc}}
%\def\a{\ensuremath{\mathcal A}\xspace}
\def\a{A}
\def\b{\ensuremath{\mathcal B}\xspace}
\def\c{\ensuremath{\mathcal C}\xspace}
\def\f{\ensuremath{\mathcal F}\xspace}
%\def\s{\ensuremath{\mathcal S}\xspace}
\def\gf{generating function\xspace}

\def\mbf#1{\mathchoice{\hbox{\boldmath $\displaystyle #1$}}
        {\hbox{\boldmath $\textstyle #1$}}
        {\hbox{\boldmath $\scriptstyle #1$}}
        {\hbox{\boldmath $\scriptscriptstyle #1$}}} % mathboldface


\renewcommand{\baselinestretch}{1.2}

\newtheorem{theorem}{Theorem}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}

\begin{document}
\title{Ascent sequences avoiding a triple of 3-letter patterns and Fibonacci numbers}
\author{David Callan}
\address{Department of Statistics, University of Wisconsin, Madison, USA}
\email{callan@stat.wisc.edu}
\author{Toufik Mansour}
\address{Department of Mathematics, University of Haifa, 3498838 Haifa, Israel}
\email{tmansour@univ.haifa.ac.il}

\begin{abstract} We consider the triples $\tau$ of three letter patterns for which ascent sequences that avoid $\tau$ are counted by Fibonacci-related numbers. Several cases are equivalent to avoiding a pair of $3$-letter patterns and have already been treated using generating functions. Here we give direct proofs of all our results. We also consider avoiders for some quadruples of 3-letter patterns.
\end{abstract}
\subjclass[2010]{05A05, 05A15}
\keywords{Ascent sequences; Fibonacci numbers}
\maketitle
\section{Introduction}
An {\it ascent} in an integer sequence $s_1s_2\cdots s_m$ is an index $1\leq j\leq m-1$ such that $s_j<s_{j+1}$. An {\it ascent sequence} $a_1a_2\cdots a_n$ is one consisting of
non-negative integers satisfying $a_1=0$ and for all $i$ with $1<i\leq n$,
$a_i\leq \as(a_1a_2\cdots a_{i-1})+1$,
where $\as(a_1a_2\cdots a_k)$ is the number of ascents in the sequence $a_1a_2\cdots a_k$. For example, the sequence $0101312501$ is an ascent sequence, whereas $01003$ is not. Bousquet-M\`{e}lou, Claesson, Dukes, and Kitaev \cite{M1} connected ascent sequences to $(2 + 2)$-free posets. Since then, ascent sequences have been studied in a series of papers where connections to many other combinatorial structures have been created (see, for example, \cite{DMS,D1,D2,K2,MS1,MS2} as well as \cite[Section 3.2.2]{K1}).

Let $a =a_1a_2\cdots a_n$ be an ascent sequence and $\tau=\tau_1\cdots\tau_m$ be any {\it pattern}, that is, a word in $\{0,\ldots,\ell\}^m$ which contains each letter $0,1,\ldots,\ell$. We say that $a$ contains $\tau$ if $a$ has a subsequence that is order isomorphic to $\tau$, that is, there is a subsequence $a_{f(1)},a_{f(2)},\ldots,a_{f(m)}$, where $1\leq f(1) < f(2) <\cdots < f(m)\leq n$, such that $a_{f(i)}Xa_{f(j)}$ if and only if $\tau_iX\tau_j$, for all $X\in\{<,>,=\}$ and $1\leq i, j\leq m$. Otherwise, $a$ is said to avoid $\tau$. For instance, the ascent sequence $01013042251$ has two occurrences of the pattern $110$, namely, the subsequences $110$ and $221$, but avoids the pattern $3210$. We denote the set of all ascent sequences that avoid a list of patterns $\tau^{(1)},\ldots,\tau^{(s)}$ by $A_n(\tau^{(1)},\ldots,\tau^{(s)})$ or $A_n(\{\tau^{(1)},\ldots,\tau^{(s)}\})$.

Mansour and Shattuck \cite{MS2} determined all pairs of patterns $\{\tau_1,\tau_2\}$ giving rise to Fibonacci numbers where $\tau_1$ and $\tau_2$ are both length-3 patterns or one is length-3 and the other is length-4. In particular, they showed that
$$\begin{array}{l}
\v A_n(000, 001)\v = \v A_n(000, 010)\v =F_{n+1},\\[4pt]
\v A_n(021, 101)\v =\v A_n(101, 102)\v =\v A_n(021, 120)\v =\v A_n(101, 110)\v=\v A_n(021, 0101)\v\\
=\v A_n(021, 0120)\v =\v A_n(021, 0122)\v =\v A_n(100, 0121)\v=\v A_n(101, 0011)\v =\v A_n(101, 0102)\v\\
=\v A_n(101, 0110)\v=\v A_n(101, 0121)\v=\v A_n(102, 0001)\v=\v A_n(102, 0012)\v =\v A_n(102, 0101)\v\\
=\v A_n(110, 0101)\v=\v A_n(110, 0122)\v =\v A_n(120, 0123)\v =F_{2n-1},
\end{array}$$
where $F_n$ denotes the $n$-th Fibonacci number defined by $F_n = F_{n-1} +F_{n-2}$ if $n\geq2$, with
$F_0 = 0$ and $F_1 = 1$ (sequence A000045 in \cite{Sl}).

The aim of this paper is to determine all pattern avoidance classes of ascent sequences avoiding a triple of length-3 patterns whose counting sequences are closely related to Fibonacci numbers. More precisely, we show the following result.

\begin{theorem}\label{thm1}
$($1$\,)$ Let
\begin{center}
\begin{tabular}{cccc}
$f_1=\{000,001,100\}$,&$f_2=\{000,001,101\}$,&
$f_3=\{000,001,102\}$,&$f_4=\{000,001,201\}$,\\
$f_5=\{000,010,021\}$,&$f_6=\{000,010,100\}$,&
$f_7=\{000,010,101\}$,&$f_8=\{000,010,102\}$,\\
$f_9=\{000,010,110\}$,&$f_{10}=\{000,010,120\}$,&
$f_{11}=\{000,010,201\}$,&$f_{12}=\{000,010,210\}$\,.
\end{tabular}
\end{center}
Then $\v A_n(f_j)\v =F_{n+1}$ for all $j=1,2,\ldots,12$.

$($2$\,)$ Let
\begin{center}
\begin{tabular}{ccc}
$g_1=\{001,100,101\}$,&$g_2=\{001,100,102\}$,& $g_3=\{001,100,201\}$.
\end{tabular}
\end{center}
Then, $\v A_n(g_j)\v=F_{n+2}-1$ for all $j=1,2,3$.

$($3$\,)$ Let
\begin{center}
\begin{tabular}{cccc}
$h_1=\{021,101,201\}$,&$h_2=\{021,101,210\}$,&$h_3=\{021,120,201\}$,& $h_4=\{021,120,210\}$,\\
$h_5=\{100,101,210\}$,&$h_6=\{101,102,201\}$,&$h_7 = \{101,110,201\}$,&$h_8 = \{101,110,210\}$.
\end{tabular}
\end{center}
They $\v A_n(h_j)\v=F_{2n-1}$, for all $j=1,2,\ldots,8$.

$($4$\,)$ Let $i_1=\{000,021,101\}$ and $i_2=\{000,021,110\}$. Then
$$\v A_n(i_1)=\v A_n(i_2)\v= F_n+\sum_{k=2}^nF_{k-1}F_{n-k+1}.$$
\end{theorem}
Additionally, in the last section, we extend our results to some quadruples of 3-letter patterns.

\section{Proof of Theorem \ref{thm1}}
\subsection{Proof of Theorem \ref{thm1} part (1)}\label{part1}

\subsubsection{$f_1$ thru $f_4$} \label{f1}
Ascent sequences avoiding the pair (000,001) were counted in \cite{baxter15}.
We recall their characterization here.
For an ascent sequence $w\in \a_n(000,001)$, all entries after the first weak descent $vu,\ v\ge u,$ must be $<u$ and strictly decreasing. In particular, for $n\ge3$, $w$ cannot begin 00 and begins $01\dots v$ where $v$ is the maximum value. The only ascent sequence in $\a_n(000,001)$ with no weak descents is $01\dots n-1$.  Thus, for $n\ge3$,
\[
\v  \a_n(000,001) \v = 1 + \sum_{v=1}^{n-2}\sum_{u=0}^{v} \binom{u}{n-(v+1)} = F_{n+1}\, .
\]
From the preceding characterization, it is clear that $w\in \a_n(000,001)$ also avoids 100, 101, 102,  and 201. Hence $\v\a_n(f_1)\v =\v \a_n(f_2)\v =\v  \a_n(f_3)\v =\v \a_n(f_4)\v$.

\subsubsection{$f_5$ thru $f_{12}$} \label{f5}
Let $\f_n$ denote the set of integer sequences $(u_i)_{i=1}^n$ that satisfy (i) $u_1=0$, (ii) $u_i \le u_{i+1} \le u_i+1$ for $1\le i \le n-1$, and (iii) no integer occurs more than twice in the sequence. For example, $\f_4=\{0011,0012,0112,0122,0123\}$. It is easy to see that $\v \f_n\v = F_{n+1}$, where $F_n$ is the Fibonacci number. It is also easy to see that $ \a_n(000,010) $ coincides with $\f_n$. Since sequences in $\f$ also avoid 021, 100, 101, 102, 110, 120, 201, and 210, all the triples $f_5$ through $f_{12}$ have the same set of avoiders.



\subsection{Proof of Theorem \ref{thm1} part (2)}\label{001and100}

An ascent sequence $w\in \a_n(001,100)$ (see \cite{baxter15} for an alternative account) must begin with unit increments until its maximum entry $m\ge0$ is achieved, thus $01\dots m$, and this $m$ then occurs (consecutively) $j\ge1$ times. Any remaining entries must be $<m$ and strictly decreasing. Consequently,
\[
\v  \a_n(001,100) \v = \sum_{m=0}^n\sum_{j=1}^{n-m} \binom{m}{n-(m+j)} = F_{n+2}-1\, .
\]
From the preceding characterization, it is clear that $w\in \a_n(001,100)$ also avoids 101, 102 and 201. Hence $\v a_n(001,100,101)\v = \v\a_n(001,100,102)\v = \v\a_n(001,100,201)\v$.


\subsection{Proof of Theorem \ref{thm1} part (3)}\label{part3}

\subsubsection{$h_1$ and $h_2$} \label{F1}
To suppress consecutive repetition in a sequence, denoted supp\_consec\_rep, means to successively erase from left to right each entry that coincides with its immediate predecessor, in other words, to replace each run of equal entries with a single copy of that entry, thus supp\_consec\_rep(0233310044046)=023104046.  Similarly, del\_0 means to erase 0's, thus del\_0(023104046)=231446.

\begin{prop}\label{ff1} A sequence of $n$ nonnegative integers $w=(w_i)_{i=1}^n$ is in $\a_n(021,101)$ if and only if $w_1=0$ and \emph{del\_0(supp\_consec\_rep$(w)$))} is empty or an initial segment of the positive integers $1,2,\dots,m$ for some $m$. For example, $00111023340055 \in \a_{14}(021,101)$ but $0101$ and $01221$ are not.
\end{prop}
\begin{proof} Easy and left to the reader. Note that the stated condition guarantees $w$ grows slowly enough to be an ascent sequence.
\end{proof}
Let $\c_{m,k}$ denote the set of compositions $(c_i)_{i=1}^k$ of $m$ into $k$ \emph{nonnegative} parts.
The following sums are well known and easy to prove using lattice paths of $m$ East and $k-1$ or $2k-1$ North steps:
\begin{align}
\sum_{c\in\c_{m,k}} 1 & =  \binom{m+k-1}{m}\, , \label{good}\\
\sum_{c\in\c_{m,k}} \prod_{i=1}^k(c_i+1) & =  \binom{m+2k-1}{m}\, \notag.
\end{align}

To form a sequence  $w=(w_i)_{i=1}^n$ with $j$ initial 0's and maximum entry $k$ that meets the condition of Proposition \ref{ff1}, note that there are $n-k-j$ entries other than the initial 0's and the first occurrences of $1,2,\dots,k$. Begin with a composition $(c_i)_{i=1}^k$ of $n-k-j$ where $c_i\ge 0$ is the number of entries strictly
between the first occurrence of $i$ and the first occurrence of $i+1$
(or strictly after the first occurrence of $k$ when $i=k$). Each $c_i$ gives $c_i+1$ choices to determine where the left to right entries switch from $i$ to 0, as they must. All told, the number of (021,101)-avoiding ascent sequences of length $n$ with $j$ initial 0's and maximum entry $k$ is
\[
\begin{array}{cllc}
1\textrm{ (for the all-0's sequence)} & + \quad \sum_{j=1}^{n-1}\sum_{k=1}^{n-j}
\sum_{c\in\c_{n-k-j,k}} \prod_{i=1}^k(c_i+1)  & = & \\[2mm]
1 & +\quad \sum_{j=1}^{n-1}\sum_{k=1}^{n-j}\binom{n+k-j-1}{n-k-j} & = & \\[2mm]
1 & + \quad \sum_{j=1}^{n-1} F_{2(n-j)} & = & F_{2n-1}\, ,
\end{array}
\]
using (\ref{good}) for the first equality and standard Fibonacci number identities for the others.

The above characterization shows that (021,101)-avoiders also avoid 201 and 210. Thus $h_1$-avoiders and $h_2$-avoiders both coincide with (021,101)-avoiders.

\subsubsection{$h_3$ and $h_4$} \label{F3}
A left-to-right maximum (lrMax) in a sequence $w$ of integers is an entry that is greater than all its predecessors; thus a particular value can occur only once as an lrMax in $w$, and 002243 has lrMax entries at positions 1,3,5.

\begin{prop} An ascent sequence $w=(w_i)_{i=1}^n$ avoids $021$ and $120$  if and only if every descent top in $w$ $($if any$)$ is $1$. For example, $00100110244455 \in \a_{14}(021,120)$ but $010212$ is not.
\end{prop}
\begin{proof} Easy and left to the reader.
\end{proof}
Thus a nonnegative sequence is in $\cup_{n\geq1}\a_n(021,120)$ if and only if it has the form $uv$ where $u$ is an arbitrary sequence of 0's and 1's that starts with a 0  and if $v$ is  nonempty then (i) max($u)=1$ so that $u$ has $r\ge 1$ ascents and (ii)
the first entry (= first lrMax) of $v$ is $\ge 2$ and the $i$-th lrMax of $v$ is $\le r+i, \ i\ge 1$. The all-0's sequence $u$ has \gf $1/(1-x)$, where $x$ marks number of entries.
Otherwise $u$ has $r\ge 1$ ascents and hence has the form $0^{i_0}\cdot01\cdot1^{i_1}0^{j_1}\cdot01\cdot \dots \cdot01\cdot 1^{i_r}0^{j_r}$ with all exponents $\ge 0$, leading to the \gf
$x^{2r}/(1-x)^{2r+1}$. As for $v$, the ``base case'' $r=1$ involves a sequence that starts with a 2 and each successive entry is the same as, or 1 unit greater than, its predecessor leading to the \gf: 1\,(for the empty sequence)$\,+\,x/(1-2x) =(1-x)/(1-2x)$. The general case can be seen to be the $r$-fold convolution of the base case with \gf $((1-x)/(1-2x))^r$. All told, including the empty ascent sequence, the \gf is
\[
\frac{1}{1-x}+\sum_{r\ge 1}\frac{x^{2r}}{(1-x)^{2r+1}}\left(\frac{1-x}{1-2x}\right)^r
=\frac{1-2x}{1-3x+x^2} = 1 +\sum_{n\ge 1}F_{2n-1}x^n\,.
\]
The above characterization shows that (021,120)-avoiders also avoid 201 and 210. Thus $h_3$-avoiders and $h_4$-avoiders both coincide with (021,120)-avoiders.


\subsubsection{$h_5$} \label{F5}
To avoid $h_5$ means that for every inversion $v>u$, all entries after the $u$
are $>u$ and $\ne v$. Now consider a nonempty ascent sequence $w$.
Let $k\ge 1$ denote the position of the last 0 in $w$ and set $m=\max(w_i)_{i=1}^k$.
Then  it is easy to see that $w$ is a (100,101,210)-avoider if and only if (i) $
(w_i)_{i=1}^{k-1}$ is weakly increasing and contains $0,1,\dots,m$, (ii) $w_{k+1}=m+1$, (iii) $(w_i-m-1)_{i\ge k+1}$ is a (100,101,210)-avoider. On the other hand, as shown in Section \ref{F7} below,
$w$ is a (101,110)-avoider if and only if (i) the nonzero entries of $(w_i)_{i=1}^{k-1}$
are $1,2,\dots,m$ in that order, (ii) $w_{k+1}=m+1$, (iii) $(w_i-m-1)_{i\ge k+1}$ is a
(101,110)-avoider. Thus a bijection $A_n(101,110) \to A_n(100,101,210)$ can be defined
as follows. Given $w \in  A_n(101,110)$, for each $i=2,3,\dots,n-2$ in turn with $u:=
w_{i+1}$, if $w_i>u$ and $w_j=u$ for some $j>i+1$, then replace $w_{i+1}$ with $w_i$.

\subsubsection{$h_6$} \label{F6}
A nonnegative sequence $w=(w_i)_{i=1}^n$ avoids 101,102, and 201 if and only if it is either weakly increasing or weakly decreasing after the first descent. Thus, if the first descent top is
$w_k=s$, we have $\ 1\le s <k \le n-1$, and $(w_i)_{i=k+1}^n$ is weakly decreasing with
$w_{k+1}\le s-1$. There are  $\binom{n-k+s-1}{s-1}$ such sequences $(w_i)_{i=k+1}^n$.
There are $\binom{k-1}{s}$ weakly increasing ascent sequences of length $k$ that end with an $s$,
and $2^{n-1}$ weakly increasing ascent sequences of length $n$. Hence,
\[
\v \a_n(101,102,201) \v =
2^{n - 1} + \sum_{k=2}^{n-1}\sum_{s=1}^{k-1}\binom{k-1}{s}\binom{n-k+s-1}{s-1} = F_{2n-1}\, .
\]

\subsubsection{$h_7$ and $h_8$} \label{F7}
Ascent sequences avoiding (101,110) were counted in \cite{baxter15} using generating trees.
Here we give a direct count.
Consider the position $k\ge 1$ of the last 0 in a (101,110)-avoiding ascent sequence $w$.

If $k=1$ then $w_2$ (if present) is 1 and $(w_i-1)_{i\ge2}$ is easily seen to be an arbitrary (101,110)-avoider.

If $k\ge2$, write $w$ as $uv$ where $u$ consists of the first $k$ entries of $w$. Then $u_k=0$ and the nonzero entries of $u$ are all distinct since $u$ avoids 110 and must form, left to right, an initial segment of the positive integers since $u$ is an ascent sequence. Thus each interior entry of $u$ is 0 or 1 more than the largest previous entry, giving $2^{k-2}$ choices for $u$. Let $m=\max{u}$. Then $v_1$ (if present) must be $m+1$. This is because $v_1\le m+1$ since $u$ contains only $m$ ascents and so $v_1=m+1$ to avoid 101. Also, $v-(m+1)$ (termwise subtraction) is an arbitrary (101,110)-avoider.

In any case $w\in \a_n(101,110)$ decomposes as an ordered pair $(u,v')$ where $u,v'$ are (101,110)-avoiders whose lengths sum to $n$, $u$ is nonempty of length $k\ge1$ with
$\max(1,2^{k-2})$ choices for $u$, and $v'$ may be empty. Iterating the decomposition, we find, with $\c_n$ denoting the set  of compositions $c=(c_i)_{i=1}^r$ into positive parts $c_i$,
\[
\v \a_n(101,110) \v = \sum_{c\in \c_n}\prod_{i=1}^r\max(1,2^{c_i-2}) = F_{2n-1}\, .
\]

The preceding observations show that (101,110)-avoiders also avoid 201 and 210. Thus $h_7$-avoiders and $h_8$-avoiders both coincide with (101,110)-avoiders.

\subsection{Proof of Theorem \ref{thm1} part (4)}

\subsubsection{$i_1$} \label{G1}
Let $w \in \a_n(000,021,101)$. Since an ascent sequence begins with a 0, to avoid 021 implies that only 0 can be a descent bottom, and so avoidance of 000 implies $w$ has at most one descent. Let $k\ge 1$ denote the position of the last 0 in $w$. If $k=1$, then $w$ is weakly increasing and so has the form $0v$ where $v-1\in \f_{n-1}$ (where $\f$ is defined in Section \ref{f5} above) since $w$ is an ascent sequence and to avoid 000. If $k=2$, then $w=00v$ where $v-1\in \f_{n-2}$. These two cases contribute $F_n+F_{n-1}$ to the count. Now suppose $k \ge 3$ and write $w$ as $0u0v$. Here $u-1 \in \f_{k-2}$ and $v-(m+1) \in \f_{n-k}$ where $m:=\max(u)$. Hence
\begin{equation}\label{G1eqn}
\v \a_n(000,021,101) \v = F_n+\sum_{k=2}^nF_{k-1}F_{n-k+1}\, .
\end{equation}

\subsubsection{$i_2$} \label{G2}
Let $w \in \a_n(000,021,110)$.  Again, let $k\ge 1$ denote the position of the last 0 in $w$.
 %and note only 0 can be a descent bottom.
Again, if $k=1$, then $w$ is weakly increasing and so has the form $0v$ where $v-1\in \f_{n-1}$, and
if $k=2$, then $w=00v$ where $v-1\in \f_{n-2}$. If $k=n\ge 3$, then $w=01\dots (n-2)0$ in order to avoid 110. Now suppose $3 \le k \le n-1$, and write $w=0u0v$. Then $u=12\dots (k-2)$ and $v=(v_i)_{i=1}^{n-k}$ is weakly increasing and satisfies $v_{i+1} \le v_i+1$ for all $i$ if $v_1=k-1$. But $v_1$ may $=k-2$ in which case the inequality $v_{i+1} \le v_i+1$ may be violated with a jump of \emph{two} units, $v_{i+1}=v_i+2$, for at most one value of $i$ due to the extra ascent introduced by $v_1$.

First, suppose no such jump occurs. If $v_1=k-2$, then $v_2$ (if present) must $=k-1$ and $(v_i-(k-1))_{i=2}^{n-k} \in \f_{n-k-1}$, counted by $F_{n-k}$. Otherwise, $v_1=k-1$ and $(v_i-(k-1))_{i=1}^{n-k} \in \f_{n-k}$, counted by $F_{n-k+1}$. Now suppose such a jump occurs starting at position $r,\  1\le r \le n-k-1$. Then $k\le n-2,\ v_1=k-2,\ v_2=k-1$ and $(v_i-(k-1))_{i=2}^{r} \in \f_{r-1}$, counted by $F_{r}$. Also, $(v_i-(v_r+2))_{i=r+1}^{n-k} \in \f_{n-k-r}$, counted by $F_{n-k-r+1}$. Hence, for $n\ge 3$,
\begin{equation*}
\v \a_n(000,021,110) \v = F_n+F_{n-1}+1 + \sum_{k=3}^{n-1} (F_{n-k}+F_{n-k+1}) + \sum_{k=3}^{n-2}\sum_{r=1}^{\ n-1-k}F_r F_{n-k-r+1}\, ,
\end{equation*}
which can be shown to agree with the expression in (\ref{G1eqn}).

\section{Further results: quadruples of 3-letter patterns}
As a consequence of the results of the previous section, here we present several pattern avoidance classes of ascent sequences avoiding a quadruple of length-3 patterns whose counting sequences are closely related to Fibonacci numbers.
\begin{prop}
For each of the following sets of 4 patterns $f$, we have $\v\a_n(f)\v=F_{n+1}$.
\begin{center}
\begin{tabular}{cccc}
\{000,001,100,101\}&\{000,001,100,102\}&\{000,001,100,201\}&\{000,001,101,102\}\\
\{000,001,101,201\}&\{000,001,102,201\}&\{000,010,021,100\}&\{000,010,021,101\}\\
\{000,010,021,102\}&\{000,010,021,110\}&\{000,010,021,120\}&\{000,010,021,201\}\\
\{000,010,021,210\}&\{000,010,100,101\}&\{000,010,100,102\}&\{000,010,100,110\}\\
\{000,010,100,120\}&\{000,010,100,201\}&\{000,010,100,210\}&\{000,010,101,102\}\\
\{000,010,101,110\}&\{000,010,101,120\}&\{000,010,101,201\}&\{000,010,101,210\}\\
\{000,010,102,110\}&\{000,010,102,120\}&\{000,010,102,201\}&\{000,010,102,210\}\\
\{000,010,110,120\}&\{000,010,110,201\}&\{000,010,110,210\}&\{000,010,120,201\}\\
\{000,010,120,210\}&\{000,010,201,210\}.	
\end{tabular}
\end{center}
\end{prop}
\begin{proof}
Each of these quadruples contains either the pair $\{000,001\}$ or the pair $\{000,010\}$. So the results follow from Section \ref{part1}.
\end{proof}

\begin{prop}\label{p2}
For all $n\geq5$, $\v\a_n(000,021,102,120)\v=F_{n+1}$.
\end{prop}
\begin{proof}
For $n\ge 5$, there can be no descent to $0$ (to avoid $120$). Thus for $n\ge 5$, these avoiders coincide with $\f_n$, defined in Section \ref{f5}, counted by $F_{n+1}$.
\end{proof}

\begin{prop}
For all $n\geq5$, $\v\a_n(000,021,102,110)\v=F_{n+1}+1$.
\end{prop}
\begin{proof}
For $n\ge5$, these avoiders include case Proposition \ref{p2} and also $012\dots (n-1)0$, counted by $F_{n+1}+1$.
\end{proof}

\begin{prop}
For all $n\geq5$,
\begin{align*}
\v\a_n(000,021,100,102)\v&=\v\a_n(000,021,102,201)\v
=\v\a_n(000,021,102,210)\v\\
&=L_n=F_{n+1}+F_{n-1},
\end{align*}
where $L_n$ is the $n$th Lucas number, sequence A000032 in \cite{Sl}.
\end{prop}
\begin{proof}
Let $\tau=\{000,021,102\}$. For a $\tau$-avoider, all descent bottoms must be 0, to avoid 021, and so an avoider has at most one descent, to avoid 000. Furthermore, this descent bottom must end the sequence, to avoid 021 and 102.
Hence, with $m'$ denoting $\max(w')$ and $w \in A_n(\tau)$, either (i) $w \in \f_n$, or (ii) $w=0w'(m'+1)0$ with $w'-1 \in \f_{n-3}$, or (iii) $w=0w'(m'+1)(m'+1)0$ with $w'-1 \in \f_{n-4}$ (here the word $w'-1$ is obtained by the word $w'$ by decreasing each letter by $1$). Thus $\tau$-avoiders are counted by $F_{n+1}+F_{n-2}+F_{n-3}=L_n$, the Lucas number, for $n\ge 5$. It is clear that $(000,021,102)$-avoiders also avoid 100, 201, and 210, and so all 3 quadruples here give rise to Lucas numbers.
\end{proof}

\begin{prop}
For all $n\geq1$,
\begin{align*}
\v\a_n(000,021,101,110)\v&=\v\a_n(000,101,102,110)\v=\v\a_n(001,100,101,102)\v\\
&=\v\a_n(001,100,101,201)\v=\v\a_n(001,100,102,201)\v=F_{n+2}-1.
\end{align*}
\end{prop}
\begin{proof}
An avoider $w \in A_n(000,021,101,110)$ is either in $\f_n$ or begins $012\dots (m-2)0$ with a descent to 0 at position $m \in[3,n]$, and $(w_i-(m-1))_{i=m+1}^n \in \f_{n-m}$. So, for $n\ge 1$,
\begin{align*}
\v\a_n(000,021,101,110)\v & =\v\f_n\v+\sum_{m=3}^n\v\f_{n-m}\v =
F_{n+1}+\sum_{m=3}^nF_{n-m+1} =F_{n+2}-1\, .
\end{align*}

For an avoider $w\in\a_n(000,101,102,110)$ either $w \in \f_n$ or the last entry of $w$ is a descent bottom that is larger than the last repetition (successive equal entries) in $w$, to avoid 110. In this case either $w=012\dots(n-2)a$ with no repetitions and $a\in [0,n-3]$, giving $n-2$ choices when $n\ge 2$, or (iii) the last repetition ends at position $k\in[2,n-3]$ and $w$ has the form  $w=w'mm(m+1)(m+2) \dots(m+n-k-2)a$ with the second $m$ in position $k$, $w'\in \f_{k-2}$ and $m-1$ the last entry of $w'$, and $a\in [m+1,m+n-k-2]$. This gives  $\binom{m}{k-2-m}$ choices for $w'$ and $n-k-2$ choices for $a$. Hence, for $n\ge 2$,
\begin{align*}
\v A_n(000,101,102,110)\v & = F_{n+1} + n-2 + \sum_{k=2}^{n-3} (n-k-2)\sum_{m=\lceil k/2\rceil-1}^{k-2} \binom{m}{k-2-m} \\
 &  = F_{n+2}-1\, .
\end{align*}

The last 3 quadruples are covered by Section \ref{001and100}.
\end{proof}


\begin{prop}\label{p6}
For all $n\geq1$,
$\v\a_n(000,101,110,120)\v=F_{n+2}^{(3)}$, the $(n+2)$-Tribonacci number, sequence A000073 in \cite{Sl}.
\end{prop}
\begin{proof}
Let $u_n=\v A_n(\tau)\v$ where $\tau=\{000,101,110,120\}$ and for an avoider $w$, let $L_0(w)$ denote the position of the last 0 in $w$.
If $L_0(w)=1$, then $(w_2-1)\cdots(w_n-1)\in A_{n-1}(\tau)$. If $L_0(w)=2$, then $w_1=w_2=0$ and
$(w_3-1)\cdots(w_n-1)\in A_{n-2}(\tau)$. Otherwise, since all descents are of precisely one unit to avoid 120, $L_0(w)=3$ and  $w_1w_2w_3=010$ and $(w_4-2)\cdots(w_n-2)\in A_{n-3}(\tau)$. Hence, the sequence $u_n$ satisfies the ``tribonacci'' recurrence $u_n=u_{n-1}+u_{n-2}+u_{n-3}$.

Here is an explicit counting approach.
If $w\in \a_n(000,101,110,120)$ has no weak descents, then $w=012\dots (n-1)$. Otherwise, a typical avoider looks like
\[012343|56788|9\,10\,9|11\,11|12\,13\,14\,15\, ,
\]
where a divider has been inserted after each weak descent bottom to divide the ascent sequence into convenient blocks. The block after the last weak descent bottom forms an interval of integers (possibly empty). Every block other than this one has successive entries increasing by 1 except the last entry may be an equality or (but only in blocks of length $\ge 3$) a decrease of 1. Furthermore, the first entry of each noninitial block is 1 more than the maximum entry of the previous block. The restricted increases are due to the ascent sequence requirement and then the other restrictions are to avoid 000, 101, 110, and 120.

Consequently, if $w$ has $r\ (0\le r \le n-2$) entries after the last weak descent, then $w$ is determined by a composition of $m:=n-r$ in which all parts are $\ge 2$ and each part $\ge 3$ is colored red ($R$) or blue ($B$), according as the last entry of the corresponding block is an equality or a decrease. For the example above, the composition of $m=16$ is $(6_B,5_R,3_B,2)$. The number of such colored compositions of $m$ is sequence A001590 in \cite{Sl},
$(0,1,2, 3, 6, 11, 20, 37,\dots)_{m\ge 1}$. The desired counting sequence can now be obtained from the partial sums of this sequence.
\end{proof}

\begin{prop}
For all $n\ge1$,
\begin{align*}
&\v\a_n(000,021,100,101)\v=\v\a_n(000,021,100,110)\v=\v\a_n(000,021,101,201)\v\\
&=\v\a_n(000,021,101,210)\v=\v\a_n(000,021,110,201)\v=\v\a_n(000,021,110,210)\v=\\
&=\v\a_n(000,101,102,210)\v=\frac{(n+4)F_n+2nF_{n-1}}{5}.
\end{align*}
%%1,2,4,8,15,+28,51,92,164,290,509,
\end{prop}
\begin{proof}
Ascent sequences avoiding 000, 021, and 101 are characterized in Section \ref{G1}. From the characterization, it is clear that such sequences also avoid 100, 201, 210 and so the first, third, and fourth quadruples all have avoiders coinciding with $A_n(000, 021, 101)$, counted in Section \ref{G1}. Similarly, ascent sequences avoiding 000, 021, and 110 are characterized in Section \ref{G2} and it is clear that such sequences also avoid 100, 201, and 210, and so the second, fifth, and sixth quadruples all have avoiders coinciding with $A_n(000, 021, 110)$, counted in Section \ref{G2}.

Now let $\tau=\{000, 101, 102, 210\}$, the seventh quadruple. It is convenient to set $\f_{n,m}=\{w\in \f_n:\,w_n=m\}$. Note that $\v \f_{n,m} \v = \binom{m+1}{n-m-1}$ and $w\in \f_{n,m}$ contains $n-1-m$ repeated letters.
After a descent $v>u$ in a $\tau$-avoider, all later entries must lie in $[u,v-1]$ and any such entry would repeat an earlier entry and thereby introduce a 000 or 101. Hence, only the last entry can be a descent bottom. So for $w \in \a_n(\tau)$, either $w\in \f_n$ or $w$ has the form (i) $w=w'ma$ where $w'=0 \dots m-1 \in \f_{n-2,m-1}$ and $a\in[0, m-1]$ is not a repeated letter in $w'$, to avoid 000, or (ii) $w=w'mma$ where $w'=0 \dots m-1 \in \f_{n-3,m-1}$ and again, $a\in[0, m-1]$ is not a repeated letter in $w'$. In case (i), there are $\v\f_{n-2,m-1}\v=\binom{m}{n-2-m}$ choices for $w'$, while there are $n-2-m$ repetitions in $w'$ and so $m-(n-2-m)=2m-n+2$ choices for $a$. In case (ii), there are $\v\f_{n-3,m-1}\v=\binom{m}{n-3-m}$ choices for $w'$, while there are $n-3-m$ repetitions in $w'$ and so $m-(n-3-m)=2m-n+3$ choices for $a$. Hence,
\begin{align*}
\v  \a_n(000, 101, 102, 210) \v  & =F_{n+1}+\sum_{m=\lfloor (n-1)/2\rfloor}^{n-2}(2m-n+2)\binom{m}{n-2-m}  \\
  & \hspace*{13mm} + \sum_{m=\lfloor (n-2)/2\rfloor}^{n-3}(2m-n+3)\binom{m}{n-3-m} \\
  & = \frac{(n+4)F_n+2nF_{n-1}}{5},
\end{align*}
which completes the proof.
\end{proof}



\begin{prop}
For all $n\geq1$, $\v\a_n(000,101,120,210)\v=F_{n+3}^{(4)}$; the $(n+3)$-Tetranacci number, sequence A000078 in \cite{Sl}.
\end{prop}
\begin{proof}
Let $u_n=\v A_n(\tau)\v$ where $\tau=\{000,101,120,210\}$ and for an avoider $w$, let $L_0(w)$ denote the position of the last 0 in $w$, so that $L_0(w)=1,2,3$ or $4$ (if $L_0(w)\ge 5$, a 120 would be present). Then, for $1\le k \le 4, \ \v \{w\in \a_n(000,101,120,210):\, L_0(w)=k\} \v =u_{n-k}$ as follows.
If $k=1$, then $(w_2-1)\cdots(w_n-1)\in A_{n-1}(\tau)$; if $k=2$, then $(w_3-1)\cdots(w_n-1)\in A_{n-2}(\tau)$; if $k=3$, then  $w_1w_2w_3=010$ and $(w_4-2)\cdots(w_n-2)_{i\ge 4}\in A_{n-3}(\tau)$; if $k=4$, then   $w_1w_2w_3w_4=0110$ and $(w_5-2)\cdots(w_n-2)\in A_{n-4}(\tau)$. Hence $u_n$ satisfies the ``tetranacci'' recurrence $u_n=u_{n-1}+u_{n-2}+u_{n-3}+u_{n-4}$.

Here is an explicit construction for these avoiders. Place $a\ge0$ trominoes (3-by-1) and $b\ge0$ quadrominoes (4-by-1) on an $n$-by-1 grid of cells so they don't overlap, illustrated in blue in the first row of Figure 1 with $a=2,\ b=1$ and $n=21$. Place 010 in the cells of each tromino and 0110 in the cells of each quadromino (second row). The $a+b$ ``ominoes'' divide the grid into $a+b+1$ segments (some or all of which may be empty) of contiguous cells of lengths, say, $c_1,c_2,\dots,c_{a+b+1}$ that form a composition $c=(c_i)$ of $n-(3a+4b)$ into $a+b+1$ nonnegative parts.
\[
\begin{array}{l}
\framebox{\phantom{0}}\framebox{\phantom{1}}\framebox{\phantom{1}}\framebox{\phantom{2}} \, \blue{\framebox{\phantom{0}}\framebox{\phantom{1}}\framebox{\phantom{1}}\framebox{\phantom{0}}}\,\framebox{\phantom{0}}\framebox{\phantom{0}}\,\blue{\framebox{\phantom{0}}\framebox{\phantom{1}}\framebox{\phantom{0}}}\,
\blue{\framebox{\phantom{0}}\framebox{\phantom{1}}\framebox{\phantom{0}}}\,\framebox{\phantom{0}}\framebox{\phantom{1}}\framebox{\phantom{1}}\framebox{\phantom{2}}\framebox{\phantom{2}} \\
\framebox{\phantom{0}}\framebox{\phantom{1}}\framebox{\phantom{1}}\framebox{\phantom{2}} \, \blue{\framebox{0}\framebox{1}\framebox{1}\framebox{0}}\,\framebox{\phantom{0}}\framebox{\phantom{1}}\,\blue{\framebox{0}\framebox{1}\framebox{0}}\,
\blue{\framebox{0}\framebox{1}\framebox{0}}\,\framebox{\phantom{0}}\framebox{\phantom{0}}\framebox{\phantom{1}}\framebox{\phantom{2}}\framebox{\phantom{2}} \\
\framebox{0}\framebox{1}\framebox{1}\framebox{2} \, \blue{\framebox{0}\framebox{1}\framebox{1}\framebox{0}}\,\framebox{0}\framebox{1}\,\blue{\framebox{0}\framebox{1}\framebox{0}}\,
\blue{\framebox{0}\framebox{1}\framebox{0}}\,\framebox{0}\framebox{0}\framebox{1}\framebox{2}\framebox{2}\\
\framebox{0}\framebox{1}\framebox{1}\framebox{2} \, \framebox{3}\framebox{4}\framebox{4}\framebox{3}\,\framebox{5}\framebox{6}\,\framebox{7}\framebox{8}\framebox{7}\,
\framebox{9}\framebox{10}\framebox{9}\,\framebox{11}\framebox{11}\framebox{12}\framebox{13}\framebox{13}
\end{array}
\]
\centerline{Figure 1}
Place an arbitrary element of $\f_{c_i}$ in the $i$-th segment, $1\le i \le a+b+1$ (third row). Then ``bump up" the entries in the ominoes and the nonempty segments, so that the first entry in each is 1 unit greater than the maximum entry in its predecessor (bottom row) to get a $\tau$-avoider of length $n$. Every $\tau$-avoider arises in this way. Consequently, recalling $\c_{m,k}$ denotes the set of compositions $(c_i)_{i=1}^k$ of $m$ into $k$ nonnegative parts,
\begin{eqnarray*}
\v\a_n(000,101,120,210)\v  = & \sum_{\substack{a,b\ge 0 \\ 3a+4b\le n}}\binom{a+b}{b}
\prod_{c\in\c_{n-3a-4b,a+b+1}}F_{c_i+1}\\
 =   & \sum_{\substack{a,b\ge 0 \\ 3a+4b\le n}}\binom{a+b}{b} [x^{n-3a-4b}]\left(\frac{1}{1-x-x^2}\right)^{a+b+1}\,,
\end{eqnarray*}
where $[x^m]$ extracts the coefficient of $x^m$, since $\frac{1}{1-x-x^2}$ is the \gf $\sum_{n\ge 0}F_{n+1}x^n$.
\end{proof}

\begin{prop}
For all $n\geq1$,
\begin{align*}
\v\a_n(021,101,201,210)\v&=	
\v\a_n(021,120,201,210)\v=	
\v\a_n(100,101,201,210)\v\\
&=\v\a_n(101,110,201,210)\v=F_{2n-1}.
\end{align*}
\end{prop}
\begin{proof}
The avoiders for these four quadruples coincide, respectively, with the avoiders for cases $h_1,\ h_3,\ h_5$, and $h_7$ in Section \ref{part3}. This is clear from the descriptions of the avoiders in Section \ref{part3}.
\end{proof}



\begin{thebibliography}{99}
\bibitem{baxter15} Andrew M. Baxter and
Lara K. Pudwell, Ascent sequences avoiding pairs of patterns,
\emph{The Electronic Journal of Combinatorics} \textbf{22}(1) (2015), \#P1.58.

\bibitem{M1}
M. Bousquet-M\`{e}lou, A. Claesson, M. Dukes, and S. Kitaev, $(2 + 2)$-free posets, ascent sequences and pattern avoiding permutations, J. Combin. Theory Ser. A 117 (7) (2010), 884--909.

\bibitem{DMS}
D. Callan, T. Mansour, and M. Shattuck, Restricted ascent sequences and Catalan numbers, Appl. Anal. Discrete Math. 8 (2014), 288--303.

\bibitem{D1}
M. Dukes and R. Parviainen, Ascent sequences and upper triangular matrices containing non-negative integers, Electron. J. Combin. 17 (1) (2010), \#R53.

\bibitem{D2}
M. Dukes, J. Remmel, S. Kitaev, and E. Steingrímsson, Enumerating $(2 + 2)$-free posets by indistinguishable elements, J. Comb. 2(1) (2011), 139--163.

\bibitem{K1}
S. Kitaev, Patterns in Permutations and Words, in: Monographs in Theoretical Computer Science (with a forward by J. Remmel), Springer-Verlag, 2011.

\bibitem{K2}
S. Kitaev and J. Remmel, Enumerating $(2 + 2)$-free posets by the number of minimal elements and other statistics, Discrete Appl. Math. 159 (2011), 2098--2108.

\bibitem{MS1}
T. Mansour and M. Shattuck, Some enumerative results related to ascent sequences, Discrete Math. 315--316 (2014), 29--41.

\bibitem{MS2}
T. Mansour and M. Shattuck, Ascent sequences and Fibonacci numbers, FILOMAT 29:4 (2015), 703--712.

\bibitem{Sl}
 N. J. Sloane, The on-line encyclopedia of integer sequences, http://oeis.org.
\end{thebibliography}

\end{document}