Ascent Sequences and 3-Nonnesting Set Partitions

Sherry H. F. Yan
Department of Mathematics, Zhejiang Normal University, Jinhua 321004, P.R.
China
<EMAIL_ADDRESS>

Abstract. A sequence $x=x_{1}x_{2}\ldots x_{n}$ is said to be an ascent
sequence of length $n$ if it satisfies $x_{1}=0$ and $0\leq x_{i}\leq
asc(x_{1}x_{2}\ldots x_{i-1})+1$ for all $2\leq i\leq n$, where
$asc(x_{1}x_{2}\ldots x_{i-1})$ is the number of ascents in the sequence
$x_{1}x_{2}\ldots x_{i-1}$. Recently, Duncan and Steingrímsson proposed the
conjecture that 210-avoiding ascent sequences of length $n$ are equinumerous
with 3-nonnesting set partitions of $\\{1,2,\ldots,n\\}$. In this paper, we
confirm this conjecture by showing that 210-avoiding ascent sequences of
length $n$ are in bijection with 3-nonnesting set partitions of
$\\{1,2,\ldots,n\\}$ via an intermediate structure of growth diagrams for
$01$-fillings of Ferrers shapes.

Key words: ascent sequence, pattern avoiding, 3-nonnesting set partition,
growth diagram, $01$-filling of Ferrers shape.

AMS Mathematical Subject Classifications: 05A05, 05C30.

##  1 Introduction

The objective of this paper is to establish a bijection between 210-avoiding
ascent sequences of length $n$ and 3-nonnesting set partitions of
$\\{1,2,\ldots,n\\}$. Let us give an overview of the notation and terminology.

Given a sequence of integers $x=x_{1}x_{2}\ldots x_{n}$, we say that the
sequence $x$ has an ascent at position $i$ if $x_{i}<x_{i+1}$. The number of
ascents of $x$ is denoted by $asc(x)$. A sequence $x=x_{1}x_{2}\ldots x_{n}$
is said to be an ascent sequence of length $n$ if it satisfies $x_{1}=0$ and
$0\leq x_{i}\leq asc(x_{1}x_{2}\ldots x_{i-1})+1$ for all $2\leq i\leq n$.
Ascent sequences were introduced by Bousquet-M$\acute{e}$lou et al. [1] in
their study of $(2+2)$-free posets. Ascent sequences are closely connected to
many other combinatorial structures. Bousquet-M$\acute{e}$lou et al. [1]
constructed bijections between unlabeled $(2+2)$-free posets and ascent
sequences, between ascent sequences and permutations avoiding a certain
pattern, between unlabeled $(2+2)$-free posets and a class of involutions
introduced by Stoimenow [7]. Dukes and Parviainen [3] established a bijection
between ascent sequences and upper triangular matrices with non-negative
integer entries such that all rows and columns contain at least one non-zero
entry. We call an ascent sequence with no two consecutive equal entries a
primitive ascent sequence. For example, the sequence $0120234603$ is a
primitive ascent sequence of length $10$.

Analogous to pattern avoidance on permutations, Duncan and Steingrímsson [4]
initiated the study of ascent sequences avoiding certain patterns. For ascent
sequences, a pattern  is a word on nonnegative integers $\\{0,1,\ldots,k\\}$,
where each element appears at least once. Given an ascent sequence
$x=x_{1}x_{2}\ldots x_{n}$ and a pattern
$\tau=\tau_{1}\tau_{2}\ldots\tau_{k}$, we say that a subsequence
$x_{i_{1}}x_{i_{2}}\ldots x_{i_{k}}$ of $x$ is a pattern of $\tau$ if it is
order-isomorphic to $\tau$. If $x$ contains no subsequence of pattern $\tau$,
then we say that $x$ is $\tau$-avoiding. Denote by $\mathcal{A}_{n}(\tau)$ and
$\mathcal{PA}_{n}(\tau)$ the set of $\tau$-avoiding ordinary and primitive
ascent sequences, respectively. Duncan and Steingrímsson [4] proved that
$|\mathcal{A}_{n}(\tau)|=C_{n}$, the $n$th Catalan number, for any
$\tau=101,0101$ or $021$. Moreover, they proposed the following conjecture.

###### Conjecture 1.1

210-avoiding ascent sequences of length $n$ are equinumerous with 3-nonnesting
(3-noncrossing) set partitions of $\\{1,2,\ldots,n\\}$.

Note that Mansour and Shattuck [6] recently derived two recurrence relations
on the generating function for 210-avoiding ascent sequences. However, as
remarked by Mansour and Shattuck, the conjecture is still open.

Recall that a set partition $P$ of $[n]=\\{1,2,\ldots,n\\}$ can be represented
by a diagram with vertices drawn on a horizontal line in increasing order. For
a block $B$ of $P$, we write the elements of $B$ in increasing order. Suppose
that $B=\\{i_{1},i_{2},\ldots,i_{k}\\}$. Then we draw an arc from $i_{1}$ to
$i_{2}$, an arc from $i_{2}$ to $i_{3}$, and so on. Such a diagram is called
the linear representation of $P$, see Figure 1 for an example. We say that $k$
arcs $(i_{1},j_{1}),(i_{2},j_{2}),\ldots,(i_{k},j_{k})$ form a $k$-crossing if
$i_{1}<i_{2}<\ldots<i_{k}<j_{1}<j_{2}<\ldots<j_{k}$. A partition without any
$k$-crossing is said to be k-noncrossing. Similarity, a $k$-nesting is a set
of $k$ arcs $(i_{1},j_{1}),(i_{2},j_{2}),\ldots,(i_{k},j_{k})$ such that
$i_{1}<i_{2}<\ldots<i_{k}<j_{k}<\ldots<j_{2}<j_{1}$. A set partition without
any $k$-nesting is said to be k-nonnesting. Chen et al. [2] proved that
k-nonnesting set partitions of $[n]$ are equinumerous with k-noncrossing set
partitions of $[n]$ bijectively using vacillating tableaux as an intermediate
object.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$ Figure 1:  The linear representation of a set
partition $\pi=\\{\\{1,2,3,4,6,10\\},\\{5,8\\},\\{7,9\\}\\}$ .

In this paper, we aim to establish a bijection between $210$-avoiding ascents
sequences of length $n$ and $3$-nonnesting set partitions of $[n]$ via an
intermediate structure of growth diagrams for $01$-fillings of Ferrers shapes
described in [5] and [8].

##  2  Growth diagrams for $01$-fillings of Ferrers shapes

Our bijection between $210$-avoiding ascent sequences and $3$-nonnesting set
partitions will be accomplished by the growth diagram for $01$-fillings of
Ferrers shapes [5]. Before we describe the growth diagram for $01$-fillings of
Ferrers shapes, we give an overview of the notation and terminology.

A partition $\lambda$ of a positive integer $n$ is defined to be a sequence
$(\lambda_{1},\lambda_{2},\ldots,\lambda_{m})$ of nonnegative integers such
that $\lambda_{1}+\lambda_{2}+\ldots\lambda_{m}=n$ and
$\lambda_{1}\geq\lambda_{2}\ldots\geq\lambda_{m}$. The empty partition is
denoted by $\emptyset$. For the sake of convenience, we identify a partition
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{m})$ with the infinite
sequence $(\lambda_{1},\lambda_{2},\ldots,\lambda_{m},0,0,\ldots)$, that is,
the sequence obtained from $\lambda$ by appending infinitely many $0$’s. Given
a partition $\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{m})$, its
Ferrers diagram is the left-justified array of
$\lambda_{1}+\lambda_{2}+\ldots+\lambda_{m}$ squares with $\lambda_{1}$
squares in the first row, $\lambda_{2}$ squares in the second row, and so on.
The partial order $\subseteq$ on partitions is defined by the containment of
their Ferrers diagrams. The conjugate  of a partition $\lambda$ is the
partition $(\lambda^{\prime}_{1},\ldots,\lambda^{\prime}_{\lambda_{1}})$ where
$\lambda^{\prime}_{j}$ is the length of the $j$th column in the Ferrers
diagram of $\lambda$.

A Ferrers shape is a Ferrers diagrams in French notation which has straight
left side, straight bottom side and supports a descending staircase. We can
also encode a Ferrers shape $F$ by sequences of $D^{\prime}s$ and
$R^{\prime}s$ by tracing the right/up boundary of $F$ from top-left to bottom-
right and writing $D$ (resp. $R$) whenever we encounter a down-step (resp.
right-step). For example, the Ferrers shape in Figure 2 can be represented by
$RRDDRDRD$.

