# Difference ascent sequences

Mark Dukes
School of Mathematics and Statistics, University College Dublin,
Belfield, Dublin 4, Ireland<EMAIL_ADDRESS>
Bruce E. Sagan
Department of Mathematics, Michigan State University,
East Lansing, MI 48824-1027, USA<EMAIL_ADDRESS>
(
Key Words: ascent sequence, bivincular pattern, factorial poset, matching,
nonnegative integer matrix, restricted growth function, rooted duplication
tree, weak ascent sequence
AMS subject classification (2020): 05A19 (Primary) 05A05, 06A07 (Secondary) )

###### Abstract

Let $\alpha=a_{1}a_{2}\ldots a_{n}$ be a sequence of nonnegative integers. The
ascent set of $\alpha$, $\operatorname{Asc}\alpha$, consists of all indices
$k$ where $a_{k+1}>a_{k}$. An ascent sequence is $\alpha$ where the growth of
the $a_{k}$ is bounded by the elements of $\operatorname{Asc}\alpha$. These
sequences were introduced by Bousquet-Mélou, Claesson, Dukes and Kitaev and
have many wonderful properties. In particular, they are in bijection with
unlabeled $(2+2)$-free posets, permutations avoiding a particular bivincular
pattern, certain upper-triangular nonnegative integer matrices, and a class of
matchings. A weak ascent of $\alpha$ is an index $k$ with $a_{k+1}\geq a_{k}$
and weak ascent sequences are defined analogously to ascent sequences. These
were studied by Bényi, Claesson and Dukes and shown to have analogous
equinumerous sets. Given a nonnegative integer $d$, we define a difference $d$
ascent to be an index $k$ such that $a_{k+1}>a_{k}-d$. We study the properties
of the corresponding $d$-ascent sequences, showing that some of the maps from
the weak case can be extended to bijections for general $d$ while the
extensions of others continue to be injective (but not surjective). We also
make connections with other combinatorial objects such as rooted duplication
trees and restricted growth functions.

##  1 Introduction

For $m,n$ nonnegative integers we let $[m,n]=\\{m,m+1,\ldots,n\\}$, and when
$m=1$ we abbreviate this to $[n]=\\{1,2,\ldots,n\\}$. Note that
$[n]=\emptyset$ if $n=0$. Consider a sequence $\alpha=a_{1}a_{2}\ldots a_{n}$
of nonnegative integers. We will sometimes put commas between the $a_{k}$ for
readability. Also note our convention that we will use Greek letters for
sequences and the corresponding roman letters for their elements. For
$k\in[n]$ we will use

$\alpha_{k}=a_{1}a_{2}\ldots a_{k}$

for the prefix of $\alpha$ with $k$ elements and also let
$\alpha_{0}=\emptyset$ be the empty sequence. The ascent set and ascent number
of $\alpha$ are

$\operatorname{Asc}\alpha=\\{k\in[n-1]\mid a_{k+1}>a_{k}\\}$

and

$\operatorname{asc}\alpha=\\#\operatorname{Asc}\alpha,$

respectively, where we will use a hash symbol or a pair of vertical bars to
denote cardinality. For example, if

$\alpha=0,1,1,0,2,1,2,4$ (1)

then $\operatorname{Asc}\alpha=\\{1,4,6,7\\}$ and
$\operatorname{asc}\alpha=4$. Call $\alpha$ an ascent sequence if

  1. (a1)

$a_{1}=0$, and

  2. (a2)

$a_{k+1}\leq 1+\operatorname{asc}\alpha_{k}$ for $k\in[n-1]$.

It is easy to check that $\alpha$ in the previous example is an ascent
sequence while

$\alpha^{\prime}=0,1,1,0,3,1,2,4$ (2)

is not because $\alpha^{\prime}_{5}=3$ while $1+\operatorname{asc}(0,1,1,0)=2$
which is smaller. For $n\geq 0$ we will use the notation

$\operatorname{A}_{n}=\\{\alpha=a_{1}a_{2}\ldots a_{n}\mid\text{$\alpha$ is an
ascent sequence}\\}.$

For example

$\operatorname{A}_{3}=\\{000,001,010,011,012\\}.$

Bousquet-Mélou, Claesson, Dukes and Kitaev [BMCDK10] were the first to define
and study ascent sequences and they have since been considered by numerous
authors such as [CDD+13, CCEPG22, CCEPG22, CDK11, CL11, Duk16, DM19, DP10,
DS11, FJL+20, JS23, LF21, MS14, Pud16, Yan18]. Ascent sequences are known to
be in bijection with unlabeled $(2+2)$-free posets, permutations avoiding a
bivincular pattern of length $3$, certain upper-triangular nonnegative integer
matrices, and a class of matchings.

Very recently, Bényi, Claesson, and Dukes [BCD23] introduced weak ascent
sequences. The set of weak ascents of $\alpha$ is

$\operatorname{wAsc}\alpha=\\{k\in[n-1]\mid a_{k+1}\geq a_{k}\\}$

with corresponding weak ascent number

$\operatorname{wasc}\alpha=\\#\operatorname{wAsc}\alpha.$

Note that $\operatorname{wAsc}\alpha\supseteq\operatorname{Asc}\alpha$. Taking
$\alpha^{\prime}$ as in (2) we see that
$\operatorname{wAsc}\alpha^{\prime}=\\{1,2,4,6,7\\}$. The sequence $\alpha$ is
a weak ascent sequence if

  1. (w1)

$a_{1}=0$, and

  2. (w2)

$a_{k+1}\leq 1+\operatorname{wasc}\alpha_{k}$ for $k\in[n-1]$.

Even though $\alpha^{\prime}$ as above was not an ascent sequence, it is a
weak ascent sequence. In fact, if we let

$\operatorname{wA}_{n}=\\{\alpha=a_{1}a_{2}\ldots a_{n}\mid\text{$\alpha$ is a
weak ascent sequence}\\}.$

then clearly $\operatorname{wA}_{n}\supseteq\operatorname{A}_{n}$ for all
$n\geq 0$. As an example,

$\operatorname{wA}_{3}=\\{000,001,002,010,011,012\\}.$

In [BCD23] the authors showed that weak ascent sequences are equinumerous with
factorial posets avoiding a specially labeled $3+1$, permutations avoiding a
bivincular pattern of length $4$, upper-triangular $0$-$1$ matrices satisfying
a column restriction, and matchings with a restriction on their nestings.

The purpose of the present work is to introduce and study a more general class
of sequences which includes both ascent sequences and weak ascent sequences as
special cases. For $d\geq 0$ the difference $d$ ascent set or simply
$d$-ascent set of $\alpha$ is

$\operatorname{dAsc}\alpha=\\{k\in[n-1]\mid a_{k+1}>a_{k}-d\\}.$

with corresponding $d$-ascent number

$\operatorname{dasc}\alpha=\\#\operatorname{dAsc}\alpha.$

Note that when $d=0$ and $d=1$ we have
$\operatorname{dAsc}\alpha=\operatorname{Asc}\alpha$ and
$\operatorname{dAsc}\alpha=\operatorname{wAsc}\alpha$, respectively. For
example, when $d=2$ we have

$\operatorname{dAsc}(0,1,0,2,3,1,4,1,7)=\\{1,2,3,4,5,6,8\\}.$

Unsurprisingly, the definition of a $d$-ascent sequence $\alpha$ is one where

  1. (d1)

$a_{1}=0$, and

  2. (d2)

$a_{k+1}\leq 1+\operatorname{dasc}\alpha_{k}$ for $k\in[n-1]$.

The example sequence just given is a $2$-ascent sequence. Let

$\operatorname{dA}_{n}=\\{\alpha=a_{1}a_{2}\ldots a_{n}\mid\text{$\alpha$ is a
$d$-ascent sequence}\\}.$

These difference $d$ ascent sequences are different from the $p$-ascent
sequences that were introduced by Kiteav and Remmel [KR17]. In what follows,
we will continue the convention initiated above using notation starting with
$d$ for notions concerning general $d$-ascent sequences, with $w$ for the
corresponding ideas applied to weak ascent sequences, and with no added
initial letter for the ascent sequence case. Sometimes the $d=2$ sequences
will be of special interest and then the prefix will be t as in
$\operatorname{tAsc}\alpha$.

The rest of this paper is structured as follows. In the next section we will
give a bijection between $d$-ascent sequence and upper triangular $0$-$1$
matrices satisfying a condition on the columns. This is a generalization of
the map given in Bényi et al. [BCD23, Sec. 3] for the case of weak ascent
sequences. Section 3 is devoted to a bijection between $\operatorname{dA}_{n}$
and a set of matchings with restricted nestings. In Section 4 we show that
there is an injection from $d$-ascent sequence to permutations avoiding a
bivincular pattern of length $d+3$. Next, we construct another injection with
domain $\operatorname{dA}_{n}$ for $d\geq 1$, this one to the factorial posets
of Claesson and Linusson [CL11] avoiding a specially labeled poset $P_{d+3}$
with $d+3$ elements. Call a $d$-ascent sequence $d$-increasing if every index
(except the last) is a $d$-ascent. In Section 6 we show that there is an
alternating sum recursion of such sequences. Also, for $d=2$, they are in
bijection with the rooted duplication trees of Gasceul, Hendy, Jean-Marie, and
McLachlan [GHJMM03]. The special factorial posets considered earlier were for
$d\geq 1$, but one can also define an analogous $P_{3}$. We show in Section 7
that the factorial posets avoiding $P_{3}$ are in bijection with restricted
growth functions. We end with a section of comments and suggestions for future
work.

##  2 Matrices

We will now give a bijection between difference $d$ ascent sequences and
matrices satisfying a certain column condition. Our map is a simplification
and generalization of the one for weak ascent sequences given in [BCD23].

$\begin{array}[]{rc}M=&\left[\begin{array}[]{ccccc}1&0&1&1&1\\\ 0&1&0&0&0\\\
0&0&0&0&1\\\ 0&0&0&1&0\\\ 0&0&0&0&1\end{array}\right]\\\ \\\
\begin{array}[]{r}j:\\\ \operatorname{rmin}c_{j}:\\\
\operatorname{rmax}c_{j}:\end{array}&\begin{array}[]{ccccc}0&1&2&3&4\\\
0&1&0&0&0\\\ 0&1&0&3&4\end{array}\end{array}$ Figure 1: A matrix $M$ with its
$\operatorname{rmin}c_{j}$ and $\operatorname{rmax}c_{j}$ values

It will be convenient to index the rows and columns of our matrices by
$0,1,\ldots,m$ for some $m\geq-1$ where $m=-1$ corresponds to the empty
matrix. In particular, we let $Z_{m}$ be the matrix with these coordinates
which has all entries zero. Figure 1 shows a matrix $M$ with rows and columns
indexed by $[0,4]$. We also let $E_{i,j}$ be the matrix whose only nonzero
entry is a one in position $(i,j)$. Note that we do not specify the dimensions
of $E_{i,j}$ but instead choose them to be consistent with the dimensions of
the other matrices involved in a given computation. Given any matrix $M$ we
let $c_{j}$ be the column vector consisting of its $j$th column. If $c_{j}$ is
not the zero vector then we define $\operatorname{rmin}c_{j}$ and
$\operatorname{rmax}c_{j}$ to be the smallest and largest row coordinates,
respectively, of a nonzero entry in $c_{j}$. For the matrix in Figure 1 the
$\operatorname{rmin}c_{j}$ and $\operatorname{rmax}c_{j}$ values are listed
above each column $c_{j}$.

If $d\geq 1$ then a $d$-matrix is a $[0,m]\times[0,m]$ matrix $M$ having the
following properties.

  1. (M1)

$M$ is upper triangular with entries $0$ and $1$.

  2. (M2)

Between any two ones in the same column there are at least $d-1$ zeros.

  3. (M3)

There are no zero columns and for all $j\in[m]$ we have

$\operatorname{rmax}c_{j}>\operatorname{rmin}c_{j-1}-d.$

For $n\geq 0$ let

$\operatorname{dMtx}_{n}=\\{M\mid\text{$M$ is a $d$-matrix having $n$
ones}\\}.$

It is easy to check that the matrix in Figure 1 is in
$\operatorname{dMtx}_{8}$ for $d=2$.

