% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
% Please remove all other commands that change parameters such as
% margins or pagesizes.
% only use standard LaTeX packages
% only include packages that you actually need
\usepackage{amsmath,amssymb,latexsym,url,graphicx,amsthm,multirow,color,enumerate}
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins
% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{conj}{Conjecture}
\newtheorem{cor}{Corollary}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{lemma}{Lemma}
\newtheorem{notation}{Notation}
\newtheorem{prop}{Proposition}
\newtheorem{remark}{Remark}
\newtheorem{theorem}{Theorem}
\newtheorem{algorithm}{Algorithm}
\newcommand{\asc}{\mathrm{asc}}
\newcommand{\red}{\mathrm{red}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% if needed include a line break (\\) at an appropriate place in the title
\title{Ascent sequences avoiding pairs of patterns}
% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address
\author{Andrew M. Baxter \\
\small Mathematics Department \\[-0.8ex]
\small Pennsylvania State University \\[-0.8ex]
\small State College, PA, USA \\[-0.8ex]
\small \texttt{baxter@math.psu.edu}\\
\and
Lara K. Pudwell\\
\small Department of Mathematics and Statistics \\[-0.8ex]
\small Valparaiso University \\[-0.8ex]
\small Valparaiso, IN, USA \\[-0.8ex]
\small \texttt{Lara.Pudwell@valpo.edu}
}
% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}
\date{\dateline{June 20, 2014}{Jan 12, 2015}\\
\small Mathematics Subject Classifications: 05A05, 05A15, 05A18, 05A19}
\begin{document}
\maketitle
\abstract{
Ascent sequences were introduced by Bousquet-Melou et al. in connection with (2+2)-avoiding posets and their pattern avoidance properties were first considered by Duncan and Steingr\'{i}msson. In this paper, we consider ascent sequences of length $n$ avoiding two patterns of length 3, and we determine an exact enumeration for 16 different pairs of patterns. Methods include simple recurrences, bijections to other combinatorial objects (including Dyck paths and pattern-avoiding permutations), and generating trees. We also provide an analogue of the Erd\H{o}s-Szekeres Theorem to prove that any sufficiently long ascent sequence contains either many copies of the same number or a long increasing subsequence, with a precise bound.
}
\section{Introduction}\label{Introduction}
Given an integer string $x_1\dotsm x_n$, an \emph{ascent} is position $j$ such that $x_j x_{i+1}$ there must be some $j* x_{j^*+1}$ implies $\red(x_{j^*} x_{j^*+1} x_{i+1}) = 101$ and maximality of $j^*$ implies $x_{j^*}\neq x_{j^*+1}$. If $x$ also avoids 210, then we can further state $x_{j^*+1} x_{i+1}$ and $x_j > x_{j+1}$ for $i x_{i+1}$
\item $x_i < x_{i+1}$ where $x_i=d$ is the last occurrence of the value $d$ in $x_1\dotsm x_{i}$ before there is a descent of the form $x_j d$. In terms of observation (ii) above, $x_i$ plays the role of $x_{j^*}$ for some later descent.
\item $x_i < x_{i+1}$ where $x_i=d$ is \emph{not} the last occurrence of the value $d$ in $x_1\dotsm x_{i}$ before there is a descent of the form $x_j d$
\end{enumerate}
These behaviors imply an encoding of any ascent sequence by a word in $w\in \{A,B,C,D\}^{n-1}$, where $w_i$ takes the value corresponding to the behavior of $a_i$ as listed above. Observation (ii) above implies that each descent is preceded by an ascent and so behaviors (B) and (C) appear equally often with the first instance of (C) preceding the first (B). The second half of observation (iii) above implies that the instances of (C) and (B) will in fact alternate, with each (C) followed by a (B) before another (C) occurs. Therefore any $x\in \mathcal{A}_{101,210}(n)$ is encoded as a word in $\{A,B,C,D\}^{n-1}$ where $C$ and $B$ alternate with $C$ appearing first. We will call such words \emph{$CB$-alternating}.
There is an obvious bijection between $CB$-alternating words and ternary strings of the same length with an even number of 2's under the mapping $A\mapsto 0$, $B\mapsto 2$, $C\mapsto 2$, and $D\mapsto 1$. Therefore it remains to show that the encoding of ascent sequences by $CB$-alternating words is bijective when the domain is restricted to $\mathcal{A}_{101,210}(n)$, which we will do by constructing the inverse.
Let $w_1 \dotsc w_{n-1}$ be a $CB$-alternating word, and we will construct the corresponding $x\in\mathcal{A}_{101,210}(n)$. Let $x_1=0$, and for $2\leq i \leq n$ determine $x_i$ as follows. If $w_{i-1}=A$, let $x_i=x_{i-1}$. If $w_{i-1}=C$ or $w_{i-1}=D$, let $x_i = \max(x_1, \dotsc, x_{i-1})+1$. If $x_{i-1}=B$, let $x_i$ take the same value as $x_{j}$ where $w_j=C$ for the largest value of $j** d_2$, then $d_2 d_2 a_i$ form a 001 pattern. Therefore, $a_i=d_2$. Therefore if $a$ has a descent $d_1 d_2$, then $a$ has the form
$$012\dotsm (d_1 -1) (d_1)^k(d_2)^{(n-k-d_1)}.$$
Thus, $a$ is uniquely defined by choosing $k$, $d_1$, and $d_2$. Clearly $0 \leq d_20$, its first appearance in $w$ must be immediately preceded by $k-1$ (a somewhat stronger condition than the RGF condition).
To prove Property (2), we will reconstruct Dyck word $d=d_1 \dotsm d_{2n}$ so that $w(d)$ matches a given $w_1 \dotsm w_n$. As for any Dyck word, $d_1=U$ and we proceed to complete $d$ from left to right. If $w_i \geq w_{i+1}$ then the $i^{th}$ upstep is followed by $w_i - w_{i+1} + 1$ downsteps, followed by the $(i+1)^{th}$ upstep. If $w_i < w_{i+1}$ then by property (1) we see that the $i^{th}$ and $(i+1)^{th}$ upsteps are consecutive. Last there are $w_{n}+1$ downsteps at the end of $d$. In this way we have inverted the function $w(d)$ and so $d$ is uniquely determined.
Property (3) follows from the proof of Property (2) as follows. As noted before, $w_i < w_{i+1}$ implies that the $i^{th}$ and $(i+1)^{th}$ upsteps of the Dyck path $d$ are consecutive. Property (2) implies that if $w_{i-1} < w_{i}$ then $w_{i-1} = w_{i} - 1$. If $w_{i-1}>w_{i}$ then the proof of Property (2) implies there are $w_{i-1} - w_{i} + 1$ consecutive downsteps immediately preceding the $i^{th}$ upstep. In particular there would be at least 2 downsteps preceding the UU formed by the $i^{th}$ and $(i+1)^{th}$ upsteps, which creates a DDUU factor. Property (3) follows.
We need one additional property to prove the bijection constructed below does what is needed. It states that, in a very specific sense, the first copy of 100 must finish before the first copy of 101 finishes.
\begin{enumerate}
\item[(4)] Let $w=w(d)$ for a DDUU-avoiding Dyck path $d$. Choose index $j$ minimally such that there exist indices $i$ and $k$ such that $iw_j$, the consecutive run of upsteps including the $j$th upstep must be preceeded by a run of at least two downsteps. Suppose to the contrary that this run is preceeded by a UD factor. Then, $d$ contains a UDUU factor, which produces a 001 pattern in $w(d)$. We assumed, however, that the 01 was part of a 101 pattern, so there must be an upstep even earlier to produce the initial 1 in the 101 pattern, creating a 1001 pattern. But then the initial 100 subpattern is a $w_iw_jw_k$ subword that creates a forbidden pattern with a smaller index for $j$, which contradicts our assumptions.}
Note that property (4) implies that if $w$ avoids 100 then $w$ must also avoid 101. This motivates the focus on removing 100 patterns in the bijection.
The proof of Property (4) is as follows. Choose $i$, $j$, and $k$ as described. The $j^{th}$ upstep of $d$ is followed either by an upstep or downstep, which we consider in cases below.
\emph{Case 1:} Assume the $j^{th}$ upstep is followed by a downstep. Then $w_j \geq w_{j+1}$. If $w_j = w_{j+1}$, then $w_i w_j w_{j+1}$ is a copy of 100. If $w_j > w_{j+1}$, then Property (1) implies the upsteps following the $(j+1)^{th}$ upstep will reach height $w_j$ (thus forming a 100 pattern) before reaching the greater height $w_i$ (which would create a 101) pattern. Therefore in this case the result is proven.
\emph{Case 2:} Assume the $j^{th}$ upstep is followed by another upstep, which we will show results in a contradiction with how $j$ is chosen. Then $w_{j}+1=w_{j+1}$.
%Since $w_i > w_j$ for some $ii$ since $w_i > w_j$ necessitates some intervening downsteps. By property (3), the DDUU-avoidance implies $w_{c-1} = w_c$. Therefore $w_{i} w_{c-1} w_{c}$ is a copy of 100 for $c-1 < j$, contradicting the minimality of $j$.
This concludes the proof of Property (4).
%We are now ready to define our map $\mathcal{D}(n) \to \mathcal{A}_{100,101}(n)$. For $d\in\mathcal{D}$, let $w=w(d)$.
%We then apply the following ``lifting'' map $\Lambda(w)$ to words in the alphabet $\{0,1,2\dotsc\}$ as follows.
%\begin{enumerate}
% \item If $w$ contains no 100 pattern, then $\Lambda(w)=w$.
% \item If $w$ contains a 100 pattern, choose index $k$ minimally such that there exist indices $j w_{\ell}$.
% \item Let $m = \max(w_1 \dotsm w_{k-1})-w_{k}+1$.
% \item Form $\Lambda(w)$ by adding $m$ to each letter of $w_{k} w_{k+1} \dotsm w_{\ell-1}$ (called ``the lifted part''), and keeping the remaining letters.
%\end{enumerate}
%Observe that the first letter in $\Lambda(w)$ which can serve as the rightmost letter in a copy of 100 appears to the right of the first such letter in $w$. In other words, $\Lambda$ moves the leftmost copy of 100 rightward until the last copy is removed entirely. Hence we may define $\Lambda^{*}(w)$ to be the word created by iterating $\Lambda$ until the result avoids 100.
%Next note that if $w$ is an RGF, then $\Lamdba(w)$ will also be an RGF: if $w'=\Lambda(w)$ with lifted part $w_{k} w_{k+1} \dotsm w_{\ell}$, then $w'_k = \max(w'_1 \dotsm w'_{k-1})+1$.
%Next suppose that $w'=\Lambda(w)$, with lifted part $w'_{k} w'_{k+1} \dotsm w'_{\ell}$, has a copy of 101 at indices $w'_a w'_b w'_c$. Since every letter in the lifted part is greater than every letter to the left of the lifted part, we know $k\leq a$. Also, if $a< \ell$ and $b>\ell$ then $w'_a w'_{\ell} w'_c$ is also a copy of 101.
%Still need: (a) If $w$ satisfies Property (4) then $\Lambda(w)$ satisfies Property (4). (b) Inverse $\Lambda^{-1}$.
Now, we define our map $\phi : \mathcal{D}(n) \to \mathcal{A}_{100,101}(n)$ as follows. It works by removing copies of 100 from left to right by ``lifting'' subwords of $w(d)$. In the process we generate words which we denote $w^0, w^1, w^2, \dotsc$, the last of which will be our $\phi(d)$.
\begin{enumerate}
\item Given $d \in \mathcal{D}(n)$, construct $w(d)$.
\item If $w(d)$ contains no forbidden 100 or 101 patterns, then $\phi(d)=w(d)$.
\item If $w(d)$ contains a forbidden pattern, then Property (4) implies there is a 100 pattern and we proceed as follows.
\begin{enumerate}
\item Let $w^{0}=w(d)$ and let $m=0$.
\item Let $i w^{m}_\ell$.
\item Let $w^{m+1}$ be the word formed by adding $\max(w^{m}_1 \dotsm w^{m}_{k-1})+1-w^m_{k}$ to each digit of $w^{m}_{k} w^{m}_{k+1} \dotsm w^{m}_{\ell-1}$. Also let $w^{m+1}_{i} = w^{m}_{i}$ for $i\ell$. Since $w^{m+1}_\ell < w^{m+1}_c$, every intermediate value must appear since $w^{m+1}_\ell w^{m+1}_{\ell} \dotsm w^{m+1}_c = w_\ell w_{\ell} \dotsm w_c$ which satisfies Property (1). Therefore there must be a digit with the same value as $w^{m+1}_b$ appearing before $w^{m+1}_c$, which would create a 100 before a 101. % (RRR: There has got to be a better way of doing this argument, but I just can't get it right.)
Observe that if $x=\phi(d)$ has letters $x_i$ and $x_{i+1}$ so that $x_{i}+1< x_{i+1}$, then a lift must have taken place that affected the $(i+1)^{th}$ letter but not the $i^{th}$. This provides the key to the inverse mapping which acts as follows:
\begin{enumerate}
\item Given $x \in \mathcal{A}_{100,101}(n)$, let $\ell$ be the largest integer such that $x_{\ell-1}+1=triangle 45,x=1.0cm,y=1.0cm]
\clip(-6.46,2.48) rectangle (8.52,6.4);
\draw (0,6)-- (-4,5);
\draw (-4,5)-- (-5,4);
\draw (-4,5)-- (-2,4);
\draw (0,6)-- (4,5);
\draw (4,5)-- (1,4);
\draw (4,5)-- (3,4);
\draw (4,5)-- (5,4);
\draw (-5,4)-- (-5.76,3);
\draw (-5,4)-- (-4.44,3);
\draw (-2,4)-- (-3.2,3);
\draw (-2,4)-- (-2,3);
\draw (-2,4)-- (-1,3);
\draw (1,4)-- (0.16,3);
\draw (1,4)-- (0.7,3);
\draw (1,4)-- (1.48,3);
\draw (3,4)-- (2.46,3);
\draw (3,4)-- (3,3);
\draw (3,4)-- (3.58,3);
\draw (5,4)-- (4.76,3);
\draw (5,4)-- (5.48,3);
\draw (5,4)-- (6.3,3);
\draw (5,4)-- (7.16,3);
\begin{scriptsize}
\fill [color=black] (0,6) circle (1.5pt);
\draw[color=black] (0,6.2) node {$0$};
\fill [color=black] (-4,5) circle (1.5pt);
\draw[color=black] (-4,5.28) node {$00$};
\fill [color=black] (4,5) circle (1.5pt);
\draw[color=black] (4,5.28) node {$01$};
\fill [color=black] (-5,4) circle (1.5pt);
\draw[color=black] (-5,4.28) node {$000$};
\fill [color=black] (-2,4) circle (1.5pt);
\draw[color=black] (-2,4.28) node {$001$};
\fill [color=black] (1,4) circle (1.5pt);
\draw[color=black] (1,4.28) node {$010$};
\fill [color=black] (3,4) circle (1.5pt);
\draw[color=black] (3,4.28) node {$011$};
\fill [color=black] (5,4) circle (1.5pt);
\draw[color=black] (5,4.28) node {$012$};
\fill [color=black] (-5.76,3) circle (1.5pt);
\draw[color=black] (-5.76,2.8) node {$0000$};
\fill [color=black] (-4.44,3) circle (1.5pt);
\draw[color=black] (-4.44,2.8) node {$0001$};
\fill [color=black] (-3.2,3) circle (1.5pt);
\draw[color=black] (-3.2,2.8) node {$0010$};
\fill [color=black] (-2,3) circle (1.5pt);
\draw[color=black] (-2,2.8) node {$0011$};
\fill [color=black] (-1,3) circle (1.5pt);
\draw[color=black] (-1,2.8) node {$0012$};
\fill [color=black] (0.16,3) circle (1.5pt);
\draw[color=black] (0.1,2.8) node {$0100$};
\fill [color=black] (0.7,3) circle (1.5pt);
\draw[color=black] (0.76,2.8) node {$0101$};
\fill [color=black] (1.48,3) circle (1.5pt);
\draw[color=black] (1.48,2.8) node {$0102$};
\fill [color=black] (2.46,3) circle (1.5pt);
\draw[color=black] (2.3,2.8) node {$0110$};
\fill [color=black] (3,3) circle (1.5pt);
\draw[color=black] (3,2.8) node {$0111$};
\fill [color=black] (3.58,3) circle (1.5pt);
\draw[color=black] (3.63,2.8) node {$0112$};
\fill [color=black] (4.76,3) circle (1.5pt);
\draw[color=black] (4.76,2.8) node {$0120$};
\fill [color=black] (5.48,3) circle (1.5pt);
\draw[color=black] (5.48,2.8) node {$0121$};
\fill [color=black] (6.3,3) circle (1.5pt);
\draw[color=black] (6.3,2.8) node {$0122$};
\fill [color=black] (7.16,3) circle (1.5pt);
\draw[color=black] (7.16,2.8) node {$0123$};
\end{scriptsize}
\end{tikzpicture}
\end{center}
\caption{Tree of ascent sequences}
\label{fig:treeall}
\end{figure}
An important observation in the subsequent proofs is that consecutive copies of the same value beyond the first have no effect on pattern containment for patterns without repeated letters. Formally, if $x$ can be decomposed into $x=X aa\dotsm a Y$, and $p$ is a pattern without consecutive repeated letters, then $x$ contains $p$ if and only if $XaY$ contains $p$. It follows then that the same letters may be appended to $X aa\dotsm a Y$ and $XaY$, and so these two ascent sequences have sets of children with the same multiset of labels. We summarize these observations in a lemma:
\begin{lemma}\label{gtlem}
For ascent sequences $ x = X aa\dotsm a Y$ and $x' = X a Y$ avoiding a pattern $p$ without consecutive repeated letters, the ascent sequence $xb$ is a child of $x$ if and only if $x'b$ is a child of $x'$ for any $b\geq 0$. In terms of generating trees, $x$ and $x'$ may be given the same label since they produce isomorphic sets of children.
\end{lemma}
\begin{prop}\label{perm1}
$\mathrm{a}_{021,102}(n) = 3\cdot2^{n-1}-\binom{n+1}{2}-1$. Equivalently, $\mathcal{A}_{021,102}(n)$ is in bijection with the set of permutations of length $n$ avoiding 123 and 3241.
\end{prop}
\begin{proof}
First note that avoiding 102 implies all ascent sequences will be RGFs by \cite{DS11}. Therefore any letter appended to $x$ may be at most $\max(x)+1$.
Members of $\mathcal{A}_{021,102}(n)$ can be generated using a generating tree with precisely 5 labels: (0),(01), (010), (012), and (0120). We have the following root label and succession rules.
\begin{itemize}
\item Root: (0)
\item Rules:
\begin{itemize}
\item $(0) \leadsto (0)(01)$
\item $(01) \leadsto (01)(010)(012)$
\item $(010) \leadsto (010)(010)$
\item $(012) \leadsto (0120)(012)(012)$
\item $(0120) \leadsto (0120)$
\end{itemize}
\end{itemize}
We now justify each succession rule in turn.
$(0) \leadsto (0)(01)$: We first consider the root $0$, which we label as $(0)$. This root has two children, $00$ and $01$. By Lemma \ref{gtlem}, any all-zero ascent sequence will have an isomorphic set of children and so we label any all-zero ascent sequence with (0) (and only the all-zero sequences get this label). Label the other child of an all-zero sequence (01).
$(01) \leadsto (01)(010)(012)$: The first appearance of the (01) label is the ascent sequence 01, which has children 010, 011, and 012. Again by Lemma \ref{gtlem} we may label 011 with (01) because of the repeated 1. Note that any ascent sequence with form $0\dotsm0 1\dotsm1$ has label (01) and no others. Label 010 with (010) and 012 with (012), and the rule follows.
$(010) \leadsto (010)(010)$: Without considering pattern avoidance, the ascent sequence 010 has children 0100, 0101, and 0102. However, 0102 contains the forbidden pattern 102, so this branch is pruned. More broadly, if an ascent sequence contains a 010 pattern, no digits larger than 1 may be appended in order to avoid 102. On the other hand, as many copies of 0 or 1 as we like may appear in the rest of the ascent sequence, so each ascent sequence starting with 010 has precisely two children: one where 0 is appended and one where 1 is appended since neither will produce a 021 nor 102. Each of these children is given the label (010). In this way, the label (010) is applied only to ascent sequences containing a 010 and consisting of only 0s and 1s.
$(012) \leadsto (0120)(012)(012)$: The first instance of the (012) is the ascent sequence 012, which has children 0120, 0121, 0122, and 0123 when ignoring pattern avoidance. However, 0121 contains the forbidden pattern 021, so this branch is pruned. Label 0120 with (0120) and 0122 may be labeled with (012) by Lemma \ref{gtlem}. The sequence 0123 may also be labeled (012) since it has an isomorphic set of children as 012: the only letters which may be added are 0, a copy of the last letter, or one more than the last letter. It follows that any ascent sequence $x_1 \dotsm x_n$ labeled with (012) will be weakly increasing and its 021-avoiding children will be $x_1\dotsm x_n 0$, $x_1\dotsm x_n x_n$ and $x_1\dotsm x_n (x_{n}+1)$ which get labels (0120), (012) and (012) respectively.
$(0120) \leadsto (0120)$: The children of 0120 are 01200, 01201, 01202, and 01203 when ignoring pattern avoidance. All but 01200 contain some forbidden patterns, however. More broadly, if an ascent sequence in this tree contains a $0120$ pattern then that pattern must be a literal 0120 and so only a 0 may be appended. Since this child also contains a 0120 we give it the label (0120) as well.
%\textcolor{red}{Referee comment \#2 asked for a transfer matrix method example. The following paragraph was inserted to illustrate. What do you think?}
%\textcolor{blue}{
Finally, we use the transfer matrix method to obtain a closed form for the generating function $f_{021,102}(z) = \sum_{n \geq 0} \mathrm{a}_{021,102}(n) z^n$. We have 5 labels in our generating tree, and we make a $6 \times 6$ production matrix $P$. We associate columns 2 through 6 and rows 2 through 6 with the labels (0), (01), (010), (012), and (0120) respectively. For $2 \leq i, j, \leq 6$, let $P_{i,j}$ be the number of nodes of label $j$ that are children of a node of label $i$. Also, we let the first row have a 1 in column 2 to account for the root, (0). The production matrix that results from our generating tree rules is $$P =\left[\begin{array}{cccccc}0&1&0&0&0&0\\0&1&1&0&0&0\\0&0&1&1&1&0\\0&0&0&2&0&0\\0&0&0&0&2&1\\0&0&0&0&0&1 \end{array}\right].$$ By construction the $j$th entry in the first row of $P^n$ is the number of nodes of type $j$ at the $n$th level of the generating tree, so $\mathrm{a}_{012,102}(n)= (P^n)_{1,2}+(P^n)_{1,3}+(P^n)_{1,4}+(P^n)_{1,5}+(P^n)_{1,6}$. It follows that $f_{021,102}(z) = u (I-zP)^{-1} e$, where $u$ is the row vector $u=\left[\begin{array}{cccccc}1&0&0&0&0&0\end{array}\right]$ and $e$ is a column vector consisting of six 1s. This calculation yields the closed form $f_{021,102}(z) = \frac{z^4-3z^3+6z^2-4z+1}{(z-1)^3(2z-1)}$, from which we deduce the desired enumeration for $n \geq 1$ by the standard methods.
%} XXX: I rephrased the last sentence slightly, but otherwise great.
Using the Maple package \texttt{FINLABEL} in \cite{V06} we see that permutations avoiding $\{123,3241\}$ admit an 8-label generating tree, which has the same enumeration. Although we have showed the cardinality of the ascent sequence set and the permutation set are the same, it remains an open problem to find a direct combinatorial bijection between them since the generating trees have differing numbers of labels.
\end{proof}
In the next two propositions we will employ similar methods and omit some of the details. Unlike the generating tree of Proposition \ref{perm1}, the generating trees in Propositions \ref{perm2} and \ref{perm3} are isomorphic to the corresponding trees for pattern-avoiding permutations and so the proofs may be translated into bijections between the two sets.
%\textcolor{red}{XXX: MS comments on Proposition 13 as follows. This is equivalent to the number of set-partitions-as-RGFs avoiding (1213, 1231). This is done in the last section of V. Jelinek, T. Mansour, and M. Shattuck, On multiple pattern
%avoiding set partitions, Adv. in Appl. Math. 50 (2013), pp. 292-326. In particular this is Example 4.16 where they provide an algebraic proof and the generating function. Ours is more combinatorial.
%}
%\textcolor{brown}{XXX: see proposed paragraph to address this below.}
\begin{prop}\label{perm2}
$\mathrm{a}_{102,120}(n) = (n-1)\,2^{n-2}+1$. Equivalently, $\mathcal{A}_{102,120}(n)$ is in bijection with the set of permutations of length $n$ avoiding 132 and 4312.
\end{prop}
%\textcolor{brown}{
By Lemma \ref{RGFlemma}, since 102 is a subpattern of 01012, $\mathcal{A}_{102,120}(n)$ is in bijection with set partitions avoiding the patterns 1213 and 1231. In Example 4.16 of \cite{JMS13}, Jelinek, Mansour, and Shattuck provide an algebraic proof of Proposition \ref{perm2} in this context of set partitions. While the result is known, this is the first proof that can be considered combinatorial.
%}
\begin{proof}
As noted in the preceding paragraph, avoiding 102 implies all ascent sequences are RGFs by Lemma \ref{RGFlemma}. Therefore any letter appended to $x$ may be at most $\max(x)+1$.
Members of $\mathcal{A}_{102,120}(n)$ can be generated using a generating tree with precisely 3 labels: (0),(01), and (010). We have the following root label and succession rules.
\begin{itemize}
\item Root: (0)
\item Rules:
\begin{itemize}
\item $(0) \leadsto (0)(01)$
\item $(01) \leadsto (01)(01)(010)$
\item $(010) \leadsto (010)(010)$
\end{itemize}
\end{itemize}
In this case we can state simply how labels are applied to ascent sequences. Any all-zero sequence gets the label (0) and any other weakly increasing sequence will have the label (01). All others, which each contain a 010 pattern, get label (010). We now justify each succession rule in turn.
$(0) \leadsto (0)(01)$: This is by the same argument as in the proof of Proposition \ref{perm1}.
$(01) \leadsto (01)(01)(010)$: The first appearance of the label (01) is the ascent sequence 01. Without considering pattern-avoidance, 01 has children 010, 011, and 012. By Lemma \ref{gtlem} we may label 011 as (01) as well, and we choose to label 010 with (010). Further, because of the ascent 12 in 012, we may have no more copies of 0 in the rest of the ascent sequence (lest we have a copy of $120$), and so the minimum for the next appended letter(s) increases to 1. Therefore $012$ may be labeled the same as 011, namely (01) without loss of significant information. Following this same logic, any weakly increasing sequence gets labeled with a (01) and is the child of a node with label either (0) or (01).
$(010) \leadsto (010)(010)$: Ignoring pattern avoidance, the children of 010 are 0100, 0101, and 0102. However, $0102$ contains the forbidden pattern 102 so that branch is pruned. Lemma \ref{gtlem} implies 0100 can have the same label as 010. For 0101, the second 1 is also irrelevant to formation of new copies of 102 and 120 since if that second 1 were part of a forbidden pattern then the first 1 would also be part of a forbidden pattern. Therefore 0101 has the same options for children as 010. More broadly, if $x$ has label (010), then $x$ contains a 010 pattern at $x_i x_j x_k$ and so the only children which avoid 102 and 120 are additional copies of the values $x_i$ or $x_j$ and so should also be labeled (010) by the same reasoning.
Via the transfer matrix method, these rules give the ordinary generating function $\frac{x^3-5x^2+4z-1}{(x-1)(2x-1)^2}$, from which we deduce the desired enumeration for $n \geq 1$.
Using the Maple package \texttt{FINLABEL} \cite{V06} we see that permutations avoiding $\{132, 4312\}$, or equivalently, their inverses $\{132,3421\}$ admit an isomorphic generating tree, and thus have the same enumeration. Details of the implied bijection are left to the reader.
\end{proof}
\begin{prop}\label{perm3}
$\mathcal{A}_{101,120}(n)$ is in bijection with the set of permutations of length $n$ avoiding 231 and 4123.
\end{prop}
\begin{proof}
First note that avoiding 101 implies all ascent sequences will be RGFs by \cite{DS11}. Therefore any letter appended to $x$ may be at most $\max(x)+1$.
Members of $\mathcal{A}_{101,120}(n)$ can be generated using a generating tree with precisely 4 labels: (0),(01),(010), and (0102). We have the following root label and succession rules.
\begin{itemize}
\item Root: (0)
\item Rules:
\begin{itemize}
\item $(0) \leadsto (0)(01)$
\item $(01) \leadsto (01)(01)(010)$
\item $(010) \leadsto (010)(0102)$
\item $(0102) \leadsto (01)(0102)$
\end{itemize}
\end{itemize}
We now justify each succession rule in turn.
$(0) \leadsto (0)(01)$: This reasoning is the same as in the previous two propositions. The ascent sequences with label (0) are exactly the all-zero sequences.
$(01) \leadsto (01)(01)(010)$: The ascent sequence 01 has children 010, 011, and 012. The first of these gets label (010). As we have seen previously, 011 may be labeled as (01) by Lemma \ref{gtlem}. As in the proof of Proposition \ref{perm2}, avoiding 120 means that 012 may be labeled with (01) since the minimum for appended letters is raised. More broadly, if $x=x_1\dots x_n$ has label (01), let $m$ be the first letter of the last ascent in $x$ or $0$ if there is no ascent. Then the only children are $xm$, $x x_n$, and $x (x_{n}+1)$, which get labels (010), (01), and (01) respectively.
$(010) \leadsto (010)(0102)$: The ascent sequence 010 has children 0100, 0101, and 0102, but 0101 has the forbidden pattern 101 and is therefore pruned. Lemma \ref{gtlem} implies 0100 can be labeled as its parent (010), and 0102 gets the new label (0102). More broadly any ascent sequence $x$ with label (010) allows for two children: repeating the last letter or appending a letter larger than all letters in $x$. These children get labels (010) and (0102) respectively.
$(0102) \leadsto (01)(0102)$: The ascent sequence 0102 has children 01020, 01021, 01022, and 01023, but the first two of these contain forbidden patterns. Lemma \ref{gtlem} implies 01022 may be labeled as its parent. For 01023, the first three letters become irrelevant because no more copies of 0 or 1 may appear lest we create a 120 pattern. Therefore the minimum for new letters is raised and only the subsequence 23 matters for the sake of pattern avoidance. Thus we label 01023 according to this pattern, (01). More broadly any ascent sequence $x$ with label (0102) allows for two children: repeating the last letter or appending $\max(x)+1$. These children get labels (0102) and (01) respectively.
Via the transfer matrix method, these rules give the ordinary generating function $\frac{(x-1)^3}{3x^3-5x^2+4x-1}$. Using the Maple package \texttt{FINLABEL} in \cite{V06} we see that permutations avoiding $\{231,4123\}$ admit an isomorphic generating tree, and thus have the same enumeration.
\end{proof}
We close this section with an additional generating tree argument, although of a very different structure than the preceding propositions.
%\textcolor{red}{XXX: Comments from MS are as follows. This is equivalent to counting set-parititions-as-RGFs avoiding (1212, 1221). This appears as the x=q=1 case of Proposition 3.6 in T. Mansour and M. Shattuck, Free rises, restricted partitions, and
%q-Fibonacci polynomials, Afr. Matematika 24:3 (2013), pp. 305-320. They prove a refined version that specializes to $a_n=3a_{n-1}-a_{n-2}$. They track according to two statistics: (1) the sum of i-1 over all indices i where ltrmaxes appear and (2) the largest letter appearing. Their methods take on the same flavor: they consider adding 1 letter near the end (either last or second-to-last) in three ways. We could drop this proof entirely and just go with citing theirs. The only thing ours has to add is the connection to A121461, a number triangle in OEIS counting nondecreasing Dyck paths.}
%\textcolor{brown}{XXX: path 1: Delete the proof. Path 2, see the inserted brown paragraph below.}
\begin{prop}\label{bifib}
$\mathrm{a}_{101,110}(n)=F_{2n-1}$
\end{prop}
%\textcolor{brown}{
This result first appeared as the $x=q=1$ case of Proposition 3.6 in \cite{MS13}. There, Mansour and Shattuck track ascent sequences according to two statistics based on indices of left-to-right maxima and the value of the largest letter. Our methods are similar, but are included to point out an interesting combinatorial connection to a refinement of the bisection of the Fibonacci numbers in the OEIS \cite{OEIS}.
%}
\begin{proof}
We will construct a generating tree more typical of those in the literature: each ascent sequences is labeled by its number of children. Thus a node with label $(k)$ has $k$ children. In the end we will need to use infinitely many labels, but still be able to arrive at a simple formula.
First note that avoiding 101 implies all ascent sequences will be RGFs by Lemma \ref{RGFlemma}. Therefore any letter appended to $x$ may be at most $\max(x)+1$.
We see that the ascent sequence 0 has two children that avoid our given patterns, namely 00 and 01. 00 has 2 children that avoid our given patterns, 000 and 001. 01 has 3 children that avoid our given patterns, 010, 011, and 012.
In general, suppose that $x=x_1\dotsm x_n$ is in $\mathcal{A}_{101,110}(n)$ and has $k$ children that avoid our given patterns. There are 3 cases to consider for a child $xz$ by appending digit $z$ to the end of $x$: (a) $z>x_n$, (b) $z=x_n$, or (c) $zx_n$, there is precisely one choice for $z$, $z = max(x)+1$, since $x$ is an RGF. Further, this child $xz$ has one more child than $x$ does, since any digit that could have been appended to $x$ can still be appended to $xz$ without creating a forbidden pattern, and we could also append $z+1$. Therefore if $x$ has label $(k)$, then this particular child has label $(k+1)$.
If $z=x_n$, then $z$ is determined uniquely. As for the children of $xz$, we cannot use any digit less than $z$ later in the construction of the ascent sequence (lest we form a 110 pattern), so $xz$ has precisely two children, $xzz$ and $xz(\max(x)+1)$, and should receive the label $(2)$.
If $zn+1 \\
\end{cases}
\end{equation}
Values of $b(n,k)$ for small $n$ and $k$ appear in Table \ref{tab:fibtri}.
\begin{table}
\begin{center}
\begin{tabular}{c|ccccc || c}
$n$~\textbackslash ~$k$ & 2 & 3& 4& 5& 6 & Row sum\\
\hline
1 & 1 & 0 & 0 & 0 & 0 & 1\\
2 & 1 & 1 & 0 & 0 & 0 & 2\\
3 & 3 & 1 & 1 & 0 & 0 & 5\\
4 & 8 & 3 & 1 & 1 & 0 & 13\\
5 & 21 & 8 & 3 & 1 & 1 & 34\\
\end{tabular}
\end{center}
\caption{Values of $b(n,k)$, the number of nodes of the generating tree for $\mathcal{A}_{101, 110}$ on level $n$ with label $(k)$.}
\label{tab:fibtri}
\end{table}
Our result that $\mathrm{a}_{101,110}(n)=F_{2n-1}$ follows from equation \eqref{eqn:fibtri} and the easily-proven identity
\begin{equation}\label{eqn:fibid}
F_{2n-1} = F_{2n-2} + F_{2n-4} + F_{2n-6} + \dotsm F_{2} + 1.
\end{equation}
Computation verifies the values for $b(n,k)$ for small $n$ and $k$. Level 1 has only the node (2), corresponding to the ascent sequence $0$, and so $b(1,2)=1$ and $b(1,k)=0$ for any $k\neq 2$. Level 2 corresponds to the ascent sequences 00 and 01, whose corresponding nodes are labeled (2) and (3) respectively and thus $b(2,2)=F_2=1$ and $b(2,3)=1$.
%For induction assume that the number of nodes on level $m$ is $F_{2m-1}$ for $m*