A $01$-filling of a Ferrers shape is obtained by filling each cells of $F$
with $1^{\prime}s$ and $0^{\prime}s$, see Figure 2 for an example, where we
present $1^{\prime}s$ by $\bullet$ and suppress the $0$’s. A NE-chain of a
$01$-filling is a sequence of $1^{\prime}s$ such that any $1$ is strictly
above and weakly to the right of the preceding $1$ in the sequence. A SE-chain
of a $01$-filling is a sequence of $1^{\prime}s$ such that any $1$ is weakly
below and strictly to the right of the preceding $1$ in the sequence. The
length of a $NE$-chain or a $SE$-chain is defined to the number of $1$’s in
the chain.

$\bullet$$\bullet$$\bullet$$\bullet$ Figure 2:  Example of a $01$-filling of a
Ferrers shape.

The growth diagram for a $01$-filling of Ferrers shape $F$ is obtained by
labelling the corners of all the squares in $F$ by partitions in such a way
that the partition assigned to any corner is either equal to the partition to
its left or is obtained from it by adding a horizontal strip, that is, by a
set of squares no two of which are in the same column, and the partition
assigned to any corner either equals the partition below it or is obtained
from this partition by adding a vertical strip, that is, by a set of squares
no two of which are in the same row. We start by assigning the partition
$\emptyset$ to each corner on the left and bottom edges of $F$. Then assign
the partitions to the other corners inductively by applying the following
forward algorithm. Consider the cell in Figure 3, filled by $m=0$ or $m=1$ and
labeled by the partitions $\rho$, $\mu$, $\upsilon$, where $\rho\subseteq\mu$
and $\rho\subseteq\upsilon$, $\mu$ and $\rho$ differ by a horizontal strip,
and $\upsilon$ and $\rho$ differ by a vertical strip. Then $\lambda$ is
determined by the following algorithm.

  * (F0)

Set $CARRY:=m$ and $i:=1$.

  * (F1)

Set $\lambda_{i}=max\\{\mu_{i}+CARRY,\upsilon_{i}\\}$.

  * (F2)

If $\lambda_{i}=0$, then stop. The output of the algorithm is
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{i-1})$. If not, then set
$CARRY:=min\\{\mu_{i}+CARRY,\upsilon_{i}\\}-\rho_{i}$ and $i:=i+1$. GO to
(F1).

$m$$\rho$$\mu$$\upsilon$$\lambda$ Figure 3:  A cell filled with $m$.

Conversely, given a labelling of the corners along the right/up border of a
Ferrer shape $F$, one can reconstruct the labels of the other corners and a
$01$-filling of $F$ inductively by applying the following backward algorithm.
Consider the cell in Figure 3 labelled by the partitions
$\mu,\upsilon,\lambda$, where $\mu\subseteq\lambda$ and
$\upsilon\subseteq\lambda$, where $\lambda$ and $\mu$ differ by a vertical
strip, and $\lambda$ and $\upsilon$ differ by a horizontal strip, the backward
algorithm works in the following way.

  * (B0)

Set $i:=max\\{j:\lambda_{j}\,\,\mbox{is positive}\\}$ and $CARRY:=0$.

  * (B1)

Set $\rho_{i}=min\\{\mu_{i},\upsilon_{i}-CARRY\\}$.

  * (B2)

Set $CARRY:=\lambda_{i}-max\\{\mu_{i},\upsilon_{i}-CARRY\\}$ and $i:=i-1$. If
$i=0$, then stop. The output of the algorithm is
$\rho=(\rho_{1},\rho_{2},\ldots)$ and $m=CARRY$. If not, go to (B1).

$\bullet$$\bullet$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$1$$1$$11$$\emptyset$$\emptyset$$1$$1$$\bullet$$\emptyset$$\emptyset$$2$$\bullet$$\emptyset$$1$$21$
Figure 4:  The growth diagram for the $01$-filling in Figure 2.

###### Theorem 2.1

(See [5], Theorem 9) Let $F$ be a Ferrers shape given by $D-R$-sequence
$w=w_{1}w_{2}\ldots w_{k}$. Then $01$-fillings of $F$ are in bijection with
sequences $(\emptyset=\lambda^{0},\lambda^{1},\ldots,\lambda^{k}=\emptyset)$
where $\lambda^{i+1}$ is obtained from $\lambda^{i}$ by doing nothing (i.e.,
$\lambda^{i+1}=\lambda^{i}$) or adding a horizontal strip if $w_{i}=R$,
whereas $\lambda^{i}$ is obtained from $\lambda^{i-1}$ by doing nothing or
deleting a vertical strip if $w_{i}=D$.

###### Theorem 2.2

(See [5], Theorem 10) Given a diagram with empty partitions labelling all the
corners along the left side and the bottom side of the Ferrers shape, suppose
that the corner $c$ is labelled by the partition
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{l})$. Then $\lambda_{1}$ is
the length of the longest $NE$-chain in the rectangular region to the left and
below of $c$, and $\lambda^{\prime}_{1}$ is the length of the longest
$SE$-chain in the same rectangular region.

###### Lemma 2.3

Given a $01$-filling of Ferrers shape $F$ given by $D-R$-sequence
$w=w_{1}w_{2}\ldots w_{k}$, let
$(\emptyset=\lambda^{0},\lambda^{1},\ldots,\lambda^{k}=\emptyset)$ be its
corresponding sequence. Then $\lambda^{i}$ is obtained from $\lambda^{i-1}$ by
adding a square if and only if there is exaclty one $1$ in the column of the
cells of $F$ below the corners labeled by $\lambda^{i-1}$ and $\lambda^{i}$,
and $\lambda^{i}$ is obtained from $\lambda^{i-1}$ by deleting a square if and
only if there is exactlty one $1$ in the row of the cells of $F$ to the left
of the corners labeled by $\lambda^{i-1}$ and $\lambda^{i}$.

Proof. Let $c$ be a cell of $F$ illustrated as Figure 3, which is filled by
$m=0$ or $m=1$ and labeled by the partitions $\rho$, $\mu$, $\upsilon$, where
$\rho\subseteq\mu$ and $\rho\subseteq\upsilon$, $\mu$ and $\rho$ differ by at
most one square, and $\upsilon$ and $\rho$ differ by at most one square. In
order to prove the lemma, it suffices to show that $\lambda$ has the following
properties.

  * (a)

If $m=0$ and $\rho=\upsilon$, then $\lambda=\mu$.

  * (b)

If $m=1$ and $\rho=\upsilon$, then $\lambda$ and $\mu$ differ by a square.

  * (c)

If $m=0$ and $\rho$ and $\upsilon$ differ by a square, then $\lambda$ and
$\mu$ differ by a square.

  * (d)

If $m=0$ and $\rho=\mu$, then $\lambda=\upsilon$.

  * (e)

If $m=1$ and $\rho=\mu$, then $\lambda$ and $\upsilon$ differ by a square.

  * (f)

If $m=0$ and $\rho$ and $\mu$ differ by a square, then $\lambda$ and
$\upsilon$ differ by a square.

Here we reformulate the forward algorithm in a slightly different, but of
course equivalent fashion. Let $a_{1}=m$ and
$\lambda_{1}=max\\{\mu_{1}+a_{1},\upsilon_{1}\\}$. Suppose that
$\lambda_{1},\lambda_{2},\ldots,\lambda_{i}$ and $a_{1},a_{2},\ldots,a_{i}$
are already determined. If $\lambda_{i}=0$, then let
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{i-1})$. Otherwise, let
$a_{i+1}=min\\{\mu_{i}+a_{i},\upsilon_{i}\\}-\rho_{i}$ and
$\lambda_{i+1}=max\\{\mu_{i+1}+a_{i+1},\upsilon_{i+1}\\}$. Repeat the above
procedure until we get $\lambda_{k}=0$ and let
$\lambda=\\{\lambda_{1},\lambda_{2},\ldots,\lambda_{k-1}\\}$.

If $m=0$ and $\rho=\upsilon$, then we have $a_{i}=0$ for all $i\geq 1$ since
$\mu_{i}\geq\rho_{i}$ for all $i\geq 1$. This implies that $\lambda=\mu$.

If $m=1$ and $\rho=\upsilon$, then we have $a_{1}=1$ and $a_{i}=0$ for all
$i\geq 2$. According to the forward algorithm, we have
$\lambda_{1}=max\\{\mu_{1}+1,\upsilon_{1}\\}=\mu_{1}+1$ and
$\lambda_{i}=max\\{\mu_{i}+a_{i},\upsilon_{i}\\}=\mu_{i}$ for all $i\geq 2$.
This yields that $\lambda$ and $\mu$ differ by a square.