$\begin{array}[]{l}\begin{array}[]{cccccc}\left[\begin{array}[]{ccccc}0&0&0&0&0\\\
0&0&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&0&0\end{array}\right]&&\left[\begin{array}[]{ccccc}1&0&0&0&0\\\
0&0&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&0&0\end{array}\right]&&\left[\begin{array}[]{ccccc}1&0&0&0&0\\\
0&1&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&0&0\end{array}\right]\\\
M_{0}&+E_{0,0}&M_{1}&+E_{1,1}&M_{2}&+E_{0,2}\end{array}\\\ \\\
\begin{array}[]{cccccc}\left[\begin{array}[]{ccccc}1&0&1&0&0\\\ 0&1&0&0&0\\\
0&0&0&0&0\\\ 0&0&0&0&0\\\
0&0&0&0&0\end{array}\right]&&\left[\begin{array}[]{ccccc}1&0&1&0&0\\\
0&1&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&1&0\\\
0&0&0&0&0\end{array}\right]&&\left[\begin{array}[]{ccccc}1&0&1&1&0\\\
0&1&0&0&0\\\ 0&0&0&0&0\\\ 0&0&0&1&0\\\ 0&0&0&0&0\end{array}\right]\\\
M_{3}&+E_{3,3}&M_{4}&+E_{0,3}&M_{5}&+E_{4,4}\end{array}\\\ \\\
\begin{array}[]{cccccc}\left[\begin{array}[]{ccccc}1&0&1&1&0\\\ 0&1&0&0&0\\\
0&0&0&0&0\\\ 0&0&0&1&0\\\
0&0&0&0&1\end{array}\right]&&\left[\begin{array}[]{ccccc}1&0&1&1&0\\\
0&1&0&0&0\\\ 0&0&0&0&1\\\ 0&0&0&1&0\\\
0&0&0&0&1\end{array}\right]&&\left[\begin{array}[]{ccccc}1&0&1&1&1\\\
0&1&0&0&0\\\ 0&0&0&0&1\\\ 0&0&0&1&0\\\ 0&0&0&0&1\end{array}\right]\\\
M_{6}&+E_{4,2}&M_{7}&+E_{4,0}&M_{8}=\operatorname{mx}(\alpha)\end{array}\end{array}$
Figure 2: Computing $\operatorname{mx}(0,1,0,3,0,4,2,0)$

In order to construct our bijection
$\operatorname{mx}:\operatorname{dA}_{n}\rightarrow\operatorname{dMtx}_{n}$ we
will need a certain factorization of $d$-ascent sequences. Given
$\alpha=a_{1}a_{2}\ldots a_{n}\in\operatorname{dA}_{n}$, its $d$-ascent
factorization is the concatenation

$\alpha=\delta_{0}\delta_{1}\ldots\delta_{m},$ (3)

where the factors $\delta_{i}$ are obtained by dividing $\alpha$ after each
$d$-ascent. Equivalently, the $\delta_{i}$ are the maximal factors of $\alpha$
containing no $d$-ascent. Note that we start our indexing of the factors with
$0$. For example, if $d=2$ then $\alpha=0,1,0,3,0,4,2,0$ has factorization

$\alpha=0\cdot 1\cdot 0\cdot 3,0\cdot 4,2,0.$

where the centered dots separate the factors. Equivalently

$\delta_{0}=0,\ \delta_{1}=1,\ \delta_{2}=0,\ \delta_{3}=3,0,\text{ and
}\delta_{4}=4,2,0.$

Now given $\alpha=a_{1}\ldots a_{n}\in\operatorname{dA}_{n}$ expressed as in
(3) we will apply the map $\operatorname{mx}$ as follows. Note that $m$ is the
last index in the factorization and $n=|\alpha|$. Construct a sequence of
matrices

$Z_{m}=M_{0},M_{1},\ldots,M_{n}=\operatorname{mx}(\alpha)$

where

$M_{k}=M_{k-1}+E_{a_{k},j}$ (4)

if $a_{k}$ is in the factor $\delta_{j}$. This construction applied to the
example $\alpha$ from the previous paragraph is shown in Figure 2, where each
matrix appears below its label.

######  Theorem 2.1.

For all $d\geq 1$ and $n\geq 0$ the map
$\operatorname{mx}:\operatorname{dA}_{n}\rightarrow\operatorname{dMtx}_{n}$ is
a bijection. Consequently

$\\#\operatorname{dA}_{n}=\\#\operatorname{dMtx}_{n}.$

###### Proof.

We first prove that $\operatorname{mx}$ is well defined in that
$M_{n}\in\operatorname{dMtx}_{n}$. To ensure triangularity, we need to have
$a_{k}\leq j$ in equation (4). Since $a_{k}\in\delta_{j}$ and $\delta_{j}$ is
decreasing, it suffices to prove this inequality when $a_{k}$ is the first
element of $\delta_{j}$. But the assumption about $a_{k}$ and $\delta_{j}$
implies that the length $k-1$ prefix
$\alpha_{k-1}=\delta_{0}\delta_{1}\ldots\delta_{j-1}$. Now using the
definition of a $d$-ascent sequence yields

$a_{k}\leq\operatorname{dasc}\alpha_{k-1}+1=(j-1)+1=j.$

So the first half of condition (M1) holds

We now show simultaneously that (M2) and the second half of (M1) are true. If
the ones added for $a_{k}$ and $a_{k+1}$ are in the same column then we must
have both in the same $\delta_{j}$ for some $j$. Since $\delta_{j}$ has no
$d$-ascents, it must be that $a_{k+1}\leq a_{k}-d$. But since the elements of
$\alpha$ give the row indices for the added ones, there must be at least $d-1$
zeros between the ones corresponding to the $k$th and $(k+1)$st positions
which is (M2). Since $d\geq 1$ by assumption, we will never add two ones to
the same position which finishes the proof of (M1).

For condition (M3), since each $\delta_{j}$ has at least one element, there
are no zero columns. Also, we have $\operatorname{rmin}c_{j-1}=a_{k-1}$ and
$\operatorname{rmax}c_{j}=a_{k}$ where $a_{k-1}$ and $a_{k}$ are as in the
first paragraph. But then, by the definition of the factorization, there is a
$d$-ascent from $a_{k-1}$ to $a_{k}$ and so

$\operatorname{rmax}c_{j}=a_{k}>a_{k-1}-d=\operatorname{rmin}c_{j-1}-d.$

To complete the proof of being well defined, we need to know that
$\operatorname{mx}(\alpha)$ has exactly $n$ ones. But an $E_{i,j}$ was added
$n$ times and we already showed that $M_{n}$ is a $0$-$1$ matrix. So $n$ must
be the number of ones.

It is easy to construct a step-by-step inverse to $\operatorname{mx}$. It
follows that this map is bijective and so we are done. ∎

##  3 Matchings

We will construct our map between $\operatorname{dA}_{n}$ and certain
matchings by restricting a bijection of Claesson and Linusson [CL11] on
inversion sequences.

Call a sequence of nonnegative integers $\alpha=a_{1}a_{2}\ldots a_{n}$ an
inversion sequence if

$0\leq a_{k}<k$ (5)

for all $k\in[n]$. The name derives from the fact that such sequences are in
natural bijection with permutations in the symmetric group
${\mathfrak{S}}_{n}$ using the inversion statistic. Let

$\operatorname{I}_{n}=\\{\alpha=a_{1}a_{2}\ldots a_{n}\mid\text{$\alpha$ is an
inversion sequence}\\}.$

For example,

$\operatorname{I}_{3}=\\{000,001,002,010,011,012\\}.$

Note that any $d$-ascent sequence is an inversion sequence: Setting $k=1$ in
(5) immediately gives $a_{1}=0$. And for $k\geq 2$, the maximum number of
$d$-ascents in $\alpha_{k-1}$ is $k-2$ so that

$a_{k}\leq 1+\operatorname{dasc}\alpha_{k-1}\leq k-1.$

It follows that $\operatorname{dA}_{n}\subseteq\operatorname{I}_{n}$ for all
$d,n\geq 0$.

$1$$2$$3$$4$$5$$6$$7$$8$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$0$$1$$2$$3$$4$ Figure 3:
A matching and its active spaces

A (perfect) matching, $m$, is a graph on the vertex set $[2n]$ with a set of
$n$ edges $e=ij$ no two of which share a vertex. We will always write our
edges $ij$ so that $i<j$ and label them
$e_{1}=i_{1}j_{1},e_{2}=i_{2}j_{2},\ldots,e_{n}=i_{n}j_{n}$ so that

$1<j_{1}<j_{2}<\ldots<j_{n}=2n.$

Figure 3 displays a matching $m$ on $[8]$ with edges

$e_{1}=13,\ e_{2}=25,\ e_{3}=47,\ \text{ and }e_{4}=68.$

The Claesson-Linusson bijection, $\operatorname{mh}$, is built on the notion
of an active space. The active spaces of $m$ are the spaces just before
$j_{1},j_{2},\ldots,j_{n}$ together with the space after $2n$. They will be
labeled $0,1,\ldots,n$ from left to right. In Figure 3, the active spaces are
indicated using double-headed arrows with their labels below. Given
$\alpha=a_{1}a_{2}\ldots a_{n}\in\operatorname{I}_{n}$ we construct a sequence
of matchings

$\emptyset=m_{0},m_{1},\ldots,m_{n}=\operatorname{mh}(\alpha)$

where $m_{k}$ is a matching on $[2k]$ for $0\leq k\leq n$. To obtain $m_{k}$
from $m_{k-1}$, insert new vertices in active spaces $a_{k}$ and $k-1$ and
connect them by an edge $e_{k}$ as well as renumbering the vertices
$1,2,\ldots,2k$ from left to right. For example, if $\alpha=0102$ then the
sequence of nonempty matchings is given in Figure 4.

$1$$m_{1}$$2$$m_{1}$$1$$m_{2}$$2$$m_{2}$$3$$m_{2}$$4$$m_{2}$$1$$2$$3$$4$$5$$6$$m_{3}$$1$$2$$3$$4$$5$$6$$7$$8$$m_{4}=\operatorname{mh}(\alpha)$
Figure 4: Computing $\operatorname{mh}(0,1,0,2)$

To describe the image of the $\operatorname{mh}$ map, define a nesting in a
matching $m$ to be a pair of edges of the form $ij$ and $kl$ where $i<k<l<j$.
As an example, in Figure 4 the edges $26$ and $45$ form a nesting in $m_{3}$.
A left nesting is a nesting with $k=i+1$, and a right nesting is one with
$j=l+1$. The nesting in the previous example is a right nesting, but not a
left nesting. Let

$\operatorname{M}_{n}=\\{m\mid\text{$m$ is a matching on $[2n]$ with no left
nestings}\\}.$

Also, given an edge $e=ij$ in a matching we say that edge $kl$ is to its left
if $l<i$. We let

$\operatorname{lef}(e)=\text{ number of edges to the left of $e$}.$

We include the following result and proof of Claesson and Linsson to motivate
what follows for $d$-ascent sequences.

######  Theorem 3.1 ([CL11]).

The map $\operatorname{mh}$ is a bijection
$\operatorname{mh}:\operatorname{I}_{n}\rightarrow\operatorname{M}_{n}$.

###### Proof.

The function is well defined since if $i_{k}j_{k}$ is the edge added to form
$m_{k}$ then, by definition of the active spaces, $i_{k}+1$ is the right
endpoint of an edge. So no left nesting can be formed.

To see that this is a bijection, one can construct the inverse by sending a
matching $m$ with vertices $[2n]$ to the inversion table
$\alpha=a_{1}a_{2}\ldots a_{n}$ where

$a_{k}=\operatorname{lef}(e_{k})$ (6)

for $k\in[n]$. ∎

Since every $d$-descent sequence is an inversion table, we can get a bijection
with matchings by restricting $\operatorname{mh}$ to $\operatorname{dA}_{n}$
and characterizing the image. In view of equation (6) and the definition of
$\operatorname{dAsc}\alpha$ we say that $k$ is a $d$-displacement of a
matching $m$ on $[2n]$ if

$\operatorname{lef}(e_{k+1})>\operatorname{lef}(e_{k})-d,$

and let

$\operatorname{ddis}m=\\#\\{k\in[n-1]\mid\text{$k$ is a $d$-displacement of
$m$}\\}.$

We can now finally define the matchings which are in bijection with $d$-ascent
sequences. The set of difference $d$ matchings is

$\operatorname{dMch}_{n}=\\{m\in\operatorname{M}_{n}\mid\text{
$\operatorname{lef}(m_{k+1})\leq 1+\operatorname{ddis}(m_{k})$ for
$k\in[n-1]$}\\}$

where $m_{k}$ is the restriction of $m$ to the arcs $e_{1},\ldots,e_{k}$
gotten by removing all vertices which are not endpoints of those edges and
relabeling the remaining vertices. The next result follows easily from the
previous theorem, so its proof is omitted.

######  Theorem 3.2.

For all $d,n\geq 0$, the map $\operatorname{mh}$ restricts to a bijection
$\operatorname{mh}:\operatorname{dA}_{n}\rightarrow\operatorname{dMch}_{n}$. ∎

##  4 Permutations

Bousquet-Mélou et al [BMCDK10] initiated the study of bivincular patterns and
showed that ascent sequences are in bijection with permutations avoiding a
bivincular pattern of length 3. A bijection between weak ascent sequences and
permutations avoiding a bivincular pattern of length 4 was found in [BCD23].
In this section, we will show that there is always an injection from
$d$-ascent sequences into a corresponding set of permutations avoiding a
pattern of length $d+3$, although it is not surjective in general. In all
cases, the technique used is based on the method of generating trees and, in
particular, of active sites in permutations.