If $m=0$ and $\rho$ and $\upsilon$ differ by a square, then choose the integer
$j$ such that $\upsilon_{j}=\rho_{j}+1$. In this case we have $a_{i}=0$ for
all $i\leq j$ and $\lambda_{i}=max\\{\mu_{i}+a_{i},\upsilon_{i}\\}=\mu_{i}$
for all $i<j$. Moreover, for all $i\geq j+1$, we have
$a_{i+1}=min\\{\mu_{i}+a_{i},\upsilon_{i}\\}-\rho_{i}=0$ and
$\lambda_{i+1}=max\\{\mu_{i+1}+a_{i+1},\upsilon_{i+1}\\}=\mu_{i+1}$.

In order to verify property $(c)$, it remains to show that we have either
$\mu_{j}=\lambda_{j}$ and $\lambda_{j+1}=\mu_{j+1}+1$, or
$\mu_{j+1}=\lambda_{j+1}$ and $\lambda_{j}=\mu_{j}+1$. We have two cases. If
$\mu_{j}>\rho_{j}$, then we have
$\lambda_{j}=max\\{\mu_{j}+a_{j},\upsilon_{j}\\}=max\\{\mu_{j},\upsilon_{j}\\}=\mu_{j}$,
$a_{j+1}=min\\{\mu_{j},\upsilon_{j}\\}-\rho_{j}=1$ and
$\lambda_{j+1}=max\\{\mu_{j+1}+a_{j+1},\upsilon_{j+1}\\}=\mu_{j+1}+1$ since
$\upsilon_{j+1}=\rho_{j+1}\leq\mu_{j+1}$. If $\mu_{j}=\rho_{j}$, then we have
$\lambda_{j}=max\\{\mu_{j}+a_{j},\upsilon_{j}\\}=max\\{\mu_{j},\upsilon_{j}\\}=\upsilon_{j}=\mu_{j}+1$,
$a_{j+1}=min\\{\mu_{j},\upsilon_{j}\\}-\rho_{j}=0$ and
$\lambda_{j+1}=max\\{\mu_{j+1}+a_{j+1},\upsilon_{j+1}\\}=\mu_{j+1}$ since
$\upsilon_{j+1}=\rho_{j+1}\leq\mu_{j+1}$. So far, we have reached the
conclusion that $\lambda$ has the properties $(a)-(c)$. By the same reasoning
as in the proofs of $(a)-(c)$, we can verify properties $(d)-(f)$. The details
are omitted. This completes the proof.

In this paper, we are mainly concerned with $01$-fillings of triangular shape.
Let $\Delta_{n}$ be the triangular shape with $n$ cells in the bottom row,
$n-1$ cells in the row above, etc., and $1$ cell in the topmost row. Combining
Theorems 2.1, 2.2 and Lemma 2.3, we have the following theorems.

###### Theorem 2.4

$01$-fillings of $\Delta_{n}$ with the property that every row contains
exactly one $1$ are in bijection with sequences
$(\emptyset=\lambda^{0},\lambda^{1},\ldots,\lambda^{2n}=\emptyset)$ where
$\lambda^{2i+1}$ is obtained from $\lambda^{2i}$ by doing nothing or adding a
horizontal strip , whereas $\lambda^{2i+2}$ is obtained from $\lambda^{2i+1}$
by deleting a square.

###### Theorem 2.5

$01$-fillings of $\Delta_{n}$ with the property that every row and every
column contains at most one $1$ are in bijection with sequences
$(\emptyset=\lambda^{0},\lambda^{1},\ldots,\lambda^{2n}=\emptyset)$ where
$\lambda^{2i+1}$ is obtained from $\lambda^{2i}$ by doing nothing or adding a
square, whereas $\lambda^{2i+2}$ is obtained from $\lambda^{2i+1}$ by doing
nothing or deleting a square.

###### Theorem 2.6

$01$-fillings of $\Delta_{n}$ with the property every row contains exactly one
$1$ and there is no NE-chain of length $k+1$ are in bijection with sequences
$(\emptyset=\lambda^{0},\lambda^{1},\ldots,\lambda^{2n}=\emptyset)$ where the
most number of columns of any $\lambda^{i}$ is at most $k$, and
$\lambda^{2i+1}$ is obtained from $\lambda^{2i}$ by doing nothing or adding a
horizontal strip, whereas $\lambda^{2i+2}$ is obtained from $\lambda^{2i+1}$
by deleting a square.

###### Theorem 2.7

$01$-fillings of $\Delta_{n}$ with the property that every row and every
column contains at most one $1$ and there is no NE-chain of length $k+1$ are
in bijection with sequences
$(\emptyset=\lambda^{0},\lambda^{1},\ldots,\lambda^{2n}=\emptyset)$ where the
most number of columns of any $\lambda^{i}$ is at most $k$, and
$\lambda^{2i+1}$ is obtained from $\lambda^{2i}$ by doing nothing or adding a
square, whereas $\lambda^{2i+2}$ is obtained from $\lambda^{2i+1}$ by doing
nothing or deleting a square.

Recall that there is a bijection between set partitions of $[n]$ and
$01$-fillings of $\Delta_{n-1}$ in which every row and every column contains
at most one $1$. Given a set partition $\pi$ of $[n]$, we can get a
$01$-filling of $\Delta_{n-1}$ by putting a $1$ in the $i$th column and $j$th
row from above (where we number rows such that the row consisting of $j-1$
cells is numbered $j$), whenever $(i,j)$ is an arc in its linear
representation. The $01$-filling corresponding to the set partition
$\pi=\\{\\{1,2,3,4,6,10\\},\\{5,8\\},\\{7,9\\}\\}$ is shown in Figure 5.
Moreover, a $k$-crossing of a set partition corresponds to a $SE$-chain of
length $k$ in the filling, while a $k$-nesting corresponds to a $NE$-chain of
length $k$. Thus the following theorem follows immediately.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$ Figure 5:  A
set partition $\pi=\\{\\{1,2,3,4,6,10\\},\\{5,8\\},\\{7,9\\}\\}$ and its
corresponding $01$-filling.

###### Theorem 2.8

$k$-nonnesting set partitions of $[n+1]$ are in bijection with $01$-fillings
of $\Delta_{n}$ with the property that every row and every column contains at
most one $1$ and there is no NE-chain of length $k$.

Denote by $\mathcal{V}_{n}$ the set of sequences
$(\emptyset=\lambda^{0},\lambda^{1},\ldots,\lambda^{2n}=\emptyset)$ where the
most number of columns of any $\lambda^{i}$ is at most $2$, and
$\lambda^{2i+1}$ is obtained from $\lambda^{2i}$ by doing nothing or adding a
square, whereas $\lambda^{2i+2}$ is obtained from $\lambda^{2i+1}$ by doing
nothing or deleting a square.

In view of Theorems 2.7 and 2.8, in order to prove Conjecture 1.1, it suffices
to establish a bijection between the set $\mathcal{A}_{n+1}(210)$ and the set
$\mathcal{V}_{n}$. In the next section, we will provide such a bijection.

##  3 Proof of the conjecture

In this section, we will establish a bijection between the set
$\mathcal{A}_{n+1}(210)$ and the set $\mathcal{V}_{n}$. To this end, we first
construct a bijection between $210$-avoiding primitive ascent sequences and a
certain class of $01$-fillings of triangular shape.

Denote by $\mathcal{N}(\Delta_{n})$ the set of all $01$-fillings of
$\Delta_{n}$ with the property that every row contains exactly one $1$ and
there is no NE-chain of length $3$. In this section, a $01$-filling in
$\mathcal{N}(\Delta_{n})$ will be identified with a sequence
$\\{(1,a_{1}),(2,a_{2}),\ldots,(n,a_{n})\\}$, where $1\leq a_{i}\leq i$ and
$a_{i}=k$ if and only if there is a $1$ in the $i$th row and $k$th column
(where we number columns from left to right and rows such that the row
consisting of $j$ cells is numbered $j$). For example, the filling in figure 6
is identified with

$\\{(1,1),(2,2,),(3,3),(4,1),(5,4),(6,4),(7,5),(8,7),(9,6)\\}.$

Let $n\geq 1$. We aim to describe a map $\phi$ from the set
$\mathcal{PA}_{n+1}(210)$ to the set $\mathcal{N}(\Delta_{n})$. Let
$x=x_{1}x_{2}\ldots x_{n+1}\in\mathcal{PA}_{n+1}(210)$. Define
$\phi(x)=\\{(1,a_{1}),(2,a_{2}),\ldots,(n,a_{n})\\}$ where
$a_{i}=i+x_{i+1}-asc(x_{1}x_{2}\ldots x_{i+1})$ for all $i=1,2,\ldots,n$. For
example, let $x=012340415\in\mathcal{PA}_{9}(210)$. Then we have

$\phi(x)=\\{(1,1),(2,2),(3,3),(4,4),(5,1),(6,5),(7,3),(8,7)\\}.$

###### Lemma 3.1

Let $x=x_{1}x_{2}\ldots x_{n+1}\in\mathcal{PA}_{n+1}(210)$ and
$\phi(x)=\\{(1,a_{1}),(2,a_{2}),\ldots,(n,a_{n})\\}$. Suppose that $a_{i}\geq
a_{j}$ with $i<j$. Then we have $x_{i+1}>x_{j+1}$.

Proof. Recall that $a_{i}=i+x_{i+1}-asc(x_{1}x_{2}\ldots x_{i+1})$ and
$a_{j}=j+x_{j+1}-asc(x_{1}x_{2}\ldots x_{j+1})$. Since $a_{i}\geq a_{j}$, we
have

$x_{i+1}-x_{j+1}\geq j-i-(asc(x_{1}x_{2}\ldots x_{j+1})-asc(x_{1}x_{2}\ldots
x_{i+1}))\geq 0.$

If $x_{i+2}<x_{i+1}$, then we have $asc(x_{1}x_{2}\ldots x_{j+1})\leq
asc(x_{1}x_{2}\ldots x_{i+1})+j-i-1$. This yields that

$x_{i+1}-x_{j+1}\geq j-i-(asc(x_{1}x_{2}\ldots x_{j+1})-asc(x_{1}x_{2}\ldots
x_{i+1}))\geq 1.$

Thus we deduce that $x_{i+1}>x_{j+1}$.

If $x_{i+2}>x_{i+1}$, then we have $asc(x_{1}x_{2}\ldots
x_{j+1})=asc(x_{1}x_{2}\ldots x_{i+1})+1+asc(x_{i+2}\ldots x_{j+1})$. If
$asc(x_{i+2}\ldots x_{j+1})=j-i-1$, then we have $x_{i+2}<\ldots<x_{j+1}$.
Thus it follows that $x_{j+1}>x_{i+1}$. This contradicts with the fact that
$x_{i+1}-x_{j+1}\geq 0$. Hence we have $asc(x_{i+2}\ldots x_{j+1})<j-i-1$. It
follows that

$\begin{array}[]{lll}asc(x_{1}x_{2}\ldots x_{j+1})&=&asc(x_{1}x_{2}\ldots
x_{i+1})+1+asc(x_{i+2}\ldots x_{j+1})\\\ &<&asc(x_{1}x_{2}\ldots
x_{i+1})+j-i.\end{array}$

This implies that $x_{i+1}-x_{j+1}\geq 1$. This completes the proof.

###### Theorem 3.2

For $n\geq 1$, the map $\phi$ is well defined, that is, for any ascent
sequence $x\in\mathcal{PA}_{n+1}(210)$, we have
$\phi(x)\in\mathcal{N}(\Delta_{n})$.

Proof. Let $x=x_{1}x_{2}\ldots x_{n+1}\in\mathcal{PA}_{n+1}(210)$ and
$\phi(x)=\\{(1,a_{1}),(2,a_{2}),\ldots,(n,a_{n})\\}$. First it is necessary to
prove that $a_{i}\leq i$. According to the definition of ascent sequences, we
have $x_{i+1}\leq asc(x_{1}x_{2}\ldots x_{i})+1$.

If $x_{i+1}=asc(x_{1}x_{2}\ldots x_{i})+1$, then we have $asc(x_{1}x_{2}\ldots
x_{i+1})=asc(x_{1}x_{2}\ldots x_{i})+1$. This yields that
$x_{i+1}=asc(x_{1}x_{2}\ldots x_{i+1})$, which implies that $a_{i}=i$.

If $x_{i+1}\leq asc(x_{1}x_{2}\ldots x_{i})$, then it follows that

$x_{i+1}\leq asc(x_{1}x_{2}\ldots x_{i})\leq asc(x_{1}x_{2}\ldots x_{i+1}).$

Recall that $a_{i}=i+x_{i+1}-asc(x_{1}x_{2}\ldots x_{i+1})$. Thus we deduce
that $a_{i}\leq i$.

Next we aim to show that $a_{i}\geq 1$. There are two cases. If
$asc(x_{1}x_{2}\ldots x_{i+1})=i$, then we have $0=x_{1}<x_{2}\ldots<x_{i+1}$.
In this case, we have

$a_{i}=i+x_{i+1}-asc(x_{1}x_{2}\ldots x_{i+1})=x_{i+1}\geq 1.$

If $asc(x_{1}x_{2}\ldots x_{i+1})<i$, then we have

$a_{i}=i+x_{i+1}-asc(x_{1}x_{2}\ldots x_{i+1})\geq x_{i+1}+1\geq 1.$

Thus we have reached the conclusion that $1\leq a_{i}\leq i$. This implies
that $\phi(x)$ is a $01$-filling of $\Delta_{n}$ with the property that every
row contains exactly one $1$.

It remains to show that there is no NE-chain of length $3$ in $\phi(x)$.
Suppose that the squares $(i,a_{i})$ $(j,a_{j})$ and $(k,a_{k})$ form a NE-
chain of length $3$, where $i<j<k$. This means that $a_{i}\geq a_{j}\geq
a_{k}$. By Lemma 3.1, we have $x_{i+1}>x_{j+1}>x_{k+1}$, which is a $210$
pattern. This leads to a contradiction with the fact that $x$ is
$210$-avoiding. Hence, we deduce that there is no NE-chain of length $3$ in
$\phi(x)$. This completes the proof.

In order to show that the map $\phi$ is a bijection, we proceed to describe a
map $\phi^{\prime}$ from the set $\mathcal{N}(\Delta_{n})$ to the set
$PA_{n+1}(210)$ for $n\geq 1$. Given a $01$-filling
$F\in\mathcal{N}(\Delta_{n})$, we wish to recover a $210$-avoiding primitive
ascent sequence of length $n+1$. Let
$F=\\{(1,a_{1}),(2,a_{2}),\ldots,(n,a_{n})\\}$. Define
$\phi^{\prime}(F)=(x_{1},x_{2},\ldots,x_{n+1})$ inductively as follows:

  * •

$x_{1}=0$ and $x_{2}=1$;

  * •

if $a_{i-1}<a_{i}$, then $x_{i+1}=asc(x_{1}x_{2}\ldots x_{i})+1+a_{i}-i$ for
all $2\leq i\leq n$ ;

  * •

if $a_{i-1}\geq a_{i}$, then $x_{i+1}=asc(x_{1}x_{2}\ldots x_{i})+a_{i}-i$ for
all $2\leq i\leq n$.

For example, let
$F=\\{(1,1),(2,2),(3,3),(4,4),(5,1),(6,5),(7,3),(8,7)\\}\in\mathcal{N}(\Delta_{8})$.
Then we have $\phi^{\prime}(F)=012340415$.

###### Lemma 3.3

For any $01$-filling
$F=\\{(1,a_{1}),(2,a_{2}),\ldots,(n,a_{n})\\}\in\mathcal{N}(\Delta_{n})$, the
sequence $\phi^{\prime}(F)=x_{1}x_{2}\ldots x_{n+1}$ has the property that

$x_{i+1}=asc(x_{1}x_{2}\ldots x_{i+1})+a_{i}-i$

for all $i\geq 1$. Furthermore, we have $x_{i}>x_{i+1}$ if $a_{i-1}\geq
a_{i}$, whereas $x_{i}<x_{i+1}$ if $a_{i-1}<a_{i}$.

Proof. We proceed by induction on $i$. It is easy to check that the statement
holds for $i=1$. Assume that $x_{i}=asc(x_{1}x_{2}\ldots
x_{i})+a_{i-1}-(i-1)$. Now we shall show that $x_{i+1}=asc(x_{1}x_{2}\ldots
x_{i+1})+a_{i}-i$. We consider two cases.

If $a_{i-1}<a_{i}$, then we have $x_{i+1}=asc(x_{1}x_{2}\ldots
x_{i})+1+a_{i}-i$. In this case, we have $x_{i+1}>asc(x_{1}x_{2}\ldots
x_{i})+a_{i-1}-(i-1)=x_{i}$. This implies that $x_{i+1}>x_{i}$ and
$asc(x_{1}x_{2}\ldots x_{i+1})=asc(x_{1}x_{2}\ldots x_{i})+1$. Thus we deduce
that $x_{i+1}=asc(x_{1}x_{2}\ldots x_{i+1})+a_{i}-i$ and $x_{i}<x_{i+1}$.

If $a_{i-1}\geq a_{i}$, then we have $x_{i+1}=asc(x_{1}x_{2}\ldots
x_{i})+a_{i}-i$. It follows that $x_{i}=asc(x_{1}x_{2}\ldots
x_{i})+a_{i-1}-(i-1)\geq asc(x_{1}x_{2}\ldots x_{i})+1+a_{i}-i=x_{i+1}+1$.
This implies that $x_{i}>x_{i+1}$ and $asc(x_{1}x_{2}\ldots
x_{i+1})=asc(x_{1}x_{2}\ldots x_{i})$. Thus we have
$x_{i+1}=asc(x_{1}x_{2}\ldots x_{i+1})+a_{i}-i$ and $x_{i}>x_{i+1}$. This
completes the proof.