Recall that we are using ${\mathfrak{S}}_{n}$ for the symmetric group of all
permutations $\pi=p_{1}p_{2}\ldots p_{n}$ of $[n]$ written in one-line
notation. Note, again, the use of Greek letters for permutations and Roman
ones for their elements. We say that $\pi$ contains the classical pattern
$\sigma=s_{1}s_{2}\ldots s_{k}\in{\mathfrak{S}}_{k}$ if there is a subsequence
$\kappa=p_{i_{1}}p_{i_{2}}\ldots p_{i_{k}}$ of $\pi$ whose elements are in the
same relative order as those of $\sigma$. In this case $\kappa$ is called a
copy of $\sigma$. For example, a copy of the pattern $231$ would be a
subsequence $\kappa=bca$ with $a<b<c$. So $\pi=643512$ contains four copies of
$231$ namely $451$, $452$, $351$, and $352$. To contain a bivincular pattern
$\sigma$, certain pairs of elements of the copy $\kappa$ must be adjacent in
$\pi$ and others must be adjacent as integers. In the first case we put a
vertical bar between the elements of $\sigma$, and in the second we put a bar
over the smaller of the two integers. To illustrate, a copy $\kappa=bca$ of
the bivincular pattern $\sigma^{\prime}=2|3\overline{1}$ in a permutation
$\pi$ would have $a<b<c$ with $b,c$ adjacent in $\pi$ and $b=a+1$. Using $\pi$
as in the previous example, only one of the subsequences listed above is a
copy of $\sigma^{\prime}$, namely $352$. Note that classical patterns are a
special case of bivincular ones where there are no bars or overlines, so
henceforth we will just use the term pattern. We say that $\pi$ avoids the
pattern $\sigma$ if it does not contain $\sigma$ and let

$\operatorname{Av}_{n}(\sigma)=\\{\pi\in{\mathfrak{S}}_{n}\mid\text{$\pi$
avoids $\sigma$}\\}.$

######  Theorem 4.1 ([BMCDK10, BCD23]).

Let

$\sigma_{3}=2|3\overline{1}\text{ and }\sigma_{4}=3|41\overline{2}.$

Then for all $n\geq 0$ there are bijections
$\operatorname{A}_{n}\leftrightarrow\operatorname{Av}_{n}(\sigma_{3})$ and
$\operatorname{wA}_{n}\leftrightarrow\operatorname{Av}_{n}(\sigma_{4})$. Thus

$\\#\operatorname{A}_{n}=\\#\operatorname{Av}_{n}(\sigma_{3})\text{ and
}\\#\operatorname{wA}_{n}=\\#\operatorname{Av}_{n}(\sigma_{4}).$

$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---
$\\#\operatorname{dA}_{n}$ | 1 | 2 | 6 | 24 | 118 | 682 | 4506 | 33376
$\\#\operatorname{Av}(\sigma_{5})$ | 1 | 2 | 6 | 24 | 119 | 699 | 4721 | 35904
Table 1: Comparison of $\\#\operatorname{dA}_{n}$ when $d=2$ and
$\\#\operatorname{Av}(\sigma_{5})$

Consider the bivincular pattern

$\sigma_{d}=(d-1)|d12\ldots\overline{(d-2)}.$

The main theorem of this section is as follows.

######  Theorem 4.2.

For all $d,n\geq 0$ we have

$\\#\operatorname{dA}_{n}\leq\\#\operatorname{Av}_{n}(\sigma_{d+3}).$

We note that the inequality in this theorem can be strict. For example, when
$d=2$ the cardinalities of of $\operatorname{dA}_{n}$ and
$\operatorname{Av}_{n}(\sigma_{5})$ are shown in Table 1 and are not always
equal.

To prove Theorem 4.2, we will need the notion of an active site in a
permutation. Fix a pattern $\sigma$ and suppose that $\pi=p_{1}p_{2}\ldots
p_{n}\in\operatorname{Av}_{n}(\sigma)$. Consider the $n+1$ spaces of $\pi$
consisting of the space before $\pi_{1}$, the space after $\pi_{n}$, and the
$n-1$ spaces between adjacent elements of $\pi$. Call a space an active space
or active site if insertion of $n+1$ in that space results in a permutation
$\pi^{\prime}$ which still avoids $\sigma$. The rest of the sites/spaces are
called inactive. We write

$\operatorname{act}\pi=\text{ number of active sites of $\pi$}$

and number the active sites of $\pi$ from left to right
$0,1,\ldots,(\operatorname{act}\pi)-1$. Note that $\operatorname{act}\pi$
depends on the pattern $\sigma$ being avoided but this will always be clear
from context. The empty permutation $\emptyset$ has one active site labeled
$0$. For example, if $\pi=631245$ and $\sigma=\sigma_{4}=3|41\overline{2}$
then the numbering of its active sites is

$\rule{0.0pt}{5.0pt}_{\genfrac{}{}{0.0pt}{2}{\uparrow}{0}}6\ 3\
1_{\genfrac{}{}{0.0pt}{2}{\uparrow}{1}}2_{\genfrac{}{}{0.0pt}{2}{\uparrow}{2}}4_{\genfrac{}{}{0.0pt}{2}{\uparrow}{3}}5_{\genfrac{}{}{0.0pt}{2}{\uparrow}{4}}.$

Note that the space after $6$ is not active because inserting $7$ there gives
the copy $\kappa=6745$ of $\sigma$, and the space after $3$ is not active
because of the creation of $\kappa=3712$.

$\begin{array}[]{ccccccc}\emptyset&\rule{0.0pt}{5.0pt}_{\genfrac{}{}{0.0pt}{2}{\uparrow}{0}}1_{\genfrac{}{}{0.0pt}{2}{\uparrow}{1}}&\rule{0.0pt}{5.0pt}_{\genfrac{}{}{0.0pt}{2}{\uparrow}{0}}1_{\genfrac{}{}{0.0pt}{2}{\uparrow}{1}}2_{\genfrac{}{}{0.0pt}{2}{\uparrow}{2}}&\rule{0.0pt}{5.0pt}_{\genfrac{}{}{0.0pt}{2}{\uparrow}{0}}31_{\genfrac{}{}{0.0pt}{2}{\uparrow}{1}}2_{\genfrac{}{}{0.0pt}{2}{\uparrow}{2}}&\rule{0.0pt}{5.0pt}_{\genfrac{}{}{0.0pt}{2}{\uparrow}{0}}31_{\genfrac{}{}{0.0pt}{2}{\uparrow}{1}}2_{\genfrac{}{}{0.0pt}{2}{\uparrow}{2}}4_{\genfrac{}{}{0.0pt}{2}{\uparrow}{3}}&\rule{0.0pt}{5.0pt}_{\genfrac{}{}{0.0pt}{2}{\uparrow}{0}}31_{\genfrac{}{}{0.0pt}{2}{\uparrow}{1}}2_{\genfrac{}{}{0.0pt}{2}{\uparrow}{2}}5_{\genfrac{}{}{0.0pt}{2}{\uparrow}{3}}4_{\genfrac{}{}{0.0pt}{2}{\uparrow}{4}}&631254\\\
\\\
\pi_{0}&\pi_{1}&\pi_{2}&\pi_{3}&\pi_{4}&\pi_{5}&\pi_{6}=\operatorname{pe}(\alpha)\end{array}$
Figure 5: Computing $\operatorname{pe}(010220)$ when $d=1$

We now define an injection
$\operatorname{pe}:\operatorname{dA}_{n}\rightarrow\operatorname{Av}_{n}(\sigma_{d+3})$
as follows. Given $\alpha=a_{1}a_{2}\ldots a_{n}\in\operatorname{dA}_{n}$ we
construct a sequence of permutations

$\emptyset=\pi_{0},\pi_{1},\ldots,\pi_{n}=\operatorname{pe}(\alpha)$

where $\pi_{k}$ is obtained from $\pi_{k-1}$ by inserting $k$ in the active
space labeled $a_{k}$ for $1\leq k\leq n$. As an example, suppose that $d=1$
so we are avoiding $\sigma_{d+3}=\sigma_{4}=3|41\overline{2}$. For the weak
ascent sequence $\alpha=010220$ we would get the sequence of permutation in
Figure 5 where the active sites of each permutation have been labeled for
convenience.

We must prove that this map is well defined in that there is a space of
$\pi_{k-1}$ labeled by $a_{k}$. This will be done using the next lemma.

######  Lemma 4.3.

For all $k\geq 1$ We have the following inequalities.

  1. (a)

If $\alpha=a_{1}a_{2}\ldots a_{k-1}$ and $\beta=\beta a_{k}$ (concatenation)
then

$\operatorname{dasc}\alpha\leq\operatorname{dasc}\beta\leq\operatorname{dasc}\alpha+1.$

  2. (b)

If $\sigma\in\operatorname{Av}_{k}(\sigma_{d+3})$ is obtained from
$\pi\in\operatorname{Av}_{k-1}(\sigma_{d+3})$ by inserting $k$ in an active
site then

$\operatorname{act}\pi\leq\operatorname{act}\sigma\leq\operatorname{act}\pi+1.$

###### Proof.

(a) The $d$-ascents of $\beta$ are those in $\alpha$ plus possibly a new
$d$-ascent if $a_{k}>a_{k-1}-d$. The result follows.

(b) Call the sites of $\pi$ which remain adjacent to the same elements in
$\sigma$ common. We first claim that common sites remain active or inactive in
passing from $\pi$ to $\sigma$. If a common site is inactive in $\pi$ then
insertion of $k$ there forms a copy $\kappa$ of $\sigma_{d+3}$. But then
insertion of $k+1$ in the same site forms a copy of $\sigma_{d+3}$ obtained by
replacing $k$ by $k+1$ in $\kappa$. Now assume, towards a contradiction, that
an active common site in $\pi$ becomes inactive in $\sigma$. So there is a
copy $\kappa^{\prime}$ of $\sigma_{d+3}$ when $k+1$ is inserted in the site of
$\sigma$. That copy must contain $k+1$ acting as the $d+3$. Also $k$ is not in
$\kappa^{\prime}$, since if it were then it would be acting as the $d+2$. But
that implies that the site where $k+1$ was inserted is adjacent to $k$ and so
not common. Thus inserting $k$ into $\pi$ in this common site produces a copy
of $\sigma_{d+3}$ obtained by replacing the $k+1$ in $\kappa^{\prime}$ with
$k$, which contradicts the fact that the site is active in $\pi$.

Now consider the new site of $\sigma$ just before and after $k$. One can show
in a manner similar to the previous paragraph that the site before $k$ will
always be active. So $\operatorname{act}\sigma=\operatorname{act}\pi+1$ or
$\operatorname{act}\sigma=\operatorname{act}\pi$ depending on whether the site
after $k$ is active or not, respectively. This is what we wished to prove. ∎

We can now show that insertion is well defined.

######  Proposition 4.4.

During the construction of $\operatorname{pe}(a_{1}a_{2}\ldots a_{n})$, there
is a site in $\pi_{k-1}$ labeled $a_{k}$ for $1\leq k\leq n$.

###### Proof.

By the way that sites are labeled, we must show that

$a_{k}\leq\operatorname{act}\pi_{k-1}-1$

for all $k\in[n]$. This is equivalent to showing that

$\operatorname{dasc}\alpha_{k}\leq\operatorname{act}\pi_{k}-2$ (7)

for all $k\in[n]$. To see this, note that since $\alpha$ is a $d$-ascent
sequence, the last inequlity implies

$a_{k}\leq\operatorname{dasc}\alpha_{k-1}+1\leq(\operatorname{act}\pi_{k-1}-2)+1=\operatorname{act}\pi_{k-1}-1$

with the converse being similar.

We will prove the inequality (7) by induction on $k$ where the case $k=1$ is
trivial. Assume the inequality for $k$. There are three cases depending on the
value of $a_{k+1}$.

For the first case, suppose $a_{k+1}\leq a_{k}-d$. So
$\operatorname{dasc}\alpha_{k+1}=\operatorname{dasc}\alpha_{k}$. But by the
previous lemma, the right side of (7) stays the same or goes up by one when
passing from $\pi_{k}$ to $\pi_{k+1}$. So it continues to hold for $k+1$.

For the second case, suppose $a_{k+1}>a_{k}$. Now
$\operatorname{dasc}\alpha_{k+1}=\operatorname{dasc}\alpha_{k}+1$. So it
suffices to show that
$\operatorname{act}\pi_{k+1}=\operatorname{act}\pi_{k}+1$. By the proof of
Lemma 4.3, this will follow if we can show that the site after $k+1$ is active
in $\pi_{k+1}$. Since $a_{k+1}>a_{k}$, the site where $k+1$ is inserted is to
the right of $k$. Suppose, towards a contradiction, that inserting $k+2$
directly to the right of $k+1$ forms a copy of $\sigma_{d+3}$. Then $k+1$ and
$k+2$ take the roles of $d+2$ and $d+3$, respectively. This forces $k$ to be
the $d+1$ and so to be the right of $k+1$. This contradiction shows that the
site after $k+1$ is active as desired.