###### Theorem 3.4

Let $n\geq 1$. The map $\phi^{\prime}$ is well defined, that is, for any
$01$-filling $F\in\mathcal{N}(\Delta_{n})$, we have
$\phi^{\prime}(F)\in\mathcal{PA}_{n+1}(210)$.

Proof. Let $F=\\{(1,a_{1}),(2,a_{2}),\ldots,(n,a_{n})\\}$ and
$\phi^{\prime}(F)=x_{1}x_{2}\ldots x_{n+1}$. Since $a_{i}\leq i$, we have
$x_{i+1}\leq asc(x_{1}x_{2}\ldots x_{i})+1$ according to the definition of the
map $\phi^{\prime}$. We next prove that $x_{i}\geq 0$ by induction on $i$. It
is apparent that $x_{1}\geq 0$ and $x_{2}\geq 0$. Assume that $x_{j}\geq 0$
for all $1\leq j\leq i$. Now we proceed to show that $x_{i+1}\geq 0$. We have
two cases. If $a_{i-1}<a_{i}$, then we have

$\begin{array}[]{ll}x_{i+1}&=asc(x_{1}x_{2}\ldots x_{i})+1+a_{i}-i\\\
&>asc(x_{1}x_{2}\ldots x_{i})+a_{i-1}-(i-1).\end{array}$

By Lemma 3.3, we have $x_{i}=asc(x_{1}x_{2}\ldots x_{i})+a_{i-1}-(i-1)$. Thus
it follows that $x_{i+1}>x_{i}\geq 0$.

If $a_{i-1}\geq a_{i}$, then we have $x_{i+1}=asc(x_{1}x_{2}\ldots
x_{i})+a_{i}-i$ according to the definition of $\phi^{\prime}$. If
$asc(x_{1}x_{2}\ldots x_{i})=i-1$, then we have $x_{i+1}\geq 0$ since
$a_{i}\geq 1$. Suppose that $asc(x_{1}x_{2}\ldots x_{i})<i-1$. By Lemma 3.3,
there exists integer $j$ such that $j\leq i-1$ and $a_{j-1}\geq a_{j}$. Let
$k$ be the largest such integer. Hence we have

$asc(x_{1}x_{2}\ldots x_{i})=asc(x_{1}x_{2}\ldots x_{k+1})+i-k-1.$

Moreover, since there is no NE-chain of length $3$ in $F$, we have
$a_{i}>a_{k}$. Thus we deduce that

$\begin{array}[]{ll}x_{i+1}&=asc(x_{1}x_{2}\ldots x_{i})+a_{i}-i\\\
&=asc(x_{1}x_{2}\ldots x_{k+1})+a_{i}+(i-k-1)-i\\\ &=asc(x_{1}x_{2}\ldots
x_{k+1})+a_{i}-k-1\\\ &\geq asc(x_{1}x_{2}\ldots x_{k+1})+1+a_{k}-k-1\\\
&=asc(x_{1}x_{2}\ldots x_{k+1})+a_{k}-k.\end{array}$

By Lemma 3.3, we have $x_{k+1}=asc(x_{1}x_{2}\ldots x_{k+1})+a_{k}-k$. This
yields that $x_{i+1}\geq x_{k+1}\geq 0$. Hence, we have reached the conclusion
that $x_{1}=0$ and $0\leq x_{i+1}\leq asc(x_{1}x_{2}\ldots x_{i})+1$ for all
$i\geq 1$. This ensures that the obtained sequence $\phi^{\prime}(F)$ is an
ascent sequence of length $n+1$. By Lemma 3.3, we have $x_{i}\neq x_{i+1}$ for
all $i\geq 1$. Hence the obtained sequence $\phi^{\prime}(F)$ is primitive.

It remains to show that $\phi^{\prime}(F)$ is $210$-avoiding. We claim that
for any integers $i,j$ with $i<j$, if $x_{i+1}>x_{j+1}$, then $a_{i}\geq
a_{j}$. By Lemma 3.3, we have $x_{i+1}=asc(x_{1}x_{2}\ldots x_{i+1})+a_{i}-i$
and $x_{j+1}=asc(x_{1}x_{2}\ldots x_{j+1})+a_{j}-j$. Suppose that
$x_{i+1}>x_{j+1}$. It follows that $asc(x_{i+1}\ldots x_{j+1})\leq j-i-1$.
Then we have

$\begin{array}[]{lll}a_{i}-a_{j}&\geq&j-i-(asc(x_{1}x_{2}\ldots
x_{j+1})-asc(x_{1}x_{2}\ldots x_{i+1}))-1\\\ &=&j-i-asc(x_{i+1}\ldots
x_{j+1})-1\\\ &\geq&0.\end{array}$

This yields that $a_{i}\geq a_{j}$. Hence the claim is proved.

Suppose that $x_{i+1}>x_{j+1}>x_{k+1}$ with $i<j<k$. Then we have $a_{i}\geq
a_{j}\geq a_{k}$. This implies that the squares $(i,a_{i})$, $(j,a_{j})$ and
$(k,a_{k})$ form a NE-chain of length $3$, which leads to a contradiction.
Therefore, the obtained sequence $\phi^{\prime}(F)$ is $210$-avoiding. This
completes the proof.

###### Theorem 3.5

The maps $\phi$ and $\phi^{\prime}$ are inverses of each other.

Proof. We first prove that $\phi^{\prime}(\phi(x))=x$ for any ascent sequence
$x=x_{1}x_{2}\ldots x_{n+1}\in\mathcal{PA}_{n+1}(210)$. Suppose that
$\phi(x)=\\{(1,a_{1}),(2,a_{2}),\ldots,(n,a_{n})\\}$. According to the
definition of the map $\phi$, we have $a_{i}=i+x_{i+1}-asc(x_{1}x_{2}\ldots
x_{i+1})$. When we apply the map $\phi^{\prime}$ to $\phi(x)$, we get a
210-avoiding ascent sequence $x^{\prime}=x^{\prime}_{1}x^{\prime}_{2}\ldots
x^{\prime}_{n+1}$ such that

  * •

$x^{\prime}_{1}=0$ and $x^{\prime}_{2}=1$;

  * •

if $a_{i-1}<a_{i}$, then
$x^{\prime}_{i+1}=asc(x^{\prime}_{1}x^{\prime}_{2}\ldots
x^{\prime}_{i})+1+a_{i}-i$ for all $2\leq i\leq n$;

  * •

if $a_{i-1}\geq a_{i}$, then
$x^{\prime}_{i+1}=asc(x^{\prime}_{1}x^{\prime}_{2}\ldots
x^{\prime}_{i})+a_{i}-i$ for all $2\leq i\leq n$.

We proceed to show that $x^{\prime}_{i}=x_{i}$ for all $i\geq 1$ by induction
on $i$. It is clear that $x^{\prime}_{1}=0=x_{1}$ and
$x^{\prime}_{2}=1=x_{2}$. Assume that $x^{\prime}_{k}=x_{k}$ for $1\leq k\leq
i$. Now we proceed to show that $x^{\prime}_{i+1}=x_{i+1}$. We have two cases.

If $a_{i-1}\geq a_{i}$, then we have
$x^{\prime}_{i+1}=asc(x^{\prime}_{1}x^{\prime}_{2}\ldots
x^{\prime}_{i})+a_{i}-i$. By the induction hypothesis, we have
$asc(x^{\prime}_{1}x^{\prime}_{2}\ldots x^{\prime}_{i})=asc(x_{1}x_{2}\ldots
x_{i})$. This implies that $x^{\prime}_{i+1}=asc(x_{1}x_{2}\ldots
x_{i})+a_{i}-i$. By Lemma 3.1, we have $x_{i}>x_{i+1}$. This yields that
$asc(x_{1}x_{2}\ldots x_{i+1})=asc(x_{1}x_{2}\ldots x_{i})$ and
$x_{i+1}=asc(x_{1}x_{2}\ldots x_{i+1})+a_{i}-i$. According to the definition
of the map $\phi$, we have $a_{i}=i+x_{i+1}-asc(x_{1}x_{2}\ldots x_{i+1})$.
Thus we have $x^{\prime}_{i+1}=x_{i+1}$.

If $a_{i-1}<a_{i}$, then we have
$x^{\prime}_{i+1}=asc(x^{\prime}_{1}x^{\prime}_{2}\ldots
x^{\prime}_{i})+1+a_{i}-i$. By Lemma 3.3, we have
$x^{\prime}_{i+1}=asc(x^{\prime}_{1}x^{\prime}_{2}\ldots
x^{\prime}_{i+1})+a_{i}-i$ and $x^{\prime}_{i}<x^{\prime}_{i+1}$. This implies
that $asc(x^{\prime}_{1}x^{\prime}_{2}\ldots
x^{\prime}_{i+1})=asc(x^{\prime}_{1}x^{\prime}_{2}\ldots x^{\prime}_{i})+1$.
By the induction hypothesis, we have $asc(x^{\prime}_{1}x^{\prime}_{2}\ldots
x^{\prime}_{i})=asc(x_{1}x_{2}\ldots x_{i})$. It follows that

$asc(x^{\prime}_{1}x^{\prime}_{2}\ldots
x^{\prime}_{i+1})=asc(x^{\prime}_{1}x^{\prime}_{2}\ldots
x^{\prime}_{i})+1=asc(x_{1}x_{2}\ldots x_{i})+1.$

By lemma 3.1, we have $x_{i+1}>x_{i}$. This yields that $asc(x_{1}x_{2}\ldots
x_{i+1})=asc(x_{1}x_{2}\ldots x_{i})+1$. Thus we deduce that
$x^{\prime}_{i+1}=asc(x_{1}x_{2}\ldots x_{i+1})+a_{i}-i$. Recall that
$a_{i}=i+x_{i+1}-asc(x_{1}x_{2}\ldots x_{i+1})$. Thus we deduce that
$x^{\prime}_{i+1}=x_{i+1}$. Hence we have reached the conclusion that
$\phi^{\prime}(\phi(x))=x$.

Next we turn to the proof of $\phi(\phi^{\prime}(F))=F$ for any $01$-filling
$F\in\mathcal{N}(\Delta_{n})$. Let
$F=\\{(1,a_{1}),(2,a_{2}),\ldots,(n,a_{n})\\}$. Suppose that
$\phi^{\prime}(F)=x_{1}x_{2}\ldots x_{n+1}$. When we apply the map $\phi$ to
$\phi^{\prime}(F)$, we get a $01$-filling
$F^{\prime}=\\{(1,a^{\prime}_{1}),(2,a^{\prime}_{2}),\ldots,(n,a^{\prime}_{n})\\}\in\mathcal{N}(\Delta_{n})$.
By the definition of the map $\phi$ and Lemma 3.3, we have
$x_{i+1}=asc(x_{1}x_{2}\ldots x_{i+1})+a_{i}-i$ and
$a^{\prime}_{i}=i+x_{i+1}-asc(x_{1}x_{2}\ldots x_{i+1})$ for $i\geq 1$. This
implies that $a^{\prime}_{i}=a_{i}$ for $i\geq 1$. Thus we deduce that
$\phi(\phi^{\prime}(F))=F$. This completes the proof.

Now we are ready to describe a bijection between the set
$\mathcal{A}_{n+1}(210)$ and the set $\mathcal{V}_{n}$. Our bijection relies
on the growth diagrams for $01$-fillings of triangular shape and the bijection
$\phi$.

###### Theorem 3.6

For $n\geq 0$, there is a bijection between the set $\mathcal{A}_{n+1}(210)$
and the set $\mathcal{V}_{n}$.

Proof. Let $x$ be a $210$-avoiding ascent sequence of length $n+1$, we wish to
construct a sequence $\psi(x)\in\mathcal{V}_{n}$. It is apparent that the
ascent sequence $x$ can be written as $x_{1}^{c_{1}}x_{2}^{c_{2}}\ldots
x_{k+1}^{c_{k+1}}$, where $x_{i}\neq x_{i+1}$ and $c_{i}\geq 1$ for all $i\geq
1$. Let $x^{\prime}=x_{1}x_{2}\ldots x_{k+1}$. Obviously, $x^{\prime}$ is a
$210$-avoiding primitive ascent sequence of length $k+1$. For $k=0$, let
$\psi(x)$ be a sequence of length $2n+1$ consisting of $\emptyset$’s. For
$k\geq 1$, by Theorem 3.2, we obtain a $01$-filling $\phi(x^{\prime})$ in
$\mathcal{N}(\Delta_{k})$ by applying the map $\phi$ to $x^{\prime}$. When we
apply the forward algorithm to $\phi(x^{\prime})$, we get the growth diagram
for the $01$-filling $\phi(x^{\prime})$. Let
$(\emptyset=\lambda^{0},\lambda^{1},\ldots,\lambda^{2k}=\emptyset)$ be the
sequence of partitions labelling the right/up border of the growth diagram
from top-left to bottom-right. By Theorem 2.6, the sequence
$(\emptyset=\lambda^{0},\lambda^{1},\ldots,\lambda^{2k}=\emptyset)$ has the
properties that the most number of columns of any $\lambda^{i}$ is at most
$2$, and $\lambda^{2i+1}$ is obtained from $\lambda^{2i}$ by doing nothing or
adding a horizontal strip, whereas $\lambda^{2i+2}$ is obtained from
$\lambda^{2i}$ by deleting a square. Now we proceed to generate a sequence of
partitions from the sequence
$(\emptyset=\lambda^{0},\lambda^{1},\ldots,\lambda^{2k}=\emptyset)$ by the
following procedure.

  * •

For all $i\geq 0$, if $\lambda^{2i+1}$ is obtained from $\lambda^{2i}$ by
adding two squares, then let $\lambda^{2i+1}=\lambda^{2i+2}$. Let
$(\mu^{0},\mu^{1},\ldots,\mu^{2k})$ denote the resulting sequence.

  * •

If $c_{1}>1$, then adjoin $2(c_{1}-1)$ copies of $\mu^{0}$ immediately left to
$\mu^{0}$.

  * •

For all $1\leq i\leq k$, if $c_{i+1}>1$ , then insert $2(c_{i+1}-1)$ copies of
$\mu^{2i}$ immediately left to $\mu^{2i}$ and right to $\mu^{2i-1}$.

Since $c_{1}+c_{2}+\ldots+c_{k+1}=n+1$, the resulting sequence is of length
$2n+1$. Denote by $(\rho^{0},\rho^{1},\ldots,\rho^{2n})$ the resulting
sequence and set $\psi(x)=(\rho^{0},\rho^{1},\ldots,\rho^{2n})$.

In order to show that $\psi(x)\in\mathcal{V}_{n}$, it suffices to show that
the sequence $(\rho^{0},\rho^{1},\ldots,\rho^{2n})$ has the following
properties:

  * (i)

$\rho^{0}=\emptyset$ and $\rho^{2n}=\emptyset$;

  * (ii)

$\rho^{2i+1}$ is obtained from $\rho^{2i}$ by doing nothing or adding a
square;

  * (iii)

$\rho^{2i+2}$ is obtained from $\rho^{2i+1}$ by doing nothing or deleting a
square;

  * (iv)

each $\rho^{i}$ has at most two columns.

From the construction of the map $\psi$, it is easily seen that the sequence
$(\rho^{0},\rho^{1},\ldots,\rho^{2n})$ has properties (i) and (iv). Moreover,
it is easy to check that the sequence $(\rho^{0},\rho^{1},\ldots,\rho^{2n})$
is defined by