The last case is when $a_{k}-d<a_{k+1}\leq a_{k}$. Again
$\operatorname{dasc}\alpha_{k+1}=\operatorname{dasc}\alpha_{k}+1$. So, as in
the previous paragraph, we have to show that the site after $k+1$ is active in
$\pi_{k+1}$. As before, we assume it is not, so inserting $k+2$ would form a
copy $k+1,k+2,k_{1},k_{2},\ldots,k_{d},k$ of $\sigma_{d+3}$ where
$k_{1}<k_{2}<\ldots<k_{d}$. We claim that there is some $i\in[d-1]$ such that
all the spaces between $k_{i}$ and $k_{i+1}$ are inactive. For suppose this
was not the case. Now the active space before $k$ is labeled $a_{k}$ and there
are at least $d-1$ active spaces between $k_{1}$ and $k_{d}$. So $k+1$ was
inserted in a space labeled at most $a_{k}-d$ which contradicts
$a_{k+1}>a_{k}-d$.

Suppose $i$ is chosen so there are no active spaces between $k_{i}$ and
$k_{i+1}$. Since $k_{i}<k_{i+1}$ there must be two adjacent elements
$p_{j}<p_{j+1}$ of $\pi_{k}$ among the elements in the factor of $\pi_{k}$
from $k_{i}$ to $k_{i+1}$. Since the space between $p_{j}$ and $p_{j+1}$ is
not active, placing $k+1$ there results in a copy $\kappa$ of $\sigma_{d+3}$
where $p_{j}$ and $k+1$ plays the roles of $d+2$ and $d+3$, respectively.
Since $p_{j}<p_{j+1}$, replacing $k+1$ in $\kappa$ by $p_{j+1}$ gives a copy
of $\sigma_{d+3}$ in $\pi_{k}$ where $p_{j}$ and $p_{j+1}$ play the roles of
$d+2$ and $d+3$, respectively. This contradicts the fact that $\pi_{k}$ avoids
$\sigma_{d+3}$ and completes the proof. ∎

We can now demonstrate Theorem 4.2 which will be an immediate consequence of
the following result.

######  Theorem 4.5.

For all $d,n\geq 0$ the map
$\operatorname{pe}:\operatorname{dA}_{n}\rightarrow\operatorname{Av}_{n}(\sigma_{d+3})$
is an injection.

###### Proof.

From the previous proposition we know that the insertion process will produce
a sequence $\pi_{0},\pi_{1},\ldots,\pi_{n}=\operatorname{pe}(\alpha)$.
Furthermore, each $\pi_{i}$ avoids $\sigma_{d+3}$ because elements are
inserted in active sites. To show that this is an injection, we induct on $n$.
Suppose $\alpha=a_{1}\ldots a_{n}$ and $\beta=b_{1}\ldots b_{n}$ are distinct
$2$-ascent sequences. If $\alpha_{n-1}\neq\beta_{n-1}$ then by induction
$\operatorname{pe}(\alpha_{n-1})\neq\operatorname{pe}(\beta_{n-1})$. And
insertion of $n$ into two different permutations can not make them equal so
$\operatorname{pe}(\alpha)\neq\operatorname{pe}(\beta)$. The other possibility
is $\alpha_{n-1}=\beta_{n-1}$ which forces $a_{n}\neq b_{n}$. So $n$ is
inserted in different positions of
$\operatorname{pe}(\alpha_{n-1})=\operatorname{pe}(\beta_{n-1})$ and we again
have that $\operatorname{pe}(\alpha)$ and $\operatorname{pe}(\beta)$ are
distinct. ∎

##  5 Posets

$P=$$1$$2$$3$$6$$4$$5$

$Q=$$1$$2$$3$$4$$5$$6$

Figure 6: Two posets

Let $(P,\leq_{P})$ be a poset (partially ordered set). We say that $P$ is
$(a+b)$-free if it does not contain an (induced) subposet isomorphic to the
disjoint union of an $a$-element chain and a $b$-element chain. The poset $P$
whose Hasse diagram is on the left in Figure 6 is not $(3+1)$-free because of
the chains $1<_{P}2<_{P}3$ and $4$. But it is $(4+1)$-free because the only
chain with four elements is $1<_{P}2<_{P}3<_{P}5$ and the remaining two
elements are related to members of that chain. Ascent sequences are in
bijection with unlabeled $(2+2)$-free posets as shown in [BMCDK10]. Claesson
and Linusson [CL11] introduced a family of labeled posets called factorial
posets which are $(2+2)$-free. Then in [BCD23] a bijective map was constructed
between weak ascent sequences and factorial posets which do not contain a
specially labeled $3+1$ subposet. In this section we will introduce a
specially labeled $(d-1)+1$ poset $P_{d}$ and show that for all $d\geq 1$
there is always an injection from $d$-ascent sequences to factorial posets
which are special $P_{d+3}$-free.

Let $P$ be a poset with elements $[n]$ for some $n$. We will use $<_{P}$ to
denote the partial order on $P$ and $<$ for the total order on the integers.
Call $P$ factorial if it satisfies the following rule reminiscent of the
transitive law:

$i<j\text{ and }j<_{P}k\implies i<_{P}k$ (8)

for all $i,j,k\in[n]$. The reason they are called factorial is because there
are $n!$ such posets on $[n]$. As an example, it is easy to check that the
poset $P$ on the left in Figure 6 is factorial. But the poset $Q$ on the right
is not because $4<5$ and $5<_{P}6$ but $4\not<_{P}6$. It is not hard to see
that a factorial poset is naturally labeled in that $i<_{P}j$ implies $i<j$.

We define a special poset $P_{d}$ to be a disjoint union $(d-1)+1$ together
with a labeling of the form

$\vdots$$P_{d}=$$i_{1}$$i_{2}$$i_{3}$$i_{d-3}$$i_{d-2}$$i_{d-1}$$i_{d-2}+1$

where $i_{1}<i_{2}<\ldots<i_{d-1}$ and $i_{d-2}+1<i_{d-1}$. Call a labeled
poset special $P_{d}$-free if it does not contain an induced subposet equal to
$P_{d}$ for some choice of labels. We will use the notation

$\operatorname{Av}_{n}(P_{d})=\\{P\mid\text{$P$ is a factorial poset on $[n]$
which is special $P_{d}$-free}\\}.$

This should cause no confusion with the use of $\operatorname{Av}_{n}$ in the
previous section since in that case it was applied to a permutation, not a
poset. To illustrate, note that even though the poset $P$ in Figure 6 is not
$(3+1)$-free, it is special $P_{4}$-free. This is because the unique copy of
$3+1$ is $1<_{P}2<_{p}3$ and $4$, but the integer $4$ is not one more then the
penultimate element of the $3$-element chain which is $2$. This section’s main
result is as follows.

######  Theorem 5.1.

For all $d\geq 1$ and $n\geq 0$ we have

$\\#\operatorname{dA}_{n}\leq\\#\operatorname{Av}_{n}(P_{d+3}).$

$n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
---|---|---|---|---|---|---|---|---
$\\#\operatorname{dA}_{n}$ | 1 | 2 | 6 | 24 | 118 | 682 | 4506 | 33376
$\\#\operatorname{Av}(P_{5})$ | 1 | 2 | 6 | 24 | 119 | 700 | 4747 | 36370
Table 2: Comparison of $\\#\operatorname{dA}_{n}$ when $d=2$ and
$\\#\operatorname{Av}(P_{5})$

We note that for $d=1$ the above inequality is actually an equality as proved
in [BCD23]. And, as in Theorem 4.2, the inequality can be strict for $d\geq 2$
as shown in Table 2.

For $d\geq 1$ we define a map
$\operatorname{po}:\operatorname{dA}_{n}\rightarrow\operatorname{Av}_{n}(P_{d+3})$
as follows. If $\alpha=a_{1}a_{2}\ldots a_{n}$ then we construct a poset
$P=\operatorname{po}(\alpha)$ on $[n]$ by letting, for each pair $i,j\in[n]$
of distinct elements,

$i<_{P}j$ if and only if $\operatorname{dasc}\alpha_{i}<a_{j}$. (9)

For example, if $d=2$ and $\alpha=012032$ then $\operatorname{po}(\alpha)$ is
the poset $P$ in Figure 6. In particular, if $j=6$ then $a_{6}=2$ so that
$1<_{P}6$ and $2<_{P}6$ since $\operatorname{dasc}\alpha_{1}=0$ and
$\operatorname{dasc}\alpha_{2}=1$ both of which are smaller than $a_{6}=2$.
However $6$ is not related to any $i>3$ since in those cases
$\operatorname{dasc}\alpha_{i}\geq 2$. We will first need a couple of lemmas
to prove that $\operatorname{po}$ is well defined and an injection.

######  Lemma 5.2.

Suppose $d\geq 0$. For any $d$-ascent sequence $\alpha=a_{1}a_{1}\ldots a_{n}$
and any $k\in[n]$ we have

$a_{k}\leq\operatorname{dasc}\alpha_{k}.$

###### Proof.

Induct on $k$ where $k=1$ is trivial. Assuming the result for $k-1$, we have
two cases. The first is if $a_{k}\leq a_{k-1}-d$. But then, by induction and
the definition of a $d$-ascent,

$a_{k}\leq
a_{k-1}\leq\operatorname{dasc}\alpha_{k-1}=\operatorname{dasc}\alpha_{k}.$

The other possibility is that $a_{k}>a_{k-1}-d$. So, from the definition of a
$d$-ascent sequence and induction, we have

$a_{k}\leq\operatorname{dasc}\alpha_{k-1}+1=\operatorname{dasc}\alpha_{k}$

which completes the proof. ∎

We can now establish that the map $\operatorname{po}$ is well defined.

######  Lemma 5.3.

Suppose $d\geq 1$ and $\alpha\in\operatorname{dA}_{n}$. Then
$\operatorname{po}(\alpha)\in\operatorname{Av}_{n}(P_{d+3})$.

###### Proof.

Let $\alpha=a_{1}a_{2}\ldots a_{n}$ and $P=\operatorname{po}(\alpha)$. Since
(9) only defines a relation on distinct elements, we can assume reflexivity.
For antisymmetry, it suffices to show that if $i<_{P}j$ then $i<j$ as then the
law will follow from antisymmetry of the total order on integers. Suppose, to
the contrary, that $j<i$. Using the previous lemma and the fact that
$\operatorname{dasc}\alpha_{k}$ is a weakly increasing function of $k$ gives

$a_{j}\leq\operatorname{dasc}\alpha_{j}\leq\operatorname{dasc}\alpha_{i}.$

But this contradicts (9). For transitivity, suppose $i<_{P}j$ and $j<_{P}k$.
By definition $\operatorname{dasc}\alpha_{i}<a_{j}$ and
$\operatorname{dasc}\alpha_{j}<a_{k}$. Now, using the previous sentence and
Lemma 5.2 again, we have

$\operatorname{dasc}\alpha_{i}<a_{j}\leq\operatorname{dasc}\alpha_{j}<a_{k}.$

Thus $i<_{P}k$.

To check the factorial condition, assume $i<j$ and $j<_{P}k$. This implies
that $\operatorname{dasc}\alpha_{i}\leq\operatorname{dasc}\alpha_{j}$ and
$\operatorname{dasc}\alpha_{j}<a_{k}$. By transitivity in the integers,
$\operatorname{dasc}\alpha_{i}<a_{k}$ which is equivalent to $i<_{P}k$.

Finally, we need to show that $P$ is special $P_{d+3}$-free. Take any chain

$C:i_{1}<_{P}i_{2}<_{P}\ldots<i_{d+1}<_{P}i_{d+2}$

in $P$ and, to simplify notation, let $i=i_{1}$, $j=i_{d+1}$, and $k=i_{d+2}$.
It suffices to show that $j+1$ must be related to some element of $C$. There
are now two cases. First suppose that $a_{j+1}\leq a_{j}-d$ so that
$\operatorname{dasc}\alpha_{j+1}=\operatorname{dasc}\alpha_{j}$. Since
$j<_{p}k$ we have $\operatorname{dasc}\alpha_{j}<a_{k}$. Combining the
inequalities gives $\operatorname{dasc}\alpha_{j+1}<a_{k}$ so that
$j+1<_{P}k$, thereby yielding the desired relation between $j+1$ and an
element of $C$.

In the second case, suppose that $a_{j+1}>a_{j}-d$. Note that since $d\geq 1$,
that element $i$ is different from $j$ and we will show $i<_{P}j+1$. Now using
the inequalities in $C$ and Lemma 5.2 several more times