$\rho^{l}=\left\\{\begin{array}[]{ll}\mu^{2i},&\,\,\mbox{if}\,\,\sum_{j=0}^{i}2c_{j}\leq
l\leq\sum_{j=0}^{i+1}2c_{j}-2,\\\
\mu^{2i+1},&\,\,\mbox{if}\,\,l=\sum_{j=0}^{i+1}2c_{j}-1,\end{array}\right.$
(3.1)

with the assumption $c_{0}=0$.

We claim that we have either $(1)$ $\mu^{2i+1}$ is obtained from $\mu^{2i}$ by
doing nothing or adding a square and $\mu^{2i+2}$ is obtained from
$\mu^{2i+1}$ by deleting a square, or $(2)$ $\mu^{2i+1}$ is obtained from
$\mu^{2i}$ by adding a square and $\mu^{2i+2}$ is obtained from $\mu^{2i+1}$
by doing nothing. Since each $\lambda^{i}$ has at most two columns,
$\lambda^{2i+1}$ is obtained from $\lambda^{2i}$ by adding a horizontal strip
of at most two squares. If $\lambda^{2i+1}$ is obtained from $\lambda^{2i}$ by
doing nothing or adding a square, then we have
$\mu^{2i}=\lambda^{2i},\mu^{2i+1}=\lambda^{2i+1}$, and
$\mu^{2i+2}=\lambda^{2i+2}$. Recall that $\lambda^{2i+2}$ is obtained from
$\lambda^{2i+1}$ by deleting a square. Thus $\mu^{2i+1}$ is obtained from
$\mu^{2i}$ by doing nothing or adding a square and $\mu^{2i+2}$ is obtained
from $\mu^{2i+1}$ by deleting a square.

If $\lambda^{2i+1}$ is obtained from $\lambda^{2i}$ by adding a horizontal
strip of two squares, then according to the construction of the map $\psi$, we
have $\mu^{2i+1}=\lambda^{2i+2}=\mu^{2i+2}$. Recall that $\lambda^{2i+2}$ is
obtained from $\lambda^{2i+1}$ by deleting a square. Hence $\lambda^{2i+2}$
and $\lambda^{2i}$ differ by exactly one square. Since $\mu^{2i}=\lambda^{2i}$
and $\mu^{2i+2}=\lambda^{2i+2}=\mu^{2i+1}$, it follows that $\mu^{2i+1}$ is
obtained from $\mu^{2i}$ by adding a square and $\mu^{2i+2}$ is obtained from
$\mu^{2i+1}$ by doing nothing. Hence the claim is proved.

By Formula 3.1, we deduce that either $(1)$ $\rho^{\sum_{j=0}^{i+1}2c_{j}-1}$
is obtained form $\rho^{\sum_{j=0}^{i+1}2c_{j}-2}$ by doing nothing or adding
a square and $\rho^{\sum_{j=0}^{i+1}2c_{j}}$ is obtained form
$\rho^{\sum_{j=0}^{i+1}2c_{j}-1}$ by deleting a square, or $(2)$
$\rho^{\sum_{j=0}^{i+1}2c_{j}-1}$ is obtained form
$\rho^{\sum_{j=0}^{i+1}2c_{j}-2}$ by adding a square and
$\rho^{\sum_{j=0}^{i+1}2c_{j}}$ is obtained form
$\rho^{\sum_{j=0}^{i+1}2c_{j}-1}$ by doing nothing. Moreover, for all
$\sum_{j=0}^{i}2c_{j}<l\leq\sum_{j=0}^{i+1}2c_{j}-2$, we have
$\rho^{l}=\rho^{l-1}$. Hence, the sequence
$(\rho^{0},\rho^{1},\ldots,\rho^{2n})$ has properties (ii) and (iii), which
implies that $\psi(x)\in\mathcal{V}_{n}$.

Conversely, given a sequence
$V=(\rho^{0},\rho^{1},\ldots,\rho^{2n})\in\mathcal{V}_{n}$, we wish to recover
a $210$-avoiding ascent sequence $\psi^{\prime}(V)$. If $\rho^{i}=\emptyset$
for all $i\geq 0$, then let $\psi^{\prime}(V)$ be the ascent sequence of
length $n+1$ consisting of $0$’s. Otherwise, for all $i\geq 0$, remove
$\rho^{2i}$ and $\rho^{2i+1}$ from the sequence
$(\rho^{0},\rho^{1},\ldots,\rho^{2n})$ whenever
$\rho^{2i}=\rho^{2i+1}=\rho^{2i+2}$. Assume that

$(\rho^{2j_{0}},\rho^{2j_{0}+1},\rho^{2j_{1}},\rho^{2j_{1}+1},\ldots,\rho^{2j_{m-1}},\rho^{2j_{m-1}+1},\rho^{2j_{m}})$

is the resulting sequence. Let
$(\upsilon^{0},\upsilon^{1},\ldots,\upsilon^{2m})$ be a sequence such that
$(1)$ $\upsilon^{2i}=\rho^{2j_{i}}$; $(2)$ if
$\rho^{2j_{i}+1}=\rho^{2j_{i+1}}$, then $\upsilon^{2i+1}$ is a partition
obtained from $\upsilon^{2i}$ by adding a horizontal strip of two squares;
$(3)$ otherwise, $\upsilon^{2i+1}=\rho^{2j_{i}+1}$. By applying the backward
algorithm to $(\upsilon^{0},\upsilon^{1},\ldots,\upsilon^{2m})$, we obtain a
$01$-filling $F\in\mathcal{N}(\Delta_{m})$. Let
$\phi^{\prime}(F)=y_{1}y_{2}\ldots y_{m+1}$ and
$\psi^{\prime}(V)=y^{c^{\prime}_{1}}_{1}y^{c^{\prime}_{2}}_{2}\ldots
y_{m+1}^{c^{\prime}_{m+1}}$, where $c^{\prime}_{i+1}=j_{i}-j_{i-1}$ for $i\geq
1$ and $c^{\prime}_{1}=j_{0}+1$.

It is apparent that we have $j_{m}=n$. Since
$c^{\prime}_{1}+c^{\prime}_{2}+\ldots+c^{\prime}_{m+1}=n+1$, the obtained
sequence $\psi^{\prime}(V)$ is a sequence of length $n+1$. By Theorems 2.6 and
3.4, in order to show that $\psi^{\prime}(V)\in\mathcal{A}_{n+1}(210)$, it
suffices to show that the sequence
$(\upsilon^{0},\upsilon^{1},\ldots,\upsilon^{2m})$ verifies the following
points.

  * (i)${}^{{}^{\prime}}$

$\upsilon^{0}=\upsilon^{2m}=\emptyset$;

  * (ii)${}^{{}^{\prime}}$

$\upsilon^{2i+1}$ is obtained from $\upsilon^{2i}$ by doing nothing or adding
a horizontal strip;

  * (iii)${}^{{}^{\prime}}$

$\upsilon^{2i+2}$ is obtained from $\upsilon^{2i+1}$ by deleting a square;

  * (iv)${}^{{}^{\prime}}$

each $\upsilon^{i}$ has at most two columns.

It is easy to check that the statements of (i)${}^{{}^{\prime}}$,
(ii)${}^{{}^{\prime}}$ and (iv)${}^{{}^{\prime}}$ are true for the sequence
$(\upsilon^{0},\upsilon^{1},\ldots,\upsilon^{2m})$. From the construction of
the map $\psi^{\prime}$, it is easily seen that if
$\rho^{2j_{i}+1}\neq\rho^{2j_{i+1}}$, then $\upsilon^{2i+2}=\rho^{2j_{i+1}}$
and $\upsilon^{2i+1}=\rho^{2j_{i}+1}$. Moreover, we have
$\rho^{2j_{i}+2}=\rho^{2j_{i+1}}$. This implies that $\rho^{2j_{i}+2}$ is
obtained form $\rho^{2j_{i}+1}$ by deleting a square. Hence, it follows that
$\upsilon^{2i+2}$ is obtained from $\upsilon^{2i+1}$ by deleting a square.

In order to verify (iii)${}^{{}^{\prime}}$, it remains to show that if
$\rho^{2j_{i}+1}=\rho^{2j_{i+1}}$, then $\upsilon^{2i+2}$ is obtained from
$\upsilon^{2i+1}$ by deleting a square. Suppose that
$\rho^{2j_{i}+1}=\rho^{2j_{i+1}}$. From the construction of the sequence

$(\rho^{2j_{0}},\rho^{2j_{0}+1},\rho^{2j_{1}},\rho^{2j_{1}+1},\ldots,\rho^{2j_{m-1}},\rho^{2j_{m-1}+1},\rho^{2j_{m}}),$

it follows that $\rho^{2j_{i}+1}\neq\rho^{2j_{i}}$. This implies that
$\rho^{2j_{i}+1}$ is obtained from $\rho^{2j_{i}}$ by adding one square.
Recall that $\upsilon^{2i}=\rho^{2j_{i}}$. This implies that $\upsilon^{2i+1}$
is obtained from $\upsilon^{2i}$ by adding a horizontal strip of two squares.
Since $\upsilon^{2i+2}=\rho^{2j_{i+1}}=\rho^{2j_{i}+1}$ and $\rho^{2j_{i}+1}$
is obtained from $\rho^{2j_{i}}$ by adding one square, the partition
$\upsilon^{2i+2}$ is obtained from $\upsilon^{2i}$ by adding one square.
Recall that $\upsilon^{2i+1}$ is obtained from $\upsilon^{2i}$ by adding a
horizontal strip of two squares. It follows that $\upsilon^{2i+2}$ is obtained
from $\upsilon^{2i+1}$ by deleting a square. Hence, we have reached the
conclusion that $\psi^{\prime}(V)\in\mathcal{A}_{n+1}(210)$.

Now we proceed to show that the map $\psi$ is indeed a bijection. To this end,
we will show that the maps $\psi$ and $\psi^{\prime}$ are inverses of each
other. We first show that the map $\psi^{\prime}$ is the inverse of the map
$\psi$, that is, $\psi^{\prime}(\psi(x))=x$. By Theorems 3.5 and 2.6, it
suffices to prove that

$(\rho^{2j_{0}},\rho^{2j_{0}+1},\rho^{2j_{1}},\rho^{2j_{1}+1},\ldots,\rho^{2j_{m-1}},\rho^{2j_{m-1}+1},\rho^{2j_{m}})=(\mu^{0},\mu^{1},\ldots,\mu^{2k}),$
(3.2)

and $c_{j}=c^{\prime}_{j}$ for all $j\geq 1$. Recall that we have either $(1)$
$\rho^{\sum_{j=0}^{i+1}2c_{j}-1}$ is obtained form
$\rho^{\sum_{j=0}^{i+1}2c_{j}-2}$ by doing nothing or adding a square and
$\rho^{\sum_{j=0}^{i+1}2c_{j}}$ is obtained form
$\rho^{\sum_{j=0}^{i+1}2c_{j}-1}$ by deleting a square, or $(2)$
$\rho^{\sum_{j=0}^{i+1}2c_{j}-1}$ is obtained form
$\rho^{\sum_{j=0}^{i+1}2c_{j}-2}$ by adding a square and
$\rho^{\sum_{j=0}^{i+1}2c_{j}}$ is obtained form
$\rho^{\sum_{j=0}^{i+1}2c_{j}-1}$ by doing nothing. Moreover, for all
$\sum_{j=0}^{i}2c_{j}<l\leq\sum_{j=0}^{i+1}2c_{j}-2$, we have
$\rho^{l}=\rho^{l-1}$. From the construction of the map $\psi^{\prime}$, it
follows that $j_{i}=\sum_{j=0}^{i+1}c_{j}-1$ for all $i\geq 0$. This implies
that $c^{\prime}_{1}=j_{0}+1=c_{1}$ and
$c^{\prime}_{i+1}=j_{i}-j_{i-1}=c_{i+1}$ for all $i\geq 1$. Moreover, by
Formula 3.1, we have $\rho^{\sum_{j=0}^{i+1}2c_{j}-2}=\mu^{2i}$ and
$\rho^{\sum_{j=0}^{i+1}2c_{j}-1}=\mu^{2i+1}$. Thus we obtain Formula 3.2.

By Theorems 3.5 and 2.6, it is routine to check that the map $\psi$ reverses
each step of the map $\psi^{\prime}$. This implies that the map $\psi$ is the
inverse map of $\psi^{\prime}$. Hence, the maps $\psi$ and $\psi^{\prime}$ are
inverses of each other. This completes the proof.

For example, let $x=0012303222353$ be a $210$-avoiding ascent sequence of
length $13$. Then $x$ can be written as
$0^{2}1^{1}2^{1}3^{1}0^{1}3^{1}2^{3}3^{1}5^{1}3^{1}$. Let
$x^{\prime}=0123032353$, which is a $210$-avoiding primitive ascent sequence
of length $10$. By applying the map $\phi$ to $x^{\prime}$, we get a
$01$-filling

$\phi(x^{\prime})=\\{(1,1),(2,2,),(3,3),(4,1),(5,4),(6,4),(7,5),(8,7),(9,6)\\}\in\mathcal{N}(\Delta_{9}).$

Then we get the growth diagram for the $01$-filling $\psi(x^{\prime})$
illustrated in Figure 6. Let

$(\lambda^{0},\lambda^{1},\ldots,\lambda^{18})=(\emptyset,2,1,2,1,2,1,21,2,21,11,111,11,21,2,2,1,1,\emptyset)$

be the sequence of partitions labelling the corners along the right/up border
of the growth diagram from top-left to bottom-right. It is easy to check that
$\lambda^{1}$ is obtained from $\lambda^{0}$ by adding two squares and
$\lambda^{7}$ is obtained form $\lambda^{6}$ by adding two squares. Hence we
get a sequence

$(\mu^{0},\mu^{1},\ldots,\mu^{18})=(\emptyset,1,1,2,1,2,1,2,2,21,11,111,11,21,2,2,1,1,\emptyset)$

by replacing $\lambda^{1}$ and $\lambda^{7}$ with the partitions
$\lambda^{2}=1$ and $\lambda^{8}=2$, respectively. Finally, we obtain a
sequence

$\psi(x)=(\emptyset,\emptyset,\emptyset,1,1,2,1,2,1,2,2,21,11,111,11,11,11,11,11,21,2,2,1,1,\emptyset)\in\mathcal{V}_{12}$

from $(\mu^{0},\mu^{1},\ldots,\mu^{18})$ by inserting two copies of $\mu^{0}$
immediately left to $\mu^{0}$, and inserting four copies of $\mu^{12}$
immediately left to $\mu^{12}$ and right to $\mu^{11}$.

$\bullet$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$1$$1$$1$$1$$\bullet$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$1$$2$$2$$\bullet$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$1$$11$$21$$\bullet$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$1$$11$$111$$\bullet$$\emptyset$$\emptyset$$\emptyset$$\emptyset$$2$$21$$\bullet$$\emptyset$$1$$1$$1$$21$$\bullet$$\emptyset$$1$$1$$2$$\emptyset$$1$$1$$1$$21$$\bullet$$\emptyset$$1$$2$$\bullet$$\emptyset$$2$.
Figure 6:  The growth diagram for a $01$-filling of $\Delta_{9}$.

Conversely, given a sequence of partitions

$V=(\rho^{0},\rho^{1},\ldots,\rho^{24})=(\emptyset,\emptyset,\emptyset,1,1,2,1,2,1,2,2,21,11,111,11,11,11,11,11,21,2,2,1,1,\emptyset),$

we aim to recover an ascent sequence $\psi^{\prime}(V)$. It is easily seen
that $\rho^{0}=\rho^{1}=\rho^{2}$, $\rho^{14}=\rho^{15}=\rho^{16}$ and
$\rho^{16}=\rho^{17}=\rho^{18}$. We obtain a sequence

$(\rho^{2},\rho^{3},\rho^{4},\rho^{5},\rho^{6},\rho^{7},\rho^{8},\rho^{9},\rho^{10},\rho^{11},\rho^{12},\rho^{13},\rho^{18},\rho^{19},\rho^{20},\rho^{21},\rho^{22},\rho^{23},\rho^{24})$

by removing $\rho^{0},\rho^{1},\rho^{14},\rho^{15},\rho^{16},\rho^{17}$.
Moreover, we have $\rho^{3}=\rho^{4}$ and $\rho^{9}=\rho^{10}$. Replace
$\rho^{3}$ and $\rho^{9}$ with the partitions $2$ and $21$ respectively. This
leads to a sequence of partitions

$(\upsilon^{0},\upsilon^{1},\ldots,\upsilon^{18})=(\emptyset,2,1,2,1,2,1,21,2,21,11,111,11,21,2,2,1,1,\emptyset).$

Applying the backward algorithm, we get a $01$-filling

$F=\\{(1,1),(2,2,),(3,3),(4,1),(5,4),(6,4),(7,5),(8,7),(9,6)\\}.$

Finally we have $\phi^{\prime}(F)=0123032353$ and
$\psi^{\prime}(V)=0012303222353$.

Combining Theorems 2.7, 2.8 and 3.6, we get the following theorem, which leads
to a combinatorial proof of Conjecture 1.1.

###### Theorem 3.7

$210$-avoiding ascent sequences of length $n$ are in bijection with
$3$-nonnesting set partitions of $[n]$.

Acknowledgments. The author was supported by the National Natural Science
Foundation of China (No.10901141).

## References

  * [1] M. Bousquet-M$\acute{e}$lou, A. Claesson, M. Dukes, S. Kitaev, $(2+2)$-free posets, ascent sequences and pattern avoiding permutations, J. Combin. Theory Ser. A 117 (2010), 884–909.
  * [2] W.Y.C. Chen, E.Y.P. Deng, R.R.X. Du, R.P. Stanley, C.H. Yan, Crossings and nestings of matchings and partitions, Trans. Amer. Math. Soc. 359 (2007), 1555–1575.
  * [3] M. Dukes, R. Parviainen, Ascent sequences and upper triangular matrices containing non-negative integers, Electronic J. combin.  17  (2010), R53.
  * [4] P. Duncan, E. Steingrímsson, Pattern avoidance in ascent sequences, Electronic J. combin.  18  (2011), P226.
  * [5] C. Krattenthaler, Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes, Adv. Appl. Math. 37 (2006), 404–431.
  * [6] T. Mansour, M. Shattuck, Some enumerative results related to ascent sequences, arXiv: math.CO 1207.3755V1.
  * [7] A. Stoimenow, Enumumeration of chord diagrams and an upper bound for Vassiliev invariants, J. Knot Theory Ramifications 7 (1998), 93–114.
  * [8] M. van Leeuwen, Spin-preserving Knuth correspondences for ribbon tableaux, Electron. J. Combin. 12(1) (2005), R10.