$\operatorname{dasc}\alpha_{i}=\operatorname{dasc}\alpha_{i_{1}}<a_{i_{2}}\leq\operatorname{dasc}\alpha_{i_{2}}<a_{i_{3}}\leq\operatorname{dasc}\alpha_{i_{3}}<\ldots<a_{i_{d+1}}=a_{j}.$

It follows that $\operatorname{dasc}\alpha_{i}\leq a_{j}-d$. Combined with the
inequality assumed for this case we obtain
$\operatorname{dasc}\alpha_{i}<a_{j+1}$. This implies $i<_{P}j+1$ which
completes the proof. ∎

We can now finish the proof that $\operatorname{po}$ is an injection.

######  Theorem 5.4.

For all $d\geq 1$ and $n\geq 0$ the map
$\operatorname{po}:\operatorname{dA}_{n}\rightarrow\operatorname{Av}(P_{d+3})$
is an injection.

###### Proof.

Since we have already proved that $\operatorname{po}$ is well defined, it just
remains to prove that the map is injective. It suffices to show that if
$\alpha=a_{1}a_{2}\ldots a_{n}$ with $\operatorname{po}(\alpha)=P$ then the
sequence $\alpha$ is uniquely determined by $P$. We will do this by induction
on $n$ where, as usual, we skip the base case.

By induction we can assume that $a_{1},\ldots,a_{n-1}$ are determined. There
are now two cases. First suppose that $n$ is minimal in $P$. We claim that
this forces $a_{n}=0$. For suppose $a_{n}>0$. But then
$a_{n}>0=\operatorname{wasc}\alpha_{1}$ and so $n>_{P}1$, contradicting
minimality of $n$.

If $n$ is not minimal, then let

$m=\max\\{i\mid i<_{P}n\\}$

where the maximum is taken in the integers. We claim that

$a_{n}=\operatorname{dasc}\alpha_{m}+1$ (10)

and so is uniquely determined. Since $n>_{P}m$ we must have
$a_{n}>\operatorname{dasc}\alpha_{m}$. There are now two subcases depending on
whether $m<n-1$ or $m=n-1$. When $m<n-1$ we have $m+1<n$, and $m+1\not<_{P}n$
by definition of $m$. So (9) implies that $\operatorname{dasc}\alpha_{m+1}\geq
a_{n}$. Thus

$1+\operatorname{dasc}\alpha_{m}\geq\operatorname{dasc}\alpha_{m+1}\geq
a_{n}>\operatorname{dasc}\alpha_{m}$

which forces (10) to hold. Now assume $m=n-1$ so that
$a_{n}>\operatorname{dasc}\alpha_{n-1}$. But the definition of a $d$-ascent
sequence implies $a_{n}\leq\operatorname{dasc}\alpha_{n-1}+1$. This forces
$a_{n}=\operatorname{dasc}\alpha_{n-1}+1$ as desired. ∎

##  6 $d$-increasing $d$-ascent sequences

Say that a sequence of nonnegative integers $\alpha=a_{1}a_{2}\ldots a_{n}$ is
$d$-increasing if

$a_{k+1}>a_{k}-d$

for all $1\leq k<n$. Equivalently,

$\operatorname{dAsc}\alpha=[n-1].$ (11)

So a $0$-increasing sequence is strictly increasing while a $1$-increasing
sequence is weakly increasing. In this section we will study $d$-increasing
$d$-ascent sequences. In other words, we will consider the set

$\operatorname{dI}_{n}=\\{\alpha\in\operatorname{dA}_{n}\mid\text{$\alpha$ is
$d$-increasing}\\}$

as well as the cardinalities

$\operatorname{di}_{n}=\\#\operatorname{dI}_{n}.$

In particular, we will find a recursion for $\operatorname{di}_{n}$ and show
that in the case $d=2$ these numbers count the rooted duplication trees
introduced in [GHJMM03].

It follows from equation (11) that in a $d$-increasing sequence we have
$\operatorname{dasc}\alpha_{k}=k-1$ for all $k$. Combining this observation
with the definitions of $d$-increasing and $d$-ascent sequence, we have that
$\alpha=a_{1}a_{2}\ldots a_{n}\in\operatorname{dI}_{n}$ if and only if

  1. (I1)

$a_{1}=0$, and

  2. (I2)

$a_{k}-d<a_{k+1}\leq k$ for $k\in[n-1]$.

Notice that if $d=0$ then there is a unique element in
$\operatorname{dI}_{n}$, namely $\alpha=01\ldots n-1$. When $d=1$, the
$\alpha\in\operatorname{dI}_{n}$ are weakly increasing sequences of
nonnegative integers satisfying $a_{k}<k$ for all $k\in[n]$. In this case
$\operatorname{di}_{n}=C_{n}$, the $n$th Catalan number. To see this, just
interpret $a_{k}$ as the height of the $k$th east step in a lattice path from
the origin to $(n,n)$ using steps north and east and never going above the
line $y=x$. We will now derive a recursive formula for $\operatorname{di}_{n}$
for any $d\geq 0$. The sign-reversing involution proof which we use to obtain
this result has wide applicability to sequence enumeration problems. It was
first used by Fröberg [Fr75] and by Carlitz, Scoville and Vaughn [CSV76]. For
more information about sign-reversing involution proofs in general, see the
text of Sagan [Sag20].

######  Theorem 6.1.

For $d\geq 0$ and $n\geq 1$ we have

$\operatorname{di}_{n}=\sum_{k\geq
1}(-1)^{k-1}\binom{n-kd+d}{k}\operatorname{di}_{n-k}.$

###### Proof.

When $d=0$ we have $\operatorname{di}_{n}=1$ for all $n$ and the identity is
well known. So we will assume that $d\geq 1$. Putting everything on the left
side of the equation, the desired formula can be rewritten

$\sum_{k\geq 0}(-1)^{k}\binom{n-kd+d}{k}\operatorname{di}_{n-k}=0.$ (12)

We will prove this by using a sign-reversing involution.

Let ${\cal S}$ be the set of all ordered pairs $(\alpha,S)$ consisting of
$\alpha=a_{1}a_{2}\ldots a_{n-k}\in\operatorname{dI}_{n-k}$ for some $k\geq 0$
and a set $S=\\{s_{1}<s_{2}<\ldots<s_{k}\\}\subseteq\\{0,1,\ldots,n-k\\}$ such
that

$s_{i+1}-s_{i}\geq d$ (13)

for all $1\leq i<k$. Notice that such $S$ are in bijection with unrestricted
subsets

$S^{\prime}=\\{s_{1},s_{2}-d+1,s_{3}-2d+2,\ldots,s_{k}-(k-1)d+(k-1)\\}$

of $\\{0,1,\ldots,n-kd+k-1\\}$ so that the number of possible $S$ is
$\binom{n-kd+k}{k}$. To each pair we associate a sign

$\operatorname{sgn}(\alpha,S)=(-1)^{k}.$

It follows directly from the definitions above that

$\sum_{(\alpha,S)\in{\cal S}}\operatorname{sgn}(\alpha,S)=\sum_{k\geq
0}(-1)^{k}\binom{n-kd+k}{k}\operatorname{di}_{n-k}.$

Thus it suffices to find a sign-reversing involution on ${\cal S}$ with no
fixed points.

Define $\iota:{\cal S}\rightarrow{\cal S}$ as follows. Keeping the notation of
the previous paragraph we let $\iota(\alpha,S)=(\beta,T)$ where there are two
cases depending on $a_{n-k}$, the last element of $\alpha$, and $m$ which is
the maximum element of $S$. In particular, we define

$(\beta,T)=\left\\{\begin{array}[]{ll}(\alpha m,\ S-\\{m\\})&\mbox{if the
concatenation $\alpha m\in\operatorname{dI}_{n-k+1}$,}\\\ (\alpha-a_{n-k},\
S\cup\\{a_{n-k}\\})&\mbox{otherwise,}\end{array}\right.$

where $\alpha-a_{n-k}$ is $\alpha$ with its last element removed. We first
need to check that this is well defined in that $(\beta,T)\in{\cal S}$. First
consider the case when $\alpha m\in\operatorname{dI}_{n-k+1}$. Then
$\beta=\alpha m$ is still a $d$-increasing $d$-ascent sequence by definition
and has length $n-k+1$. Also $T=S-\\{m\\}$ is of size $k-1$. By equation (13)
it has largest element at most $n-k-1$ (in fact, at most $n-k-d$) and still
satisfies that inequality for $0\leq i<k-1$. So $(\beta,T)\in{\cal S}$ as
desired. Now consider the second case. Removing an element from a
$d$-increasing $d$-ascent sequence does not change these characteristics, so
$\beta=\alpha-a_{n-k}\in\operatorname{dI}_{n-k-1}$. By condition (I2) above we
have $a_{n-k}\leq n-k-1$. So, $T\subseteq\\{0,1,\ldots,n-k-1\\}$ which is the
correct superset. Finally, we claim that $T$ has cardinality $k+1$ and
satisfies (13) for $0\leq i<k+1$. Because we are in the second case, it must
be that $\alpha m$ is not a $d$-increasing $d$-ascent sequence. Since $\alpha$
is $d$-increasing, the number of $d$-ascents in $\alpha$ is $n-k-1$. So
concatenation of $\alpha$ with any number in $\\{0,1,\ldots,n-k\\}$ yields a
$d$-ascent sequence. Thus it must be that $\alpha m$ is not $d$-increasing.
But this means that $m\leq a_{n-k}-d$. Since $m$ is the maximum of $S$, it
follows that $T=\\{s_{1}<s_{2}<\ldots<m<a_{n-k}\\}$ has $k+1$ elements and
that (13) continues to hold.

We will be finished if we can show that $\iota^{2}$ is the identity map since
it clearly has no fixed points. Given $(\alpha,S)\in{\cal S}$ we let
$\iota(\alpha,S)=(\beta,T)$. Suppose first that $(\beta,T)$ is obtained from
$(\alpha,S)$ as in the first case of the definition of $\iota$. So
$\beta=\alpha m$ and $T=S-\\{m\\}$. But now we can not remove the largest
element of $T$ and append it to $\beta$. Indeed, $\beta$ ends with $m$ and the
largest element $l$ of $S-\\{m\\}$ satisfies $l\leq m-d$. So $\beta l=\alpha
ml$ is not $d$-increasing. It follows that we must apply case two when
computing $\iota(\beta,T)$ and will thus recover $(\alpha,S)$. Now assume that
$\iota(\alpha,S)$ is computed using case two. Then $\beta=\alpha-a_{n-k}$ and,
as shown in the previous paragraph, $a_{n-k}$ becomes the largest element of
$T$. Hence it is clearly possible to concatenate $\beta$ and $a_{n-k}$ to
reform $\alpha$ and the first case will be applied resulting in
$\iota(\beta,T)=(\alpha,S)$, ∎

$\sigma^{\prime}=$$\sigma_{1}^{\prime}$$\sigma_{2}^{\prime}$$\sigma_{3}^{\prime}$$\sigma_{4}^{\prime}$$\sigma_{5}^{\prime}$$\sigma_{6}^{\prime}$$\sigma_{7}^{\prime}$$\sigma_{8}^{\prime}$$\sigma_{9}^{\prime}$$\sigma=$$\sigma_{1}$$\sigma_{2}$$\sigma_{3}$$\sigma_{4}$$\sigma_{5}$$\sigma_{6}$

$\mapsto$

$\phi_{2,3}$$r=3$$a=2$

$T=$631425R

$\mapsto$

$\phi_{2,3}$$T^{\prime}=$936147258R

Figure 7: A $(2,3)$-duplication

When $d=2$ there is a bijection between $2$-increasing $2$-ascent sequences
and rooted duplication trees which we will now explain. Recall that we use the
prefix t, rather than d, in our notation in the $d=2$ case. A sequence of
genes $\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n}$ can evolve by having some
factor $\sigma_{i}\sigma_{i+1}\ldots\sigma_{i+a}$ duplicate itself. For
example, on the left in Figure 7 the sequence $\sigma$ has the factor
$\sigma_{2}\sigma_{3}\sigma_{4}$ duplicate itself as indicated by the arrows
to form $\sigma^{\prime}$. The duplication process is specified by two
parameters: $a\geq 0$ which is the number of genes after the duplicated
segment, and $r\geq 1$ which is the number of genes in the duplicated segment.
This is called a $(a,r)$-duplication and we write
$\sigma^{\prime}=\phi_{a,r}(\sigma)$. In the example of the figure, $a=2$,
$r=3$ and $\sigma^{\prime}=\phi_{2,3}(\sigma)$.

One can model a sequence of duplications using certain trees $T$. Such $T$
have a rooted edge, $R$, indicating the beginning of the process. They are
also binary because a factor is doubled at each stage. The leaves are
bijectively labeled by $[n]$ for some $n$ and represent the genes
$\sigma_{1},\ldots,\sigma_{n}$. The distance between two leaves in the tree
weakly increases with each duplication. If two leaves $\\{\ell,m\\}$ are
siblings then we call them a leaf pair. Suppose that tree $T$ corresponds to a
sequence $\sigma=\sigma_{1}\ldots\sigma_{n}$ on which an $(a,r)$-duplication
is performed to obtain $\sigma^{\prime}$. Then this is mirrored in a tree
$T^{\prime}=\phi_{a,r}(T)$ obtained from $T$ as follows.

  1. 1.

The leaves $\ell\in[n-a+1,n]$ are all renumbered as $\ell+r$.

  2. 2.

Each leaf $\ell\in[n-a-r+1,n-a]$ becomes the parent of a leaf pair
$\\{\ell,\ell+r\\}$.

If the sequence $\sigma$ in Figure 7 has resulted from a history whose
duplication tree is $T$ as given at the top-right, the resulting
$T^{\prime}=\phi_{2,3}(T)$ corresponding to $\sigma^{\prime}$ is displayed on
the bottom-right.

We can now formally define the set of rooted duplication trees,
$\operatorname{RDT}$, inductively as follows.

  1. 1.

The tree

$T_{2}:=$12R

is in $\operatorname{RDT}$.

  2. 2.

If $T\in\operatorname{RDT}$ has $n$ leaves then
$\phi_{a,r}(T)\in\operatorname{RDT}$ for any $a,r$ such that $a\geq 0$ and
$1\leq r\leq n-a$.

We also let

$\operatorname{RDT}_{n}=\\{T\in\operatorname{RDT}\mid\text{ $T$ has $n$
leaves}\\}.$

Note that $T_{2}$ will always stand for the unique element in
$\operatorname{RDT}_{2}$.

125812369471011R Figure 8: A tree in $\operatorname{RDT}_{12}$

A complication with this definition of $\operatorname{RDT}$ is that the same
tree can be constructed by different applications of the $\phi$-maps. For
example, $\phi_{2,1}(\phi_{0,1}(T_{2}))=\phi_{0,1}(\phi_{1,1}(T_{2}))$.
Gasceul et al. [GHJMM03] gave a canonical way to describe a given tree $T$
based on picking one of the most recent duplications which could lead to $T$.
Say that $T$ contains a visible $(a,r)$-duplication event if there is a tree
$T^{\prime}$ such that $\phi_{a,r}(T^{\prime})=T$. Note that the roles of $T$
and $T^{\prime}$ have switched from the way they were used in Figure 7. Having
a visible $(a,r)$-duplication event for $T\in\operatorname{RDT}_{n}$ is
equivalent to there being $a,r$ such that $\\{\ell,\ell-r\\}$ are leaf pairs
for $\ell\in[n-a-2r+1,n-a]$. For example, suppose $T$ is as in Figure 8. The
visible duplication events in $T$ are as follows:

  * •

$\\{2,3\\}$ is a leaf pair so $T$ contains a visible $(9,1)$-duplication
event,

  * •

$\\{4,7\\},\ \\{5,8\\},\ \\{6,9\\}$ are leaf pairs so $T$ contains a visible
$(3,3)$-duplication event,

  * •

$\\{10,11\\}$ is a leaf pair so $T$ contains a visible $(1,1)$-duplication
event.

Importantly, if $T$ contains a visible $(a,r)$-duplication event then $a$
uniquely determines $r$ since leaf $n-a$ must have a sibling. Moreover, if the
label of that sibling is $m$ then $r=n-a-m$. The leftmost visible
$(a,r)$-duplication event for $T$ is the one with largest $a$. By the
observation just made, this is well defined.

$T_{8}=$84152367R$T_{7}=$$\stackrel{{\scriptstyle\psi_{5,1}}}{{\mapsto}}$7314256R

$T_{6}=$$\stackrel{{\scriptstyle\psi_{1,1}}}{{\mapsto}}$631425R$T_{5}=$$\stackrel{{\scriptstyle\psi_{0,3}}}{{\mapsto}}$51324R

$T_{4}=$$\stackrel{{\scriptstyle\psi_{1,2}}}{{\mapsto}}$4312R$T_{3}=$$\stackrel{{\scriptstyle\psi_{2,1}}}{{\mapsto}}$321R

$T_{2}=$$\stackrel{{\scriptstyle\psi_{1,1}}}{{\mapsto}}$21R

Figure 9: A canonical reduction history

We now define the canonical reduction history of $T\in\operatorname{RDT}_{n}$
to be the sequence of trees

$T=T_{n},T_{n-1},T_{n-2},\ldots,T_{2}$ (14)

such that $T_{k}\in\operatorname{RDT}_{k}$ for $k\in[2,n]$ as follows. If
$T_{k}$, where $k\in[3,n]$, has leftmost duplication event with parameters
$(a,r)=(a_{k},r_{k})$ then we will construct $T_{k-1}=\psi_{a,r}(T_{k})$ by
performing an operation which corresponds to reducing the length of the
duplicated string by one and call $T_{k-1}$ the canonical $(a,r)$-reduction of
$T_{k}$. Formally, $T_{k-1}$ is obtained from $T_{k}$ by

  1. (1)

The leaf pair $\\{k-a,k-a-r\\}$ is removed and the parent is labeled $k-a$.

  2. (2)

Each leaf $\ell>k-a-r$ is relabeled $\ell-1$.

So after step (1) the leaves are labeled by $[k]\setminus\\{k-a-r\\}$ and then
step (2) adjusts the labels to be in $[k-1]$. We also define the canonical
reduction sequence of $T$ to be

$\alpha(T)=(a_{2},a_{3},\ldots,a_{n})$

where $a_{2}{\bf:=}0$. Figure 9 shows the canonical reduction history for the
tree in its upper-left corner. So the tree $T=T_{8}$ has canonical reduction
sequence

$\alpha(T)=(0,1,2,1,0,1,5).$

In order to prove that the map $T\mapsto\alpha(T)$ is a bijection from
$\operatorname{RDT}_{n}$ to $\operatorname{tI}_{n-1}$ we will need the
following lemma.

######  Lemma 6.2.

Suppose that in a canonical reduction history we have three consecutive trees
$T$, $T^{\prime}=\psi_{a,r}(T)$, and
$T^{\prime\prime}=\psi_{a^{\prime},r^{\prime}}(T^{\prime})$.

  1. (a)

If $r\geq 2$ then

$a^{\prime}=a+1\text{ and }r^{\prime}=r-1.$

  2. (b)

If $r=1$ then

$a^{\prime}\leq a.$

###### Proof.

(a) Since $\psi_{a,r}$ was applied to $T$, that tree’s leftmost visible
duplication consisted of leaf pairs $\\{\ell,\ell-r\\}$ for
$\ell\in[n-a-r+1,n-a]$ where $a$ is maximum. In $T^{\prime}$, the leaf pair
$\\{n-a,n-a-r\\}$ was replaced by a leaf $n-a-1$ and the rest of the pairs
became $\\{\ell-1,\ell-r\\}$ for $\ell\in[n-a-r+1,n-a-1]$. Since $r\geq 2$
there is at least one such pair, and these pairs form a visible
$(a+1,r-1)$-duplication event in $T^{\prime}$. So to finish the demonstration,
we just need to show they are leftmost.

Suppose, towards a contradiction, that in $T^{\prime}$ there was a visible
$(a^{\prime\prime},r^{\prime\prime})$-duplication event with
$a^{\prime\prime}>a+1$. But then $n-a^{\prime\prime}\leq n-a-2$ and $n-a-2$ is
in one of the pairs for the $(a,r)$-duplication event in $T$. So the
$(a^{\prime\prime},r^{\prime\prime})$-duplication event in $T^{\prime}$ must
correspond to a duplication event in $T$ which is to the left of the
$(a,r)$-duplication event. This contradicts the fact that the
$(a,r)$-duplication event is leftmost in $T$.

(b) The proof is similar to that of the second paragraph of the demonstration
of (a). So it is left to the reader. ∎

######  Theorem 6.3.

The map $T\mapsto\alpha(T)$ is a bijection
$\operatorname{RDT}_{n}\rightarrow\operatorname{tI}_{n-1}$.

###### Proof.

We first need to show that the map is well defined in that
$\alpha(T)=(a_{2},\ldots,a_{n})\in\operatorname{tI}_{n-1}$. We have $a_{2}=0$
by definition. So we only need to verify that the inequalities in (I2) hold
for $d=2$. Taking into account that $\alpha(T)$ starts with index $2$, these
inequalities translate as

$a_{k}-1\leq a_{k+1}\leq k-1.$

We prove this by induction on $k$ where the base case is easy.

Assume that the inequalities hold for $k-1$ and let the canonical reduction
history trees of $T$ be as in (14). Also, adopt the notation of the previous
lemma where $T=T_{k+1}$, $T^{\prime}=T_{k}$, and $T^{\prime\prime}=T_{k-1}$.
So we wish to prove that

$a^{\prime}-1\leq a\leq k-1.$

The largest $a$ can be is if $T$ has a single visible duplication event
consisting of leaf pair $\\{1,2\\}$. Since $T$ has $k+1$ leaves, this results
in $a=(k+1)-2=k-1$ which is the desired upper bound. Cases (a) and (b) of
Lemma 6.2 immediately imply that $a\geq a^{\prime}-1$ which confirms the lower
bound.

To show we have a bijection we will construct the inverse. Given
$\alpha=(a_{2},a_{3},\ldots,a_{n})\in\operatorname{tI}_{n-1}$ we will
construct a sequence of trees $T_{2},T_{3},\ldots,T_{n}=T$ and nonnegative
integers $r_{2},r_{3},\ldots,r_{n}$. We start with $r_{2}=1$ and $T_{2}$ as
the unique tree in $\operatorname{RDT}_{2}$. Given $T_{k}$ and $r_{k}$ we
construct $T_{k+1}$ and $r_{k+1}$ as follows. First, we let

$r_{k+1}=\left\\{\begin{array}[]{ll}r_{k}+1&\mbox{if $a_{k+1}=a_{k}-1$,}\\\
1&\mbox{otherwise.}\end{array}\right.$

Letting $a=a_{k+1}$ and $r=r_{k+1}$, we create $T_{k+1}$ from $T_{k}$ by

  1. 1.

Each leaf $\ell>k-a-r$ is relabeled $\ell+1$.

  2. 2.

The leaf labeled $k-a+1$ is given a sibling $k-a-r+1$.

We leave the verification that this is well defined and the inverse of the map
$T\mapsto\alpha(T)$ as a straightforward exercise. ∎

##  7 Restricted growth functions

The reader will have noticed that Theorem 5.1 is only true for $d\geq 1$ and
so only applies starting with the poset $P_{4}$. It is natural to ask if
anything can be said about factorial posets which are special $P_{3}$-free,
and it turns out that these are in natural bijection with restricted growth
functions (RGFs). These sequences are a way of modeling set partitions and
have been widely studied [BKM22, CDD+18, Kad85, LF17, MNV11, Mil77, Mil78,
Mil82, SV17, Wac94, WW91]. We will also see how these sequences are related to
pattern avoidance, matrices, and matchings.

A restricted growth function (RGF) of length $n$ is a sequence of nonnegative
integers $\rho=r_{1}r_{2}\ldots r_{n}$ satisfying

  1. (r1)

$r_{1}=0$, and

  2. (r2)

$r_{k+1}\leq 1+\max\rho_{k}$ for $k\in[n-1]$,

where, as with $d$-ascent sequences, we let $\rho_{k}=r_{1}r_{2}\ldots r_{k}$
and the maximum of a sequence is the maximum value of its elements as
integers. Since $\rho_{k+1}=\rho_{k}r_{k+1}$ and $\rho$ is an RGF, it must be
that for all $k<n$ we have

$\max\rho_{k}\leq\max\rho_{k+1}\leq\max\rho_{k}+1,$ (15)

where $\rho_{k+1}$ achieving its upper bound forces $r_{k+1}=\max\rho_{k+1}$.
Let

$\operatorname{RGF}_{n}=\\{\rho\mid\text{$\rho$ is a restricted growth
function of length $n$}\\}.$

It is not hard to see that

$\operatorname{RGF}_{n}\subseteq\operatorname{A}_{n},$

the set of length $n$ ascent sequences. Also, the RGFs of length $n$ are in
natural bijection with the partitions of $[n]$ so that

$\\#\operatorname{RGF}_{n}=B_{n},$ (16)

the $n$th Bell number.

We will show that there is a bijection
$\operatorname{rp}:\operatorname{RGF}_{n}\rightarrow\operatorname{Av}_{n}(P_{3})$.
Given $\rho\in\operatorname{RGF}_{n}$ we define a poset
$P=\operatorname{rp}(\rho)$ by

$\text{$i<_{P}j$ if and only if $\max\rho_{i}<r_{j}$}.$ (17)

Note the similarity with the definition of $\operatorname{po}(\alpha)$ (9). We
must first show that this map is well defined.

######  Lemma 7.1.

If $\rho\in\operatorname{RGF}_{n}$ then
$P=\operatorname{rp}(\rho)\in\operatorname{Av}_{n}(P_{3})$.

###### Proof.

The fact that $P$ is a poset is proved in much the same way as in Lemma 5.3,
and so is omitted. To show that $P$ is factorial, assume $i<j$ and $j<_{P}k$.
Since $\rho_{i}$ is a subsequence of $\rho_{j}$ we have
$\max\rho_{i}\leq\max\rho_{j}$. Also, $j<_{P}k$ implies $\max\rho_{j}<r_{k}$.
So, by transitivity, $\max\rho_{i}<r_{k}$ which is equivalent to $i<_{P}j$.

We show that $P$ avoids a special $P_{3}$ by induction on $n$, where the
statement is obvious for $n\leq 2$. Assume, that for RGFs of length $n-1$
their image under $\operatorname{rp}$ is special $P_{3}$-free. Now consider an
RGF $\rho$ of length $n$ and assume, towards a contradiction, that
$P=\operatorname{rp}(\rho)$ contains a special $P_{3}$ labeled as

$j$$k$$j+1$

where $j+1<k$. Now the prefix $\rho^{\prime}=\rho_{n-1}$ of $\rho$ is of
length $n-1$. So, by induction, $P^{\prime}=\operatorname{rp}(\rho^{\prime})$
is special $P_{3}$-free. But by (17), the poset $P^{\prime}$ is the
restriction of $P$ to the elements of the set $[n-1]$. So the only way that
$P^{\prime}$ could avoid $P_{3}$ while $P$ contains a copy would be if that
copy includes $n$. Since $k$ is the largest integer in our copy, it must be
that $k=n$.

Now $j<_{P}n$ and $j+1\nless_{P}n$ implies
$\max\rho_{j}<r_{n}\leq\max\rho_{j+1}$. Combining the previous sentence with
equation (15) and the comment which follows it, we must have
$r_{j+1}=\max\rho_{j+1}=\max\rho_{j}+1$. But $j\nless_{P}j+1$ and so
$\max\rho_{j}\geq r_{j+1}$ which contradicts the previous sentence. ∎

In order to provide an inverse for $\operatorname{rp}$, we will need the
following lemmas. For $k$ in a factorial poset $P$ we will use the notation

$M(k)=\max\\{i\in P\mid i<_{P}k\\},$

where the maximum is taken in the integers. It follows easily from properties
of factorial posets that if $M(k)=m$ then

$\\{i\in P\mid i<_{P}k\\}=[m].$ (18)

######  Lemma 7.2.

If $\rho=r_{1}r_{2}\ldots r_{n}$ and $P=\operatorname{rp}(\rho)$ then for all
$k\in[n]$ we have

$r_{k}=\left\\{\begin{array}[]{ll}0&\mbox{if $k$ is minimal in $P$,}\\\
\max\rho_{M(k)}+1&\mbox{otherwise.}\end{array}\right.$ (19)

###### Proof.

Suppose first that $k$ is minimal in $P$. If $k=1$ then $r_{1}=0$ by
definition of an RGF. If $k>1$ then we must have $\max\rho_{j}\geq r_{k}$ for
all $j<k$. Letting $j=1$ this becomes $0=\max\rho_{1}\geq r_{k}$ which forces
$r_{k}=0$.

Now assume that $k$ is not minimal and let $m=M(k)$. Since $m<_{P}k$ we have
$\max\rho_{m}<r_{k}$. On the other hand, $m+1\nless_{P}r_{k}$ so that
$\max\rho_{m+1}\geq r_{k}$. Using the previous inequalities and equation (15)
gives $\max\rho_{m}<r_{k}\leq\max\rho_{m}+1$. This implies
$r_{k}=\max\rho_{m}+1$ as desired. ∎

Now we defined a map
$\operatorname{rp}^{-1}:\operatorname{Av}_{n}(P_{3})\rightarrow\operatorname{RGF}_{n}$
by letting $\operatorname{rp}^{-1}(P)$ be the sequence $\rho$ defined by
equation (19). Again, we need to worry about whether the map is well defined.

######  Lemma 7.3.

If $P\in\operatorname{Av}_{n}(P_{3})$ then
$\rho=\operatorname{rp}^{-1}(P)\in\operatorname{RGF}_{n}$.

###### Proof.

We claim that since $P$ is factorial we must have that $1$ is a minimal
element. Suppose this were not the case. Then the set of elements below $1$
would not form an inverval of the form $[m]$ for some $m>2$ since all such
intervals contain $1$, which contradicts (18). But $1$ being minimal means
that $\rho_{1}=0$ as needed for an RGF.

We now prove that (r2) in the definition of an RGF holds. If $k$ is minimal
then $r_{k}=0$ and the inequality is trivial. If $k$ is not minimal then let
$m=M(k)$. Since $P$ is factorial we have $m\leq k-1$. It follows that
$\max\rho_{m}\leq\max\rho_{k-1}$. Combining this with (19) gives

$r_{k}=\max\rho_{m}+1\leq\max\rho_{k-1}+1$

which is what we wished to prove. ∎

We can now show that the maps $\operatorname{rp}$ and $\operatorname{rp}^{-1}$
are indeed inverses. We compose functions from right to left.

######  Theorem 7.4.

The map
$\operatorname{rp}:\operatorname{RGF}_{n}\rightarrow\operatorname{Av}_{n}(P_{3})$
is a bijection with inverse $\operatorname{rp}^{-1}$. Thus

$\\#\operatorname{Av}_{n}(P_{3})=B_{n}.$

###### Proof.

By (16), the cardinality result will follow once we know that
$\operatorname{rp}$ is a bijection.

Since equation (19) was shown to hold for $\operatorname{rp}$ and then used to
define $\operatorname{rp}^{-1}$, we automatically have that
$\operatorname{rp}^{-1}\circ\operatorname{rp}$ is the identity map. For the
other composition, consider $P\in\operatorname{Av}_{n}(P_{3})$ and let
$\rho=\operatorname{rp}^{-1}(P)$ and $P^{\prime}=\operatorname{rp}(\rho)$. By
induction on $n$ we can assume that $P$ equals $P^{\prime}$ when both are
restricted to $[n-1]$. There are now two cases depending on the element $n$.
Note that since $P$ and $P^{\prime}$ are both naturally labeled, it suffices
to consider the elements below $n$ in the two posets.

Suppose first that $n$ is minimal in $P$. By the definition of
$\operatorname{rp}^{-1}$ we have $r_{n}=0$. But then there is no $i$ with
$\max\rho_{i}<r_{n}$. So $n$ is also minimal in $P^{\prime}$ and we are done.

If $n$ is not minimal in $P$ then let $m=M(n)$ computed in $P$. We need to
show that $m$ is the element of maximum label below $n$ in $P^{\prime}$. First
note that by (19) we have

$r_{n}=\max\rho_{m}+1.$

So, in particular, $\max\rho_{m}<r_{n}$ and the definition of
$\operatorname{rp}$ implies $m<_{P^{\prime}}n$. Thus we will be done if we can
prove that $m+1\nless_{P^{\prime}}n$. If, instead, we have
$m+1<_{P^{\prime}}n$ then this is equivalent to $\max\rho_{m+1}<r_{n}$.
Combining this with the previous displayed equation gives

$\max\rho_{m}\leq\max\rho_{m+1}<r_{n}=\max\rho_{m}+1.$

It follows that

$\max\rho_{m+1}=\max\rho_{m}.$

Now recall that $P$ has no special $P_{3}$. But $m<_{P}n$ and $m+1\nless_{P}n$
so we must have $m+1>_{P}m$ otherwise $m$, $m+1$, and $n$ form a special
$P_{3}$. And since $m,m+1$ are consecutive integers this forces $m=M(m+1)$
computed in $P$. Now (19) implies $r_{m+1}=\max\rho_{m}+1$. This in turn
yields $\max\rho_{m+1}=\max\rho_{m}+1$ which directly contradicts the previous
displayed equation. ∎

We will now make a connection between RGFs and pattern avoidance. Claesson
[Cla01] showed that the number of permutations in $S_{n}$ avoiding any of the
following vincular patterns is the Bell number, $B_{n}$:

$1|23,12|3,1|32,21|3,23|1,3|12,3|21,32|1$

These are trivially Wilf equivalent to the bivincular patterns

$\overline{1}23,1\overline{2}3,\overline{1}32,\overline{2}13,23\overline{1},31\overline{2},3\overline{2}1,32\overline{1}.$

We will translate a version of one of his bijections from set partitions into
the language of RGFs. Given $\rho=r_{1}r_{2}\ldots
r_{n}\in\operatorname{RGF}_{n}$ we form a permutation $\pi=p_{1}p_{2}\ldots
p_{n}\in S_{n}$ as follows. Suppose the indices for which $r_{i}=0$ are

$1=i_{1}<i_{2}<\ldots<i_{k}.$ (20)

Then $\pi$ will start with the initial segment

$\pi_{k}=i_{k}i_{k-1}\ldots i_{1}.$

Now let the indices for which $r_{j}=1$ be

$j_{1}<j_{2}<\ldots<j_{l}.$ (21)

Continue building $\pi$ so that

$\pi_{k+l}=\pi_{k}j_{l}j_{l-1}\ldots j_{1}.$

The rest of $\pi$ is built in a similar manner.

######  Proposition 7.5 ([Cla01]).

The map $\rho\mapsto\pi$ is a bijection $\operatorname{RGF}_{n}\rightarrow
S_{n}(23|1)$. ∎

There is also a standard way to associate with any RGF a strictly upper-
triangular, $0$-$1$ matrix. This is usually expressed in the language of set
partitions and rook placements on a triangular Ferrers board. We mention it
here in translation. Given $\rho\in\operatorname{RGF}_{n}$ we will associate
an $n\times n$ matrix $M$ with rows and columns indexed by $[n]$. Start with
$M$ being the zero matrix. Now consider the indices in (20) and for each
adjacent pair $(i,j)=(i_{a},i_{a+1})$ set $M_{i,j}=1$ giving $k-1$ nonzero
entries. Continue with the sequence (21), letting $M_{i,j}=1$ for each pair
$(i,j)=(j_{b},j_{b+1})$, and so forth.

######  Proposition 7.6.

The map $\rho\mapsto M$ is a bijection between $\operatorname{RGF}_{n}$ and
$n\times n$ strictly upper-triangular, $0$-$1$ matrices. ∎

One can also associate with each RGF a perfect matching by restricting the
Claesson-Linusson bijection [CL11] to the inversion sequences which are RGFs.
However, the description of the image seems a bit contrived and so we will
leave the details to the reader.

##  8 Comments and open questions

We collect here some of the problems suggested by our work.

###  8.1 More on matrices

Notice that Theorem 2.1 only applies for $d\geq 1$. But a similar result holds
for $d=0$ and the set of ascent sequences $\operatorname{A}_{n}$.
Specifically, factor an ascent sequence
$\alpha=\delta_{0}\delta_{1}\ldots\delta_{m}$ by breaking at every ascent. So
the $\delta_{i}$ are maximal weakly decreasing factors of $\alpha$. Now use
(4) to construct a matrix $\operatorname{mx}(\alpha)$. Note that since the
$\delta_{i}$ weakly decrease, it is possible to add the same $E_{i,j}$
multiple times so that the entries of the final matrix can be larger than one.
In fact, it is not hard to see that the image of the map is the set
$\operatorname{Mtx}_{n}$ of all matrices $M$ who entries sum to $n$ and have
the following properties.

  1. (Ma)

$M$ is upper triangular with nonnegative integer entries.

  2. (Mb)

There are no zero columns in $M$, and for all column indicies $j$

$\operatorname{rmax}c_{j}>\operatorname{rmin}c_{j-1}.$

Thus, we have the following result

######  Theorem 8.1.

For $n\geq 0$ the map
$\operatorname{mx}:\operatorname{A}_{n}\rightarrow\operatorname{Mtx}_{n}$ is a
bijection. Consequently

${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\qed}\hfill{\displaystyle\\#\operatorname{A}_{n}=\\#\operatorname{Mtx}_{n}}\hfill\qed$

Dukes and Parviainen [DP10] have shown that ascent sequences are in bijection
with another set of upper triangular matrices. Let
$\operatorname{Mtx}^{\prime}_{n}$ be the set of all matrices $M$ whose entries
sum to $n$ and which satisfy (Ma) and

  1. (Mc)

There are no zero rows or columns in $M$.

######  Theorem 8.2 ([DP10]).

There is a bijection
$\operatorname{mx}^{\prime}:\operatorname{A}_{n}\rightarrow\operatorname{Mtx}^{\prime}_{n}$.
∎

######  Problem 8.3.

Find a direct bijection
$\operatorname{Mtx}_{n}\rightarrow\operatorname{Mtx}^{\prime}_{n}$ without
composing $\operatorname{mx}^{-1}$ and $\operatorname{mx}^{\prime}$.

###  8.2 More on permutations and posets

The inequalities in Theorems 4.2 and 5.1 can be strict for $d\geq 2$. This
raises the question of how different $\\#\operatorname{dA}_{n}$ can be from
$\\#\operatorname{Av}_{n}(\sigma_{d+3})$ and from
$\\#\operatorname{Av}_{n}(P_{d+3})$. One could also ask if equality could be
obtained by enlarging the set of patterns or posets to be avoided.
Specifically, we have the following questions.

######  Question 8.4.

Fix $d\geq 2$.

  1. (a)

Does
$\lim_{n\rightarrow\infty}\\#\operatorname{dA}_{n}/\\#\operatorname{Av}_{n}(\sigma_{d+3})$
exists and, if so, what is its value?

  2. (b)

Is there a set $\Sigma_{d}$ of bivincular patterns containing $\sigma_{d}$
such that $\\#\operatorname{dA}_{n}=\\#\operatorname{Av}_{n}(\Sigma_{d+3})$
for $n\geq 0$?

  3. (c)

Answer the analogues of (a) and (b) for posets.

###  8.3 More on rooted duplication trees

Recall that Theorem 6.3 only holds for $d=2$. So a natural question to ask is
the following.

######  Question 8.5.

For $d\geq 3$, is there a generalization $\operatorname{dRDT}_{n}$ of the set
$\operatorname{RDT}_{n}$ (rooted duplication trees with $n$ leaves) which is
in bijection with $\operatorname{dI}_{n-1}$ ($d$-increasing $d$-ascent
sequences of length $n-1$)?

We note that there is an obvious analogue of rooted duplication trees which
model the duplication of a factor in a gene sequence $d$ times rather than
just twice. This results in a set of rooted $d$-ary trees with labeled leaves.
Unfortunately, these tree are more numerous than $d$-increasing $d$-ascent
sequences.

###  8.4 Generating functions

$d\setminus n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
0 | 1 | 1 | 2 | 5 | 15 | 53 | 217 | 1014 | 5335 | 31240 | 201608
1 | 1 | 1 | 2 | 6 | 23 | 106 | 567 | 3440 | 23286 | 173704 | 1414102
2 | 1 | 1 | 2 | 6 | 24 | 118 | 682 | 4506 | 33376 | 273200 | 2444274
3 | 1 | 1 | 2 | 6 | 24 | 120 | 714 | 4896 | 37854 | 324792 | 3055320
4 | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5016 | 39624 | 348840 | 3378192
5 | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5040 | 40200 | 358800 | 3534120
6 | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5040 | 40320 | 362160 | 3600720
Table 3: The values of $\\#\operatorname{dA}_{n}$ for $d\leq 6$ and $n\leq 10$

Let $a_{n}=\\#\operatorname{A}_{n}$, the number of ascent sequences of length
$n$. In [BMCDK10] the generating function for $a_{n}$ was derived using the
kernel method. This series had been shown earlier by Zagier [Zag01] to count
matchings with neither left nor right nestings.

######  Theorem 8.6 ([BMCDK10]).

We have

${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\qed}\hfill{\displaystyle\sum_{n\geq
0}a_{n}t^{n}=\sum_{n\geq
0}\prod_{i=1}^{n}\left(1-(1-t)^{i}\right).}\hfill\qed$

######  Problem 8.7.

Find the generating function for $\\#\operatorname{dA}_{n}$ for all $d\geq 0$.
A table of these values for $d\leq 6$ and $n\leq 10$ is given in 3

It is not hard to at least find a functional equation that might be of use to
solve the previous problem. Suppose $d=1$ so we are considering weak ascents.
Define

$W(u,v)=W(t;u,v)=\sum_{n\geq
0}\sum_{\alpha\in\operatorname{wA}_{n}}t^{n}u^{\operatorname{wasc}\alpha}v^{a_{n}}$

where $a_{n}$ is the last element of $\alpha$. The next result can be easily
derived by considering how the possible last elements of $\alpha$ affect the
number of weak ascents.

######  Proposition 8.8.

We have

$[v-1+t(u-1)]W(u,v)=[(1+t)(v-1)+tu(1-v^{2})]-tW(u,1)+tuv^{2}W(uv,1).\ \qed$

It would also be nice to have a generating function for
$\operatorname{di}_{n}$, the number of $d$-increasing $d$-ascent sequences of
length $n$, and not just the recursion in Theorem 6.1. Note that for $d=0$ or
$d=1$ this sequence is the all ones or Catalan number sequence, respectively,
whose generating functions are well known.

######  Problem 8.9.

Find the generating function for
$\operatorname{di}_{n}=\\#\operatorname{dI}_{n}$ for all $d\geq 0$. A table of
these values for $d\leq 6$ and $n\leq 10$ is given in 4

Enumeration of lattice paths may be helpful with this problem. Take
$\alpha=a_{1}a_{2}\ldots a_{n}\in\operatorname{dI}_{n}$ and form the sequence
$\alpha^{\prime}=a_{1}^{\prime}a_{2}^{\prime}\ldots a_{n}^{\prime}$ where
$a_{k}^{\prime}=a_{k}+(k-1)(d-1)$ for $k\in[n]$. From properties (I1) and (I2)
one sees that

  1. (I1’)

$a_{1}^{\prime}=0$, and

  2. (I2’)

$a_{k}^{\prime}\leq a_{k+1}^{\prime}\leq kd$ for $k\in[n-1]$

Letting $a_{k}^{\prime}$ be the height of the $k$th east step, one obtains a
lattice path using north and east steps and staying inside a cone. It may also
be advantageous to do a linear transformation so that the paths in question
are restricted to the first quadrant, although now the two steps used will not
be as simple as in the conical case.

$d\setminus n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
---|---|---|---|---|---|---|---|---|---|---|---
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1
1 | 1 | 1 | 2 | 5 | 14 | 42 | 132 | 429 | 1430 | 4862 | 16796
2 | 1 | 1 | 2 | 6 | 22 | 92 | 420 | 2042 | 10404 | 54954 | 298648
3 | 1 | 1 | 2 | 6 | 24 | 114 | 612 | 3600 | 22680 | 150732 | 1045440
4 | 1 | 1 | 2 | 6 | 24 | 120 | 696 | 4512 | 31920 | 242160 | 1942800
5 | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 4920 | 37200 | 305280 | 2680800
6 | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5040 | 39600 | 341280 | 3175200
Table 4: The values of $\\#\operatorname{dI}_{n}$ for $d\leq 6$ and $n\leq 10$

## References

  * [BCD23] Beáta Bényi, Anders Claesson, and Mark Dukes.  Weak ascent sequences and related combinatorial structures.  European J. Combin., 108:Paper No. 103633, 19, 2023.
  * [BKM22] Aubrey Blecher, Arnold Knopfmacher, and Toufik Mansour.  Alphabetic points in restricted growth functions.  Discrete Appl. Math., 309:130–137, 2022.
  * [BMCDK10] Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, and Sergey Kitaev.  $(2+2)$-free posets, ascent sequences and pattern avoiding permutations.  J. Combin. Theory Ser. A, 117(7):884–909, 2010.
  * [CCEPG22] Andrew R. Conway, Miles Conway, Andrew Elvey Price, and Anthony J. Guttmann.  Pattern-avoiding ascent sequences of length 3.  Electron. J. Combin., 29(4):Paper No. 4.25, 32, 2022.
  * [CDD+13] William Y. C. Chen, Alvin Y. L. Dai, Theodore Dokos, Tim Dwyer, and Bruce E. Sagan.  On 021-avoiding ascent sequences.  Electron. J. Combin., 20(1):Paper 76, 6, 2013.
  * [CDD+18] Lindsey R. Campbell, Samantha Dahlberg, Robert Dorward, Jonathan Gerhard, Thomas Grubb, Carlin Purcell, and Bruce E. Sagan.  Restricted growth function patterns and statistics.  Adv. in Appl. Math., 100:1–42, 2018.
  * [CDK11] Anders Claesson, Mark Dukes, and Sergey Kitaev.  A direct encoding of Stoimenow’s matchings as ascent sequences.  Australas. J. Combin., 49:47–59, 2011.
  * [CL11] Anders Claesson and Svante Linusson.  $n!$ matchings, $n!$ posets.  Proc. Amer. Math. Soc., 139(2):435–449, 2011.
  * [Cla01] Anders Claesson.  Generalized pattern avoidance.  European J. Combin., 22(7):961–971, 2001.
  * [CSV76] L. Carlitz, Richard Scoville, and Theresa Vaughan.  Enumeration of pairs of sequences by rises, falls and levels.  Manuscripta Math., 19(3):211–243, 1976.
  * [DM19] Mark Dukes and Peter R. W. McNamara.  Refining the bijections among ascent sequences, $(2+2)$-free posets, integer matrices and pattern-avoiding permutations.  J. Combin. Theory Ser. A, 167:403–430, 2019.
  * [DP10] Mark Dukes and Robert Parviainen.  Ascent sequences and upper triangular matrices containing non-negative integers.  Electron. J. Combin., 17(1):Research Paper 53, 16, 2010.
  * [DS11] Paul Duncan and Einar Steingrímsson.  Pattern avoidance in ascent sequences.  Electron. J. Combin., 18(1):Paper 226, 17, 2011.
  * [Duk16] Mark Dukes.  Generalized ballot sequences are ascent sequences.  Australas. J. Combin., 64:61–63, 2016.
  * [FJL+20] Shishuo Fu, Emma Yu Jin, Zhicong Lin, Sherry H. F. Yan, and Robin D. P. Zhou.  A new decomposition of ascent sequences and Euler-Stirling statistics.  J. Combin. Theory Ser. A, 170:105141, 31, 2020.
  * [Fr75] Ralph Fröberg.  Determination of a class of Poincaré series.  Math. Scand., 37(1):29–39, 1975.
  * [GHJMM03] Olivier Gasceul, Michael D. Hendy, Alain Jean-Marie, and Robert McLachlan.  The combinatorics of tandem duplication trees.  Syst. Biol., 52(1):110–118, 2003.
  * [JS23] Emma Yu Jin and Michael J. Schlosser.  Proof of a bi-symmetric septuple equidistribution on ascent sequences.  Comb. Theory, 3(1):Paper No. 5, 44, 2023.
  * [Kad85] Kevin W. J. Kadell.  Weighted inversion numbers, restricted growth functions, and standard Young tableaux.  J. Combin. Theory Ser. A, 40(1):22–44, 1985.
  * [KR17] Sergey Kitaev and Jeffrey B. Remmel.  A note on p-ascent sequences.  J. Comb., 8(3):487–506, 2017.
  * [LF17] Zhicong Lin and Shishuo Fu.  On 1212-avoiding restricted growth functions.  Electron. J. Combin., 24(1):Paper No. 1.53, 20, 2017.
  * [LF21] Zhicong Lin and Shishuo Fu.  On $\underline{12}0$-avoiding inversion and ascent sequences.  European J. Combin., 93:Paper No. 103282, 12, 2021.
  * [Mil77] Stephen Milne.  Restricted growth functions and incidence relations of the lattice of partitions of an $n$-set.  Advances in Math., 26(3):290–305, 1977.
  * [Mil78] Stephen C. Milne.  A $q$-analog of restricted growth functions, Dobinski’s equality, and Charlier polynomials.  Trans. Amer. Math. Soc., 245:89–118, 1978.
  * [Mil82] Stephen C. Milne.  Restricted growth functions, rank row matchings of partition lattices, and $q$-Stirling numbers.  Adv. in Math., 43(2):173–196, 1982.
  * [MNV11] Toufik Mansour, Ghalib Nassar, and Vincent Vajnovszki.  Loop-free Gray code algorithm for the $\bf e$-restricted growth functions.  Inform. Process. Lett., 111(11):541–544, 2011.
  * [MS14] Toufik Mansour and Mark Shattuck.  Some enumerative results related to ascent sequences.  Discrete Math., 315:29–41, 2014.
  * [Pud16] Lara K. Pudwell.  Ascent sequences and the binomial convolution of Catalan numbers.  Australas. J. Combin., 64:21–43, 2016.
  * [Sag20] Bruce E. Sagan.  Combinatorics: the art of counting, volume 210 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, [2020] ©2020.
  * [SV17] Ahmad Sabri and Vincent Vajnovszki.  More restricted growth functions: Gray codes and exhaustive generation.  Graphs Combin., 33(3):573–582, 2017.
  * [Wac94] Michelle L. Wachs.  $\sigma$-restricted growth functions and $p,q$-Stirling numbers.  J. Combin. Theory Ser. A, 68(2):470–480, 1994.
  * [WW91] Michelle Wachs and Dennis White.  $p,q$-Stirling numbers and set partition statistics.  J. Combin. Theory Ser. A, 56(1):27–46, 1991.
  * [Yan18] Sherry H. F. Yan.  Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions.  Appl. Math. Comput., 325:24–30, 2018.
  * [Zag01] Don Zagier.  Vassiliev invariants and a strange identity related to the Dedekind eta-function.  Topology, 40(5):945–960, 2001.