# On the correspondence between perfect matchings and compatible pairs for
affine cluster algebra

Ivan Ip111 Department of Mathematics, Hong Kong University of Science and
Technology
Email<EMAIL_ADDRESS>
Email<EMAIL_ADDRESS>, Duy Phan11footnotemark: 1

###### Abstract

We study cluster algebra of affine type $A_{1}^{(1)}$ by using two methods
including counting the numbers of perfect matchings on snake graphs and
compatible pairs on maximal Dyck paths. We find that the sum of coefficients
of the terms in the Laurent polynomials of these cluster variables are odd-
indexed Fibonacci numbers. In addition, we prove that the numbers of non-
decreasing Dyck paths of even lengths are also odd-indexed Fibonacci numbers.
As a consequence, we define explicit bijective correspondences among three
combinatorial models, including perfect matchings on the snake graph,
compatible pairs on the maximal Dyck path, and non-decreasing Dyck paths of
even lengths.

##  1 Introduction

_Cluster algebra_ was first introduced by Fomin and Zelevinsky due to their
inspiration for solving total positivity problems [5]. A type of commutative
ring known as cluster algebra is made up of generators known as _cluster
variables_. Cluster variables are produced from the initial $n$ cluster
variables by a process known as _mutations_. All cluster variables can be
written as a rational function of $n$ initial cluster variables. Furthermore,
in [5] Fomin and Zelevinsky also proved that these rational functions are
actually Laurent polynomials.

In this paper, we consider the _affine type_ cluster algebra
$\mathcal{A}(2,2)$ of rank $2$ and type $A_{1}^{(1)}$ with an initial cluster
$(x_{1},x_{2})$ and mutations expressed as a recurrence relation

$\displaystyle x_{n-1}x_{n+1}=x_{n}^{2}+1,\quad n\in\mathbb{Z}$ (1.1)

(see [18]). This cluster algebra is also associated with the surface of an
annulus with one marked point on each boundary circle. The curves on this
surface, also known as _arcs_ , correspond to cluster variables.
_Triangulations_ of this surface correspond to clusters, and changes of
triangulations correspond to mutations.

In [12], cluster algebra associated with oriented unpunctured Riemann surface
with boundaries is studied, by counting the _perfect matchings_ on the _snake
graphs_ obtained from arcs on the surface. On the other hand, in [10], it is
shown that cluster variables in rank $2$ cluster algebra are _greedy elements_
of the form $x[a_{1},a_{2}]$. The greedy elements are computed by counting
_compatible pairs_ on the _maximal Dyck path_ $\mathcal{D}^{a_{1}\times
a_{2}}$ of a rectangle of size $a_{1}\times a_{2}$.

In this paper, we use these two methods to show that the numbers of perfect
matchings on the snake graph $G_{T,\gamma_{n+3}}$ and the number of compatible
pairs on the maximal Dyck path $\mathcal{D}^{\left(n+1\right)\times n}$ are
both _Fibonacci numbers_ $F_{2n+3}$. This new calculation implies that in the
coefficient free case, the sum of the integer coefficients in the Laurent
polynomials of these cluster variables are the odd-indexed Fibonacci numbers.
As a result, we come up with the idea of creating a new bijective
correspondence between these two combinatorial patterns. This bijective map is
defined by the following theorem (see Theorem 6.2).

######  Theorem.

The set map

$\phi:\\{\text{perfect matchings on
}G_{T,\gamma_{n+3}}\\}\mapsto\\{\text{compatible pairs on
}\mathcal{D}^{\left(n+1\right)\times n}\\}$ $P\to(S_{1},S_{2})$

defined by the conditions

  * •

$u_{i}\in S_{1}\iff A_{2i}A_{2i+1},B_{2i}B_{2i+1}\in P$ for any $i=0,1,...,n$.

  * •

$v_{i}\in S_{2}\iff A_{2i-1}A_{2i},B_{2i-1}B_{2i}\in P$ for any $i=1,2,...,n$.

is a bijective correspondence.

Next, we expand our interest in the combinatorial patterns involving the Dyck
path and the odd-indexed Fibonacci numbers. We find a combinatorial pattern
called _nondecreasing Dyck paths_ of even length. The number of nondecreasing
Dyck paths of length $2n+4$ is also $F_{2n+3}$. This model has significance in
_computer science_ and has been studied by Deutsch and Prodinger [3]. They
showed that it has many connections with other combinatorial models such as
_directed column-convex polynominoes_ and _ordered trees_ of height at most
three. Therefore, we include nondecreasing Dyck paths of even length in our
study.

Note that here the term “Dyck path” is defined slightly differently in
“maximal Dyck path” and “nondecreasing Dyck path”, see Remark 5.2 for an
explanation.

perfect matchingson the snake graph$G_{T,\gamma_{n+3}}$compatible pairs onthe
maximal Dyck path$\mathcal{D}^{(n+1)\times n}$nondecreasingDyck paths of
length$2n+4$$\phi$$\theta$$\psi$Fibonacci numbers$F_{2n+3}$ Figure 1: Main
correspondence.

Finally, this paper constructs two more new maps $\theta$ and $\psi$ to
complete the diagram (see Figure 1) of correspondences among the three
combinatorial models.

######  Main Theorem.

The maps $\phi$, $\theta$ and $\psi$ on Figure 1 give a bijective
correspondence among perfect matchings on the snake graphs
$G_{T,\gamma_{n+3}}$, compatible pairs on maximal Dyck paths
$\mathcal{D}^{\left(n+1\right)\times n}$, and nondecreasing Dyck paths of
length $2n+4$.

We expect our explicit construction in the case of $\mathcal{A}(2,2)$ cluster
algebra considered here will shed light into finding the analogy of bijective
correspondences in higher rank combinatorial models and discrete dynamical
systems [6, 9, 14], in particular to cluster algebra arising from other
surfaces and the more general canonical theta bases constructed in [8], in
which the greedy basis is a special case [1]. A $q$-graded version of the
correspondence may also be studied in relation to quantum cluster algebra and
their quantum theta basis [2].

The paper is organized as follows. We recall the general definition of cluster
algebra in Section 2.1 and then cluster algebra from surfaces in Section 2.2.
In Section 2.3, we recall the construction of snake graphs and expansion
formula for cluster variables in terms of perfect matchings on these graphs.
In Section 2.4, we recall the definition of compatible pairs on maximal Dyck
paths. We give recursion relations between an extended sequence of cluster
variables and count the number of perfect matchings related to cluster algebra
on an annulus in Section 3. In Section 4 and Section 5, we prove that the
number of compatible pairs on the maximal Dyck path and nondecreasing paths of
length $2n$ are both odd-indexed Fibonacci numbers. In Section 6, we give the
proof of the Main Theorems.

## Acknowledgment

This study is conducted under the Undergraduate Research Opportunities Program
(UROP) at The Hong Kong University of Science and Technology. The first author
is supported by the Hong Kong RGC General Research Funds [GRF #16305122].

##  2 Preliminaries

In this section, we recall some basic definitions and properties about cluster
algebra arising from surfaces and their expansion formulas using snake graphs,
as well as the greedy basis of rank $2$ cluster algebra.

###  2.1 Cluster algebra

We review the construction of cluster algebra, first introduced by Fomin and
Zelevinsky [5]. Our terminologies are based on [7], that are rewritten in [11,
15, 17].

To define cluster algebra $\mathcal{A}$, we must first fix its ground ring.

######  Definition 2.1.

A _semifield_ $(\mathbb{P},\oplus,\circ)$ is an abelian multiplicative group
$(\mathbb{P},\circ)$ together with a binary operation $\oplus$ such that

$\oplus:\mathbb{P}\times\mathbb{P}\longrightarrow\mathbb{P}$ $(p,q)\mapsto
p\oplus q$ (2.1)

is commutative, associative, and distributive:

$p\circ(q\oplus r)=p\circ q\oplus p\circ r$ (2.2)

######  Remark 2.2.

The binary operation $\oplus$ may not be invertible.

Let $\mathbb{Z}\mathbb{P}$ be the group ring of $(\mathbb{P},\circ)$, which is
torsion free. Hence we can define the field of rational functions
$\mathcal{F}=\mathbb{Q}\mathbb{P}(x_{1},x_{2},...,x_{n})$ in $n$ variables
with coefficients in $\mathbb{Q}\mathbb{P}$.

######  Definition 2.3.

A _seed_ is a triple $\Sigma=(\textbf{x},\textbf{y},B)$ where

  * •

$\textbf{x}=\\{x_{1},x_{2},...,x_{n}\\}$ is a transcendental basis of
$\mathcal{F}$ over $\mathbb{Q}\mathbb{P}$.

  * •

$\textbf{y}=\\{y_{1},y_{2},...,y_{n}\\}$ is an $n$-tuple of elements
$y_{i}\in\mathbb{P}$.

  * •

$B=(b_{ij})$ is a skew-symmetrizable $n\times n$ integer matrix.

The set x is called a _cluster_ and its elements $x_{i}$ are the _cluster
variables_. The set y is called the _coefficient tuple_ and $B$ is called the
_exchange matrix_.

Throughout the paper, for any $x\in\mathbb{R}$ we will use the notation

$\displaystyle[x]_{+}:=\max(x,0).$ (2.3)

######  Definition 2.4.

A _mutation_ $\mu_{k}(\textbf{x},\textbf{y},B)$ is a new seed
$\Sigma^{\prime}:=(\textbf{x}^{\prime},\textbf{y}^{\prime},B^{\prime})$ such
that

  * •

$\mathbf{x}^{\prime}:=(\mathbf{x}\setminus\\{x_{k}\\})\cup\\{x_{k}^{\prime}\\}$
where $x_{k}^{\prime}\in\mathcal{F}$ is determined by the _exchange relation_

$x_{k}^{\prime}:=\frac{y_{k}\Pi x_{i}^{[b_{ik}]_{+}}+\Pi
x_{i}^{[-b_{ik}]_{+}}}{(y_{k}\oplus 1)x_{k}},$ (2.4)

  * •

$\mathbf{y}^{\prime}:=(y_{1}^{\prime},y_{2}^{\prime},...,y_{n}^{\prime})$
where

$y_{j}^{\prime}:=\left\\{\begin{array}[]{ll}y_{k}^{-1}&\text{ if }j=k,\\\
y_{j}y_{k}^{[b_{kj}]_{+}}(y_{k}\oplus 1)^{-b_{kj}}&\text{ if }j\neq
k,\end{array}\right.$ (2.5)

  * •

$B^{\prime}:=(b_{ij}^{\prime})$ where

$b_{ij}^{\prime}:=\left\\{\begin{array}[]{ll}-b_{ij}&\text{ if }i=k\text{ or
}j=k,\\\ b_{ij}+[-b_{ik}]_{+}b_{kj}+b_{ik}[b_{kj}]_{+}&\text{
otherwise.}\end{array}\right.$ (2.6)

######  Definition 2.5.

Two seeds $\Sigma_{1}$ and $\Sigma_{2}$ are called _mutation equivalent_ if
there is a finite sequence of mutations
$\mu=\mu_{i_{s}}...\mu_{i_{2}}\mu_{i_{1}}$ such that
$\mu\Sigma_{1}=\Sigma_{2}$.

Let $\mathcal{X}$ be the union of all clusters $\mathbf{x}^{\prime}$ belonging
to a seed $(\mathbf{x}^{\prime},\mathbf{y}^{\prime},B^{\prime})$ that is
mutation equivalent to the initial seed $(\mathbf{x},\mathbf{y},B)$. Now, we
are ready to define cluster algebra.

######  Definition 2.6.

The _cluster algebra_ $\mathcal{A}(\mathbf{x},\mathbf{y},B)$ is the
$\mathbb{Z}\mathbb{P}$-subalgebra of the field $\mathcal{F}$ generated by the
set of all cluster variables

$\mathcal{A}(\mathbf{x},\mathbf{y},B):=\mathbb{Z}\mathbb{P}[\mathcal{X}]$
(2.7)

We say that the cluster algebra is _coefficient free_ if $\mathbb{P}=1$, in
which $\mathbb{ZP}=\mathbb{Z}$.

######  Definition 2.7.

The _tropical semifield_ $(\text{Trop}(u_{1},...,u_{m}),\oplus,\circ)$ is
defined to be the semifield of monomials in independent variables $u_{j}$’s
with usual multiplication and semifield addition $\oplus$ given by

$\prod_{j}u_{j}^{a_{j}}\oplus\prod_{j}u_{j}^{b_{j}}=\prod_{j}u_{j}^{\min(a_{j},b_{j})}.$
(2.8)

Note that the group ring of $\text{Trop}(u_{1},...,u_{m})$ is isomorphic to
the ring of Laurent polynomials in the variables $u_{j}$.

######  Definition 2.8.

A cluster algebra $\mathcal{A}(\mathbf{x},\mathbf{y},B)$ is said to have
_principal coefficients_ if the coefficient semifield
$\mathbb{P}=\text{Trop}(y_{1},y_{2},...,y_{n})$ is the tropical semifield with
the initial coefficient tuple $\mathbf{y}=\\{y_{1},y_{2},...,y_{n}\\}$ as a
set of generators. In this case, we say that the corresponding cluster algebra
is of _geometric type_.

###  2.2 Cluster algebra on surfaces

We recall some facts about cluster algebras associated with unpunctured
surfaces [4]. The reader can also refer to [12, 13, 15].

######  Definition 2.9.

A _bordered surface with marked points_ is a pair $(S,M)$ such that $S$ is a
connected oriented two-dimensional Riemann surface with boundary, and the set
of _marked points_ $M$ is a nonempty finite set in the closure of $S$ with at
least one marked point on each boundary component. Marked points in the
interior of $S$ are called _punctures_. The surface $(S,M)$ with all marked
points lying on the boundary of $S$ are called _unpunctured surface_.

In the following, we will only consider unpunctured surfaces.

######  Definition 2.10.

An _arc_ $\gamma$ in $(S,M)$ is a curve in $S$, considered up to isotopy, such
that

  * •

the endpoints of $\gamma$ belongs to $M$;

  * •

except for the endpoints, $\gamma$ is disjoint from $M$ and from the boundary
of $S$;

  * •

$\gamma$ does not cut out an unpunctured 1-gon or an unpunctured 2-gon;

  * •

$\gamma$ does not cross itself, except that its endpoints may coincide;

A _boundary arc_ is a curve that connects two marked points and lies entirely
on the boundary of $S$ without passing through a third marked point. Two arcs
are _compatible_ if they do not cross each other. A _triangulation_ $T$ of an
unpunctured surface $(S,M)$ is a maximal collection of compatible arcs. The
number of arcs $n$ in a triangulation of $S$ is called the _rank_ of the
surface.

######  Example 2.11.

Figure 2 shows the surface $S$ of an annulus with a set of marked points $M$
including 1 marked point on the inner circle and 2 marked points on the outer
circle. A triangulation is given by $T=\\{\tau_{1},\tau_{2},\tau_{3}\\}$ with
the boundary arcs $\tau_{4},\tau_{5},\tau_{6}$.

$\tau_{1}$$\tau_{2}$$\tau_{3}$$\tau_{4}$$\tau_{5}$$\tau_{6}$ Figure 2: A
triangulation $T=\\{\tau_{1},\tau_{2},\tau_{3}\\}$ and boundary arcs
$\tau_{4},\tau_{5},\tau_{6}$.

It is well known that any triangulations can be obtained from each other by a
finite sequence of _flips_. Each flip replaces a single arc $\gamma$ in $T$ by
a unique new arc $\gamma^{\prime}\neq\gamma$ such that

$T^{\prime}=(T\setminus\\{\gamma\\})\cup\\{\gamma^{\prime}\\}$ (2.9)

is another triangulation (see Figure 3).

flip
$\gamma$$\gamma$$\gamma^{\prime}$$\sigma_{1}$$\sigma_{2}$$\sigma_{1}$$\sigma_{2}$$\rho_{2}$$\rho_{1}$$\rho_{2}$$\rho_{1}$
Figure 3: A flip.

######  Remark 2.12.

On an unpunctured surface, there always exists a flip for any single arc
$\gamma$. Moreover, there is no self-folded triangle in both triangulation $T$
and $T^{\prime}$.

We are now ready to define the cluster algebra associated to the surface
$(S,M)$. Fix any triangulation $T=\\{\tau_{1},\tau_{2},...,\tau_{n}\\}$ with
$n$ arcs on $(S,M)$, and denote the $m$ boundary arcs of the surface by
$\tau_{n+1},\tau_{n+2},...,\tau_{n+m}$.

######  Definition 2.13.

For any triangle $\bigtriangleup$ in $T$ define a _minor matrix_
$B^{\bigtriangleup}=(b_{ij}^{\bigtriangleup})_{i,j=1}^{n}$ by

$b_{ij}^{\bigtriangleup}:=\left\\{\begin{array}[]{lll}1&\text{if $\tau_{i}$
and $\tau_{j}$ are sides of $\bigtriangleup$ with $\tau_{j}$ following
$\tau_{i}$ in the counter-clockwise order}\\\ -1&\text{if $\tau_{i}$ and
$\tau_{j}$ are sides of $\bigtriangleup$ with $\tau_{j}$ following $\tau_{i}$
in the clockwise order}\\\ 0&\text{otherwise}\end{array}\right.$ (2.10)

The _exchange matrix_ $B_{T}=(b_{ij})_{i,j=1}^{n}$ is defined by
$b_{ij}=\sum_{\bigtriangleup\in T}b_{ij}^{\bigtriangleup}$, where the sum is
taken over all triangles in $T$.

######  Definition 2.14.

A _cluster algebra on surface_
$\mathcal{A}(\mathbf{x}_{T},\mathbf{y}_{T},B_{T})$ is defined by the cluster
algebra with principal coefficients for a fixed triangulation $T$.

In other words, $\mathcal{A}(\mathbf{x}_{T},\mathbf{y}_{T},B_{T})$ is given by
the initial seed $\Sigma_{T}=(\mathbf{x}_{T},\mathbf{y}_{T},B_{T})$ where

  * •

the initial cluster
$\mathbf{x}_{T}=\\{x_{\tau_{1}},x_{\tau_{2}},...,x_{\tau_{n}}\\}$ is the
cluster associated to the triangulation,

  * •

the initial coefficient vector $\mathbf{y}_{T}=\\{y_{1},y_{2},...,y_{n}\\}$ is
the vector of generators of $\mathbb{P}=\text{Trop}(y_{1},y_{2},...,y_{n})$,
and

  * •

the exchange graph $B_{T}$ defined above.

For the boundary arcs we will set $x_{\tau_{k}}=1$, for $k=n+1,n+2,...,n+m$.
For each $k=1,2,...,n$, there is a unique quadrilateral in
$T\setminus\\{\tau_{k}\\}$ in which $\tau_{k}$ is one of the diagonals. Let
$\tau_{k}^{\prime}$ denote the other diagonal in that quadrilateral. Define
the flip $\mu_{k}(T)$ to be the triangulation
$(T\setminus\\{\tau_{k}\\})\cup\\{\tau_{k}^{\prime}\\}$. We refer to [12] for
the following property.

######  Proposition 2.15.

The mutation $\mu_{k}$ of the seed $\Sigma_{T}$ in the cluster algebra
$\mathcal{A}$ corresponds to the flip $\mu_{k}$ of the triangulation $T$ in
the following sense:

  * •

the matrix $\mu_{k}(B_{T})$ is the matrix corresponding to the triangulation
$\mu_{k}(T)$,

  * •

the cluster $\mu_{k}(\mathbf{x}_{T})$ is
$(\mathbf{x}_{T}\setminus\\{x_{\tau_{k}}\\})\cup\\{x_{\tau_{k}}^{\prime}\\}$,

  * •

the corresponding exchange relation is given by

$x_{\tau_{k}}x_{\tau_{k}}^{\prime}=x_{\rho_{1}}x_{\rho_{2}}y^{+}+x_{\sigma_{1}}x_{\sigma_{2}}y^{-}$
(2.11)

where $y^{+},y^{-}$ are some coefficients in $\mathbb{P}$, and
$\rho_{1},\sigma_{1},\rho_{2},\sigma_{2}$ are the sides of the quadrilateral
in which $\tau_{k}$ and $\tau_{k}^{\prime}$ are the diagonals, such that
$(\rho_{1},\rho_{2})$ and $(\sigma_{1},\sigma_{2})$ lie on opposite sides
respectively (see Figure 3).

###  2.3 Expansion formula

We recall the expansion formula for the cluster variables in terms of perfect
matchings of a graph that is constructed recursively using “tiles”. For
further details, the reader is referred to [12].

######  Definition 2.16.

A _tile_ $\overline{S}_{k}$ is a planar four-vertex graph with five weighted
edges having the shape of two equilateral triangles that share one edge,
oriented as in Figure 4. The parallelogram $S_{k}$ is constructed by removing
the diagonal from $\overline{S}_{k}$.

Now let $T$ be a triangulation of the unpunctured surface $(S,M)$. If
$\tau_{k}\in T$ is an interior arc, then $\tau_{k}$ lies in precisely two
triangles in $T$, hence $\tau_{k}$ is the diagonal of a unique quadrilateral
$Q_{\tau_{k}}$ in $T$ with 4 edges $\tau_{a},\tau_{b},\tau_{c},\tau_{d}$. We
associate to this quadrilateral a tile $\overline{S}_{k}$ by assigning the
weight $x_{k}$ (as a variable) to the diagonal and the weights
$x_{a},x_{b},x_{c},x_{d}$ to the sides of $\overline{S}_{k}$ (see Figure 4).

$x_{a}$$x_{b}$$x_{c}$$x_{d}$$x_{k}$ Figure 4: The tile $\overline{S}_{k}$

Let $\gamma\notin T$ be an arbitrary arc joining two endpoints $s,t$. Choose
an orientation of $\gamma$ and assume $\gamma$ cuts the arcs in $T$ at the
intersections (allowing repeats)

$s:=p_{0},p_{1},p_{2},...,p_{d},p_{d+1}:=t,$ (2.12)

let $i_{1},i_{2},...,i_{d}$ be the indices such that $p_{k}$ lies on the arc
$\tau_{i_{k}}\in T$. For $0\leq k\leq d$, let $\gamma^{k}$ denote the segment
of the path $\gamma$ from the point $p_{k}$ to the point $p_{k+1}$. Each
$\gamma^{k}$ lies in exactly one triangle $\Delta_{k}$ in $T$. For $1\leq
k\leq d-1$, $\Delta_{k}$ is formed by the arcs $\tau_{i_{k}},\tau_{i_{k+1}}$
and a third arc that we denote by $\tau_{[\gamma^{k}]}$ for some index
$[\gamma^{k}]\in\\{1,2,...,n+m\\}$.

For $1\leq k\leq d-1$, we glue tiles $\overline{S}_{i_{k}}$ and
$\overline{S}_{i_{k+1}}$ along the common edge $\tau_{[\gamma^{k}]}$ such that
the triangle
$\Delta_{k}=\\{\tau_{i_{k}},\tau_{i_{k+1}},\tau_{[\gamma^{k}]}\\}$ is oriented
differently in the two tiles (see Figure 5).

$x_{[\gamma^{k}]}$$x_{i_{k}}$$x_{i_{k}}$$x_{i_{k+1}}$$x_{i_{k+1}}$ Figure 5:
Gluing tiles $\overline{S}_{i_{k}}$ and $\overline{S}_{i_{k+1}}$ along the
edge weighted $x_{[\gamma^{k}]}$

######  Definition 2.17.

The _full graph_ $\overline{G}_{T,\gamma}$ is constructed by gluing tiles
$\overline{S}_{{i_{1}}},\overline{S}_{{i_{2}}},...,\overline{S}_{{i_{d}}}$
together with the procedure above, such that the first tile have the
orientation induced from the surface, and the starting point $p_{0}$ of
$\gamma$ lies in the southwest corner of the first tile. The _snake graph_
$G_{T,\gamma}$ is obtained from the full graph by removing the diagonal
$\tau_{i_{k}}$ of each tile $\overline{S}_{{i_{k}}}$.

######  Definition 2.18.

A _perfect matching_ $P$ of a graph is a subset of the edges so that each
vertex belongs to exactly one edge in $P$. The _weight_ $w(P)$ of a perfect
matching $P$ of $G_{T,\gamma}$ is the product of all the weights assigned to
the edges in $P$.

There are precisely two perfect matchings $P_{+}$ and $P_{-}$ of
$G_{T,\gamma}$ that contain only the boundary edges of $G_{T,\gamma}$. The
matching $P_{-}$ contains the western (left-most) edge of the bottom-most tile
on $G_{T,\gamma}$, while $P_{+}$ contains the southern (bottom) edge.

######  Definition 2.19.

The _symmetric difference_ of a perfect matching $P$ is a subgraph $G_{P}$ of
$G_{T,\gamma}$ given by

$G_{P}:=P_{-}\ominus P=(P_{-}\cup P)\setminus(P_{-}\cap P)$ (2.13)

Given an unpunctured surface $(S,M)$ and a triangulation
$T=\\{\tau_{1},\tau_{2},...,\tau_{n}\\}$, we consider the cluster algebra
$\mathcal{A}:=\mathcal{A}(\mathbf{x}_{T},\mathbf{y}_{T},B_{T})$ as defined in
Section 2.2. Each arc $\gamma$ in $(S,M)$ corresponds to a cluster variable
$x_{\gamma}$ in $\mathcal{A}$, with the arcs in $T$ corresponding to the
initial cluster $\mathbf{x}_{T}$. In the following we will denote the initial
cluster variables by $x_{k}:=x_{\tau_{k}}$.

We can now state the following theorems [12] about cluster expansion.

######  Theorem 2.20.

The set $P_{-}\ominus P$ is the set of boundary edges of a (possibly
disconnected) subgraph $G_{P}$ of $G_{T,\gamma}$ which is a union of tiles

$G_{P}=\bigcup_{j\in J}S_{j}.$ (2.14)

Define a monomial in $y_{T}$ by

$y(P):=\prod_{j\in J}y_{i_{j}}.$ (2.15)

######  Theorem 2.21.

Any cluster variable can be expressed as a Laurent polynomial of the initial
variables by

$x_{\gamma}=\sum_{P}\frac{w(P)y(P)}{x_{i_{1}}x_{i_{2}}...x_{i_{d}}}$ (2.16)

where the sum is over all perfect matchings $P$ of $G_{T,\gamma}$, $w(P)$ is
the weight of $P$, and $y(P)$ is defined as in (2.15).

###  2.4 Maximal Dyck path and compatible pairs

Any rank $2$ cluster algebra of finite or affine type has a $\mathbb{Z}$-basis
that includes elements called _indecomposable positives_ [16]. A special
family called _greedy elements_ is first introduced in [10]. These elements
are proven to be indecomposable positives, hence form a $\mathbb{Z}$-basis of
the cluster algebra. There are several expressions of greedy elements, but
this subsection only introduces the one mentioned in [10].

In the following, a rank $2$ cluster algebra is of the form
$\mathcal{A}:=\mathcal{A}(b,c)$ defined by the exchange matrix
$B=\begin{pmatrix}0&b\\\ -c&0\end{pmatrix}$, where $b,c\in\mathbb{N}$. It is
generated by the initial cluster $\\{x_{1},x_{2}\\}$ and the exchange
relations for $n\in\mathbb{Z}$

$x_{n-1}x_{n+1}=\left\\{\begin{array}[]{ll}x_{n}^{b}+1&\text{for $n$ odd},\\\
x_{n}^{c}+1&\text{for $n$ even}.\\\ \end{array}\right.$ (2.17)

To express greedy elements in $\mathcal{A}(b,c)$, we need some terminologies.

######  Definition 2.22.

For $a_{1},a_{2}\in\mathbb{Z}_{\geq 0}$, a _Dyck path_ of dimension
$a_{1}\times a_{2}$ is a lattice path going from $(0,0)$ to $(a_{1},a_{2})$
that just go up or to the right, but is never higher than the straight line
joining $(0,0)$ and $(a_{1},a_{2})$. A Dyck path is _maximal_ if it is not
lower than any other Dyck path.

In the dimension $a_{1}\times a_{2}$, the maximal Dyck path is unique, denoted
by $\mathcal{D}=\mathcal{D}^{a_{1}\times a_{2}}$. Let
$\mathcal{D}_{1}=\\{u_{1},...,u_{a_{1}}\\}$ be the set of horizontal edges of
$\mathcal{D}$ indexed from left to right, and
$\mathcal{D}_{2}=\\{v_{1},...,v_{a_{2}}\\}$ the set of vertical edges of
$\mathcal{D}$ indexed from bottom to top.

In the following, it is convenient to regard $(0,0)$ and $(a_{1},a_{2})$ as
the same point.

######  Definition 2.23.

For any points $A$ and $B$ on $\mathcal{D}$, the _subpath $AB$_ is the path of
$\mathcal{D}$ starting from $A$ and going in the Northeast direction until it
reaches $B$ (if we reach $(a_{1},a_{2})$ first, we loop back to $(0,0)$).

######  Remark 2.24.

In the special case $A=B$, define the subpath $AA$ to be the path that starts
from A until it reaches $(a_{1},a_{2})$, loops back to $(0,0)$, and then ends
at $A$.

We denote by $(AB)_{1}$ the set of horizontal edges in $AB$ and by $(AB)_{2}$
the set of vertical edges in $AB$. Also, let $AB^{\circ}$ denote the set of
lattice points on the subpath $AB$ excluding the endpoints $A$ and $B$.

######  Example 2.25.

Figure 11 shows the maximal Dyck path $\mathcal{D}^{6\times 4}$, where
$\mathcal{D}_{1}=\\{u_{1},u_{2},u_{3},u_{4},u_{5},u_{6}\\}$ and
$\mathcal{D}_{2}=\\{v_{1},v_{2},v_{3},v_{4}\\}$. We choose $A=(5,2),B=(2,1)$,
with subpath $AB=(v_{3},u_{6},v_{4},u_{1},u_{2},v_{1})$ and the set of lattice
points $AB^{\circ}=\\{(5,3),(6,3),(6,4)=(0,0),(1,0),(2,0)\\}$.

$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$A$$B$
Figure 6: The maximal Dyck path of $\mathcal{D}^{6\times 4}$

######  Definition 2.26.

A pair $(S_{1},S_{2})$ with $S_{1}\subset\mathcal{D}_{1}$,
$S_{2}\subset\mathcal{D}_{2}$ is called _compatible_ if for every $u\in
S_{1},v\in S_{2}$, there exists $A\in EF^{\circ}$ ,where $E$ is the left
endpoint of $u$ and $F$ is the upper endpoint of $v$, such that:

$|(AF)_{1}|=b|(AF)_{2}\cap S_{2}|\text{ or }|(EA)_{2}|=c|(EA)_{1}\cap S_{1}|$
(2.18)

Now, we recall the expression of greedy elements mentioned in [10].

######  Theorem 2.27.

For any $a_{1},a_{2}\in\mathbb{Z}$, the _greedy element_
$x[a_{1},a_{2}]\in\mathcal{A}(b,c)$ is defined by

$x[a_{1},a_{2}]:=x_{1}^{-a_{1}}x_{2}^{-a_{2}}\sum_{(S_{1},S_{2})}x_{1}^{b|S_{2}|}x_{2}^{c|S_{1}|}.$
(2.19)

where the sum is over all compatible pairs $(S_{1},S_{2})$ in
$\mathcal{D}^{{[a_{1}]_{+}}\times{[a_{2}]_{+}}}$.

######  Remark 2.28.

If $a_{1}\leq 0$ and $a_{2}\leq 0$, then by the definition,

$\displaystyle x[a_{1},a_{2}]=x_{1}^{-a_{1}}x_{2}^{-a_{2}}.$ (2.20)

######  Definition 2.29.

For any $p\in\mathbb{Z}$, we denote the _standard permutation_ for cluster
variable

$\sigma_{p}(x_{n})=x_{2p-n}.$ (2.21)

We recall some propositions in [10].

######  Proposition 2.30.

The set of all greedy elements

$\displaystyle\mathcal{B}:=\\{x[a_{1},a_{2}]:a_{1},a_{2}\in\mathbb{Z}\\}$
(2.22)

forms a $\mathbb{Z}$-basis of $\mathcal{A}(b,c)$. It is called the _greedy
basis_.

######  Proposition 2.31.

The greedy basis $\mathcal{B}$ is invariant under the action of any
$\sigma_{p}$, $p\in\mathbb{Z}$. Specifically, $\sigma_{p}$ can be written as a
composition of some automorphisms $\sigma_{1}$ and $\sigma_{2}$, where they
act on the greedy elements as:

$\displaystyle\sigma_{1}(x[a_{1},a_{2}])$
$\displaystyle:=x[a_{1},c[a_{1}]_{+}-a_{2}],$ (2.23)
$\displaystyle\sigma_{2}(x[a_{1},a_{2}])$
$\displaystyle:=x[b[a_{2}]_{+}-a_{1},a_{2}].$ (2.24)

##  3 Perfect matchings of the snake graph

In this section, we study the cluster algebra associated to an annulus with
one marked point on each boundary circle by using perfect matchings on the
snake graphs mentioned in Section 2.3. We find some recurrence relations
between cluster variables associated with the arcs.

Let $(S,M)$ be the annulus with one marked point on each of the two boundary
components, and let $T=\\{\tau_{1},\tau_{2}\\}$ be the triangulation with
boundary arcs $\tau_{3},\tau_{4}$ shown in Figure 7. Denote the marked points
to be $M_{1}$ and $M_{2}$. Let
$\mathcal{A}(\textbf{x}_{T},\textbf{y}_{T},B_{T})$ be the cluster algebra
associated to this triangulation with the initial cluster
$\textbf{x}_{T}=\\{x_{1},x_{2}\\}$ and the initial coefficient vector
$\textbf{y}_{T}=\\{y_{1},y_{2}\\}$. The exchange matrix of this triangulation
is

$B_{T}=\begin{pmatrix}0&2\\\ -2&0\end{pmatrix}.$ (3.1)

$M_{1}$$M_{2}$$P_{1}$$P_{2}$$P_{3}$$\tau_{1}$$\tau_{2}$$\tau_{3}$$\tau_{4}$$\gamma_{5}$
Figure 7: Annulus with triangulation $T=\\{\tau_{1},\tau_{2}\\}$ and the arc
$\gamma_{4}$ (shown in red)

######  Definition 3.1.

For $k\geq 3$, define $\gamma_{k}$ to be the arc that

  * •

wraps clockwise around the inner circle $(k-2)$ times and cut
$\tau_{1},\tau_{2}$ at $k-2,k-3$ points respectively.

  * •

starts from $M_{1}$ through the corner $(\tau_{2},\tau_{3})$ of the triangle
$\Delta=\\{\tau_{1},\tau_{2},\tau_{3}\\}$.

  * •

goes into the corner $(\tau_{2},\tau_{4})$ of the triangle
$\Delta=\\{\tau_{1},\tau_{2},\tau_{4}\\}$ and then ends at $M_{2}$.

The definition gives the following flips of triangulations:

  * •

flips $T=(\tau_{1},\tau_{2})$ along $\tau_{1}$, we get another triangulation
$T^{\prime}=(\tau_{2},\gamma_{3})$,

  * •

flips $T^{\prime}=(\tau_{2},\gamma_{3})$ along $\tau_{2}$, we get
$T^{\prime\prime}=(\gamma_{3},\gamma_{4})$,

  * •

for $k\geq 3$, flips $(\gamma_{k},\gamma_{k+1})$ along $\gamma_{k}$, we get
$(\gamma_{k+1},\gamma_{k+2})$.

Next, for any $k\geq 3$, the full graph $\overline{G}_{T,\gamma_{k}}$ and
snake graph $G_{T,\gamma_{k}}$ are constructed as in Section 2.3. They consist
of $(2k-5)$ parallelograms stacked consecutively on top of each other.

######  Example 3.2.

Figure 7 shows the arc $\gamma_{4}$ cutting $\tau_{1},\tau_{2}$ at
$P_{1},P_{2},P_{3}$ in clockwise direction. Figure 8 shows the graphs
$\overline{G}_{T,\gamma_{4}}$ and $G_{T,\gamma_{4}}$.

We recall the expansion formula in Section 2.3:

$x_{\gamma_{k}}=\sum_{P}\frac{w(P)y(P)}{x_{1}^{k-2}x_{2}^{k-3}}$ (3.2)

where the sum is over all perfect matchings $P$ of $G_{T,\gamma_{k}}$.

The snake graphs $G_{T,\gamma_{k}}$ contain only an odd number of
parallelograms. Therefore, for convenience in calculation, we introduce the
following graphs.

######  Definition 3.3.

The graphs $\overline{H}_{1},\overline{H}_{2},...$ is defined by

  * •

For $n\geq 0$, $\overline{H}_{2n+1}=\overline{G}_{T,\gamma_{n+3}}$

  * •

For $n\geq 1$, $\overline{H}_{2n}$ is obtained from
$\overline{G}_{T,\gamma_{n+3}}$ by deleting the top parallelogram.

Similarly, the graph $H_{n}$ is obtained from $\overline{H}_{n}$ by deleting
the diagonals of its parallelograms. Now the graphs $H_{n}$ have $n$
parallelograms. For even more convenience, we can draw $H_{n}$ horizontally as
$n$ consecutive squares (see Figure 9). The configuration is now good enough
for calculation.

Inspired by the expansion formula, for $n\geq 1$, we introduce the following
variables

$z_{2n-1}:=\sum_{P}\frac{w(P)y(P)}{x_{1}^{n}x_{2}^{n-1}}$ (3.3)
$z_{2n}:=\sum_{P}\frac{w(P)y(P)}{x_{1}^{n}x_{2}^{n}}$ (3.4)

where the sums are over all perfect matchings $P$ of $H_{2n-1}$ and $H_{2n}$
respectively.

######  Remark 3.4.

The relationship between the cluster variables and the sequence $\\{z_{n}\\}$
is given by

$x_{\gamma_{k}}=z_{2k-5}.$ (3.5)

######  Example 3.5.

Figure 8 shows the graphs of
$\overline{H}_{2},H_{2},\overline{H}_{3}=\overline{G}_{T,\gamma_{4}},H_{3}=G_{T,\gamma_{4}}$.
Then, applying the formula of $z_{n}$ on all perfect matchings of $H_{n}$, we
have

$\displaystyle z_{1}(x_{1})$ $\displaystyle=(x_{3}x_{4})(y_{1})$ (3.6)
$\displaystyle+(x_{2}x_{2})$ $\displaystyle z_{2}(x_{1}x_{2})$
$\displaystyle=(x_{3}x_{4}x_{3})(y_{1})$ (3.7)
$\displaystyle+(x_{3}x_{1}x_{1})(y_{1}y_{2})$
$\displaystyle+(x_{2}x_{2}x_{3})$ $\displaystyle z_{3}(x_{1}x_{2}x_{1})$
$\displaystyle=(x_{3}x_{4}x_{3}x_{4})(y_{1}y_{1})$ (3.8)
$\displaystyle+(x_{3}x_{4}x_{2}x_{2})(y_{1})$
$\displaystyle+(x_{3}x_{1}x_{1}x_{4})(y_{1}y_{2}y_{1})$
$\displaystyle+(x_{2}x_{2}x_{3}x_{4})(y_{1})$
$\displaystyle+(x_{2}x_{2}x_{2}x_{2}).$

$\overline{H}_{2}$$A_{0}$$A_{1}$$A_{2}$$B_{0}$$B_{1}$$B_{2}$$x_{3}$$x_{4}$$x_{3}$$x_{2}$$x_{2}$$x_{1}$$x_{1}$$x_{1}$$x_{2}$$H_{2}$$A_{0}$$A_{1}$$A_{2}$$B_{0}$$B_{1}$$B_{2}$$x_{3}$$x_{4}$$x_{3}$$x_{2}$$x_{2}$$x_{1}$$x_{1}$$\overline{G}_{T,\gamma_{4}}=\overline{H}_{3}$$A_{0}$$A_{1}$$A_{2}$$A_{3}$$B_{0}$$B_{1}$$B_{2}$$B_{3}$$x_{3}$$x_{4}$$x_{3}$$x_{4}$$x_{2}$$x_{2}$$x_{1}$$x_{1}$$x_{2}$$x_{2}$$x_{1}$$x_{2}$$x_{1}$$G_{T,\gamma_{4}}=H_{3}$$A_{0}$$A_{1}$$A_{2}$$A_{3}$$B_{0}$$B_{1}$$B_{2}$$B_{3}$$x_{3}$$x_{4}$$x_{3}$$x_{4}$$x_{2}$$x_{2}$$x_{1}$$x_{1}$$x_{2}$$x_{2}$
Figure 8: $\overline{H}_{2},H_{2}$; the full and snake graphs of the arcs
$\gamma_{4}$

Let $A_{0},A_{1},...,A_{k}$ and $B_{0},B_{1},...,B_{k}$ be vertices and
$x_{i}$ be weights on edges of the graph $H_{k}$. The graph $P_{-}$ contains
edges of the form $A_{2i}A_{2i+1},B_{2i}B_{2i+1}$.

######  Example 3.6.

Figure 9 shows perfect matchings $P$ on $H_{13}=G_{T,\gamma_{9}}$ and $P_{1}$
on $H_{12}$. The third and fourth graphs are their symmetric differences
$H_{P}$ and $H_{P_{1}}$ with $P_{-}$.

$x_{2}$$x_{1}$$x_{2}$$x_{1}$$x_{2}$$x_{1}$$x_{2}$$x_{1}$$x_{2}$$x_{1}$$x_{2}$$x_{1}$$x_{2}$$x_{2}$$x_{1}$$x_{2}$$x_{1}$$x_{2}$$x_{1}$$x_{2}$$x_{1}$$x_{2}$$x_{1}$$x_{2}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{3}$$x_{4}$$x_{3}$$x_{4}$$x_{3}$$x_{4}$$x_{3}$$x_{4}$$x_{3}$$x_{4}$$x_{3}$$x_{4}$$B_{0}$$B_{1}$$B_{2}$$B_{3}$$B_{4}$$B_{5}$$B_{6}$$B_{7}$$B_{8}$$B_{9}$$B_{10}$$B_{11}$$B_{12}$$B_{13}$$A_{0}$$A_{1}$$A_{2}$$A_{3}$$A_{4}$$A_{5}$$A_{6}$$A_{7}$$A_{8}$$A_{9}$$A_{10}$$A_{11}$$A_{12}$$A_{13}$$S_{1}$$S_{2}$$S_{1}$$S_{2}$$S_{1}$$S_{2}$$S_{1}$$S_{2}$$S_{1}$$S_{2}$$S_{1}$$S_{2}$$S_{1}$$S_{1}$$S_{2}$$S_{1}$$S_{2}$$S_{1}$$S_{2}$$S_{1}$$S_{2}$$S_{1}$$S_{2}$$S_{1}$$S_{2}$$P$$P_{1}$$H_{P}$$H_{P_{1}}$
Figure 9: Perfect matchings and their symmetric differences. (The colors will
be explained in Example 6.1.)

######  Proposition 3.7.

With the above notations, for $k\geq 1$,

$z_{2k+1}=(x_{1}^{-1}x_{4}y_{1})z_{2k}+(x_{1}^{-1}x_{2})z_{2k-1}.$ (3.9)
$z_{2k+2}=(x_{2}^{-1}x_{3})z_{2k+1}+(x_{1}x_{2}^{-1}y_{1}y_{2})z_{2k}.$ (3.10)

###### Proof.

If $P$ is a perfect matching of $H_{2n+1}$ then $P$ contains
$\\{A_{2k+1}B_{2k+1}\\}$ or $\\{A_{2k}A_{2k+1},B_{2k}B_{2k+1}\\}$ in the last
portion.

  * •

If the perfect matching $P$ contains $\\{A_{2k+1}B_{2k+1}\\}$ (see Figure 9):

    * –

$P_{1}=P\setminus\\{A_{2k+1}B_{2k+1}\\}$ is a perfect matching of $H_{2n}$,

    * –

$H_{P}=H_{P_{1}}\cup S_{1}$.

  * •

If the perfect matching $P$ contains $\\{A_{2k}A_{2k+1},B_{2k}B_{2k+1}\\}$
(similar to the previous case):

    * –

$P_{2}=P\setminus\\{A_{2k}A_{2k+1},B_{2k}B_{2k+1}\\}$ is a perfect matching of
$H_{2n-1}$,

    * –

$H_{P}=H_{P_{2}}$.

Conversely, we can get a perfect matching of $H_{2n+1}$ from perfect matching
of $H_{2n}$ by adding the edge $A_{2k+1}B_{2k+1}$ and from perfect matching of
$H_{2n-1}$ by adding the edges $A_{2k}A_{2k+1},B_{2k}B_{2k+1}$. So, from
Theorem 2.20–2.21, we have:

$\displaystyle z_{2k+1}$ $\displaystyle=\sum_{P\in
H_{2k+1}}\frac{w(P)y(P)}{x_{1}^{k+1}x_{2}^{k}}$ $\displaystyle=\sum_{P_{1}\in
H_{2k}}\frac{(x_{4}w(P_{1}))(y_{1}y(P_{1}))}{x_{1}^{k+1}x_{2}^{k}}+\sum_{P_{2}\in
H_{2k-1}}\frac{(x_{2}^{2}w(P_{2}))(y(P_{2}))}{x_{1}^{k+1}x_{2}^{k}}$
$\displaystyle=(x_{1}^{-1}x_{4})z_{2k}+(x_{1}^{-1}x_{2})z_{2k-1}.$

By the same method for the perfect matchings of $H_{2n+2}$, we get

$z_{2k+2}=(x_{2}^{-1}x_{3})z_{2k+1}+(x_{1}x_{2}^{-1}y_{1}y_{2})z_{2k}.$

∎

######  Corollary 3.8.

The number of perfect matchings on the graph $H_{n}$ is $F_{n+2}$.

###### Proof.

Let $|z_{k}|$ be the value of $z_{k}$ by setting
$x_{1}=x_{2}=x_{3}=x_{4}=y_{1}=y_{2}=1$. We will prove by induction that

$|z_{k}|=F_{k+2}$

for any $k\geq 1$. The base case $|z_{1}|=2=F_{3}$ and $|z_{2}|=3=F_{4}$ are
true as shown in Example 3.5. Suppose that the claim is true for $k\leq n$,

  * •

If $n$ is odd,

$z_{n+1}=(x_{1}^{-1}x_{4}y_{1})z_{n}+(x_{1}^{-1}x_{2})z_{n-1}\implies|z_{n+1}|=|z_{n}|+|z_{n-1}|=F_{n+2}+F_{n+1}=F_{n+3}.$

  * •

If $n$ is even,

$z_{n+1}=(x_{2}^{-1}x_{3})z_{n}+(x_{1}x_{2}^{-1}y_{1}y_{2})z_{n-1}\implies|z_{n+1}|=|z_{n}|+|z_{n-1}|=F_{n+2}+F_{n+1}=F_{n+3}.$

Thus the claim is true for $k=n+1$, so the claim is true for any $k\geq 1$ by
induction. Moreover, by the definition

$z_{n}=\sum_{P}\frac{w(P)y(P)}{x_{i_{1}}x_{i_{2}}...x_{i_{d}}}$

where the sum is over all perfect matchings $P$ of $H_{n}$. Since each term
becomes $1$ under the evaluation, $|z_{n}|$ is the number of perfect matchings
on the graph $H_{n}$. ∎

######  Corollary 3.9.

In the coefficient free case, the sum of coefficients in the Laurent
polynomials of the cluster variables $x_{\gamma_{k}}$ is $F_{2n-3}$

###### Proof.

The sum of coefficients in the Laurent polynomials is equal to the number of
perfect matchings on the graph $G_{\gamma_{k}}=H_{2k-5}$, that is $F_{2n-3}$.
∎

##  4 Compatible pairs on the maximal Dyck path

In this section, we prove that the cluster variable $x_{n}$ in
$\mathcal{A}(2,2)$ is the greedy element $x[n-2,n-3]$ which is a Laurent
polynomial of the initial cluster $\\{x_{1},x_{2}\\}$. Then we use compatible
pairs on the maximal Dyck path $\mathcal{D}^{(n-2)\times(n-3)}$ to calculate
these greedy elements, see Section 2.4 for the terminologies.

Consider the coefficient free cluster algebra $\mathcal{A}(2,2)$ with initial
cluster $\\{x_{1},x_{2}\\}$ and exchange relation $x_{n-1}x_{n+1}=x_{n}^{2}+1$
for $n\in\mathbb{Z}$. We first prove the following lemma.

######  Lemma 4.1.

For $n\geq 2$, the cluster variable

$x_{n}=x[n-2,n-3].$ (4.1)

###### Proof.

By Proposition 2.31,

$\sigma_{1}(x[a_{1},a_{2}])=x[a_{1},2[a_{1}]_{+}-a_{2}]\text{ and
}\sigma_{2}(x[a_{1},a_{2}])=x[2[a_{2}]_{+}-a_{1},a_{2}].$

For the base cases, $x_{1}=x_{1}^{1}x_{2}^{0}=x[-1,0]$ and
$x_{2}=x_{1}^{0}x_{2}^{1}=x[0,-1]$, thus

$x_{3}=\sigma_{2}(x_{1})=\sigma_{2}(x[-1,0])=x[1,0].$

Suppose that $x_{k}=x[k-2,k-3]$ for any $k\leq n+1$, then:

$\displaystyle x_{n+2}$ $\displaystyle=\sigma_{2}(\sigma_{1}(x_{n}))$
$\displaystyle=\sigma_{2}(\sigma_{1}(x[n-2,n-3]))$
$\displaystyle=\sigma_{2}(x[n-2,n-1])$ $\displaystyle=x[n,n-1].$

Hence the statement is true by induction. ∎

The maximal Dyck path $\mathcal{D}^{(n+1)\times n}$ is determined as in Figure
10, where we label its vertices by $A_{0},A_{1},...A_{n},A_{n+1}\equiv A_{0}$,
and $B_{0}\equiv A_{1},B_{1},B_{2},...,B_{n}$. Let
$\mathcal{D}_{1}=\\{u_{0},u_{1},...,u_{n}\\},\mathcal{D}_{2}=\\{v_{1},v_{2},...,v_{n}\\}$
be the sets of horizontal and vertical edges respectively on the maximal Dyck
path. Note that

$\displaystyle u_{i}$ $\displaystyle=A_{i}B_{i},\quad\quad 0\leq i\leq n,$
(4.2) $\displaystyle v_{j}$ $\displaystyle=B_{j}A_{j+1},\quad\quad 1\leq j\leq
n.$ (4.3)

For $S_{1}\subset\mathcal{D}_{1},S_{2}\subset\mathcal{D}_{2}$, to facilitate
the calculation we define the following functions.

######  Definition 4.2.

For $C\in(AB)^{\circ}$, the _step functions_ are defined by

$\displaystyle f(C,AB)$ $\displaystyle:=|(AC)_{2}|-2|(AC)_{1}\cap S_{1}|,$
(4.4) $\displaystyle g(C,AB)$ $\displaystyle:=|(CB)_{1}|-2|(CB)_{2}\cap
S_{2}|.$ (4.5)

######  Proposition 4.3.

In the maximal Dyck path $\mathcal{D}^{(n+1)\times n}$, $(S_{1},S_{2})$ is a
compatible pair if and only if for any $u_{i}\in S_{1},v_{j}\in S_{2}$:

$\max_{C\in(A_{i}A_{j+1})^{\circ}}\\{f(C,A_{i}A_{j+1}),g(C,A_{i}A_{j+1})\\}\geq
0.$ (4.6)

###### Proof.

By Definition 2.26, $(S_{1},S_{2})$ is a compatible pair if and only if there
exists $C\in(A_{i}A_{j+1})^{\circ}$ such that $f(C,A_{i}A_{j+1})=0$ or
$g(C,A_{i}A_{j+1})=0$.

In particular if $(S_{1},S_{2})$ is a compatible pair, then condition (4.6)
clearly holds.

Now assume the condition (4.6) holds. We observe that if $u_{i}\in
S_{1},v_{j}\in S_{2}$ then

$f(B_{i},A_{i}A_{j+1})=g(B_{j},A_{i}A_{j+1})=-2$

when $C\in(A_{i}A_{j+1})^{\circ}$ is nearest to $A_{i}$ or $A_{j+1}$. We also
note that

  * •

if $A_{k},B_{k}\in(A_{i}A_{j+1})^{\circ}$ where $0\leq k\leq n$, then

$f(B_{k},A_{i}A_{j+1})-f(A_{k},A_{i}A_{j+1})\in\\{0,-2\\},$

  * •

if $B_{k},A_{k+1}\in(A_{i}A_{j+1})^{\circ}$ where $1\leq k\leq n$, then

$f(A_{k+1},A_{i}A_{j+1})-f(B_{k},A_{i}A_{j+1})=1.$

Thus, $f$ may increase by no more than 1 when $C$ travels from $B_{i}$ to
$B_{j}$ in the Northeast direction. Similarly,

  * •

if $A_{k},B_{k}\in(A_{i}A_{j+1})^{\circ}$ for some $0\leq k\leq n$, then

$g(A_{k},A_{i}A_{j+1})-g(B_{k},A_{i}A_{j+1})=1,$

  * •

if $B_{k},A_{k+1}\in(A_{i}A_{j+1})^{\circ}$ for some $1\leq k\leq n$, then

$g(B_{k},A_{i}A_{j+1})-g(A_{k+1},A_{i}A_{j+1})\in\\{0,-2\\}.$

Thus, $g$ may increase by no more than 1 when $C$ travels from $B_{j}$ back to
$B_{i}$ in the Southwest direction.

Since $f$ may increase by no more than 1, if $f(C,A_{i}A_{j+1})>0$, there
exists $D\in(A_{i}C)^{\circ}$ such that $f(D,A_{i}A_{j+1})=0$. Similarly since
$g$ may decrease by no more than $1$ when $C$ travels backward, if
$g(C,A_{i}A_{j+1})>0$ for some $C\in(A_{i}A_{j+1})^{\circ}$, there exists
$D\in(CA_{j+1})^{\circ}$ such that $g(D,A_{i}A_{j+1})=0$. In other words
$(S_{1},S_{2})$ is a compatible pair. ∎

$u_{0}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{5}$$u_{6}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$A_{0}$$A_{1}\equiv
B_{0}$$A_{2}$$A_{3}$$A_{4}$$A_{5}$$A_{6}$$A_{7}\equiv
A_{0}$$B_{1}$$B_{2}$$B_{3}$$B_{4}$$B_{5}$$B_{6}$ Figure 10: A compatible pair
on the maximal Dyck path $\mathcal{D}^{7\times 6}$ with solid edges. (The
colors will be explained in Example 6.1.)

######  Lemma 4.4.

$(S_{1},S_{2})$ is a compatible pair in $\mathcal{D}^{(n+1)\times n}$ if and
only if

$\\{j-i|u_{i}\in S_{1},v_{j}\in S_{2}\\}\cap\\{0,1\\}=\emptyset.$ (4.7)

###### Proof.

One direction is clear:

  * •

if $u_{i}\in S_{1},v_{i}\in S_{2}$ for some $1\leq i\leq n$, then
$(A_{i}A_{i+1})^{\circ}=\\{B_{i}\\}$. However,

$f(B_{i},A_{i}A_{i+1})=g(B_{i},A_{i}A_{i+1})=-2,$

so $(S_{1},S_{2})$ is not compatible by Proposition 4.3;

  * •

if $u_{i}\in S_{1},v_{i+1}\in S_{2}$ for some $0\leq i\leq n-1$ then for any
$C\in(A_{i}A_{i+2})^{\circ}=\\{B_{i},A_{i+1},B_{i+1}\\}$,

$f(C,A_{i}A_{i+2})<0\text{ and }g(C,A_{i}A_{i+2})<0$

so $(S_{1},S_{2})$ is not compatible again by Proposition 4.3.

Conversely, if

$\\{j-i|u_{i}\in S_{1},v_{j}\in S_{2}\\}\cap\\{0,1\\}=\emptyset$

then for any $u_{i}\in S_{1},v_{j}\in S_{2}$, either $j-i>1$ or $i>j$. Suppose
on the contrary that both

$f(A_{j},A_{i}A_{j+1})\leq-1\text{ and }g(A_{i+1},A_{i}A_{j+1})\leq-1.$

Case 1: Let $u_{i}\in S_{1}$ and $v_{j}\in S_{2}$ with $j-i>1$. Then we have

$\displaystyle|(A_{i}A_{j})_{1}\cap S_{1}|$
$\displaystyle=\frac{1}{2}\bigg{(}|(A_{i}A_{j})_{2}|-f(A_{j},A_{i}A_{j+1})\bigg{)}$
$\displaystyle\geq\frac{1}{2}\bigg{(}(j-i-1)-(-1)\bigg{)}$
$\displaystyle=\frac{1}{2}(j-i),$

(note that $|(A_{i}A_{j})_{2}|=j-i-1$ when $i=0$) and

$\displaystyle|(A_{i+1}A_{j+1})_{2}\cap S_{2}|$
$\displaystyle=\frac{1}{2}\bigg{(}|(A_{i+1}A_{j+1})_{1}|-g(A_{i+1},A_{i}A_{j+1})\bigg{)}$
$\displaystyle\geq\frac{1}{2}\bigg{(}(j-i)-(-1)\bigg{)}$
$\displaystyle=\frac{1}{2}(j-i+1).$

Thus

$|A_{i}A_{j+1}\cap(S_{1}\cup S_{2})|\geq|(A_{i}A_{j})_{1}\cap
S_{1}|+|(A_{i+1}A_{j+1})_{2}\cap S_{2}|\geq j-i+\frac{1}{2}$

which implies

$|A_{i}A_{j+1}\cap(S_{1}\cup S_{2})|\geq j-i+1.$

On the other hand, $|A_{k}A_{k+1}\cap(S_{1}\cup S_{2})|\leq 1$ because of
(4.7) for any $i\leq k\leq j$, so that

$|A_{i}A_{j+1}\cap(S_{1}\cup S_{2})|\leq j-i+1.$

Therefore $|A_{i}A_{j+1}\cap(S_{1}\cup S_{2})|=j-i+1$ and we must require
$|A_{k}A_{k+1}\cap(S_{1}\cup S_{2})|=1$ for any $i\leq k\leq j$ for this to
hold.

However, if we take the smallest index $k\in[i+1,j]$ such that $v_{k}\in
S_{2}$, which exists by assumption, then $u_{k-1}\notin S_{1}$ and
$v_{k}\notin S_{2}$, which implies $|A_{k-1}A_{k}\cap(S_{1}\cup S_{2})|=0$, a
contradiction.

Case 2: Let $u_{i}\in S_{1}$ and $v_{j}\in S_{2}$ with $i>j$. Then similarly
we have

$|(A_{i}A_{j})_{1}\cap S_{1}|\geq\frac{1}{2}(n+j-i+1)$

and

$|(A_{i+1}A_{j+1})_{2}\cap S_{2}|\geq\frac{1}{2}(n+j-i+2).$

(Recall that by convention we loop back from $(n+1,n)$ to $(0,0)$ when we
consider the subpaths in this case.)

Therefore

$|A_{i}A_{j+1}\cap(S_{1}\cup S_{2})|\geq n+j-i+2.$

On the other hand, by (4.7) again, $|A_{k}A_{k+1}\cap(S_{1}\cup S_{2})|\leq 1$
for any $k\geq i$ or $k\leq j$, so

$|A_{i}A_{j+1}\cap(S_{1}\cup S_{2})|\leq n+j-i+2.$

Therefore $|A_{i}A_{j+1}\cap(S_{1}\cup S_{2})|=n+j-i+2$ and we must again
require $|A_{k}A_{k+1}\cap(S_{1}\cup S_{2})|=1$ for any $k\geq i$ or $k\leq j$
for this to hold. In particular,

$|A_{0}A_{2}\cap(S_{1}\cup S_{2})|=2$

which implies $u_{0},u_{1}\in S_{1}$ and $v_{1}\notin S_{2}$ by (4.7). Then
taking $u_{0}\in S_{1}$ and $v_{j}\in S_{2}$ with $j\geq 2$ we reduce to Case
1.

Therefore we conclude that for any $u_{i}\in S_{1},v_{j}\in S_{2}$:

$f(A_{j},A_{i}A_{j+1})\geq 0\quad\text{ or }\quad g(A_{i+1},A_{i}A_{j+1})\geq
0$

which implies $(S_{1},S_{2})$ is a compatible pair by Proposition 4.3. ∎

Finally, we recall a well-known fact that

######  Lemma 4.5.

The odd-indexed Fibonacci sequence satisfies the recurrence relation

$\displaystyle F_{2n+1}=3F_{2n-1}-F_{2n-3},\quad n>1$ (4.8)

with initial terms $F_{1}=1,F_{3}=2,F_{5}=5$.

Let $T_{n}$ be the set of all compatible pairs on $\mathcal{D}^{(n+1)\times
n}$.

######  Theorem 4.6.

We have the following recurrence relation for $n>1$:

$|T_{n}|=3|T_{n-1}|-|T_{n-2}|.$ (4.9)

In particular the number of compatible pairs in $\mathcal{D}^{(n+1)\times n}$
is $F_{2n+3}$.

###### Proof.

Define the following subsets of $T_{n}$ :

$O_{n}:=\\{(S_{1},S_{2})|u_{n}\notin S_{1},v_{n}\notin S_{2}\\},$
$U_{n}:=\\{(S_{1},S_{2})|u_{n}\in S_{1},v_{n}\notin S_{2}\\},$
$V_{n}:=\\{(S_{1},S_{2})|u_{n}\notin S_{1},v_{n}\in S_{2}\\}.$

Note that if $u_{n}\in S_{1},v_{n}\in S_{2}$, then $(S_{1},S_{2})$ cannot be a
compatible pair. Hence

$T_{n}=O_{n}\sqcup U_{n}\sqcup V_{n}.$

From Lemma 4.4, we see that $|O_{n}|=|U_{n}|=|T_{n-1}|$ and
$|V_{n}|=|O_{n-1}|+|V_{n-1}|$. Applying the two relations above, we get:

$\displaystyle|T_{n}|$ $\displaystyle=|O_{n}|+|U_{n}|+|V_{n}|$
$\displaystyle=|T_{n-1}|+|T_{n-1}|+(|O_{n-1}|+|V_{n-1}|)$
$\displaystyle=2|T_{n-1}|+(|T_{n-1}|-|U_{n-1}|)$
$\displaystyle=3|T_{n-1}|-|T_{n-2}|.$

Since the initial terms $|T_{0}|=F_{3}=2$ and $|T_{1}|=F_{5}=5$, by Lemma 4.5
the theorem is proven. ∎

##  5 Nondecreasing Dyck paths of length $2n$

In this section, we will count the number of the so-called _nondecreasing Dyck
paths_ of length $2n$. For further details, the reader is referred to [3].

######  Definition 5.1.

A _Dyck path of length $2n$_ is a discrete path consisting of diagonal
segments going from $(0,0)$ to $(2n,0)$ in the first quadrant
$\\{(x,y):x,y\in\mathbb{Z}_{\geq 0}\\}$, such that each step equals to a
vector $\vec{u}:=(1,1)$ or $\vec{v}:=(1,-1)$.

In particular a Dyck path $w$ of length $2n$ is equivalent to a sequence of
$2n$ vectors $\vec{w}_{1},\vec{w}_{2},...,\vec{w}_{2n}$ where $\vec{w}_{i}$
equals $\vec{u}$ or $\vec{v}$.

######  Remark 5.2.

The notion of “Dyck path” here has a different meaning compared to that in
Section 2.4. However, they are the same if we rotate the path defined here
counterclockwise by 45 degrees. Specifically, a Dyck path of length $2n$ is
equivalent to a normal Dyck path on $\mathcal{D}^{n\times n}$ in Section 2.4.

######  Definition 5.3.

Suppose $(x,y)=\vec{w}_{1}+...+\vec{w}_{i}$ for some $1\leq i<2n$ is a point
on the Dyck path $w$. It is a _peak_ if $\vec{w}_{i}=\vec{u}$ and
$\vec{w}_{i+1}=\vec{v}$. Conversely, it is a _valley_ if $\vec{w}_{i}=\vec{v}$
and $\vec{w}_{i+1}=\vec{u}$.

######  Definition 5.4.

We call $y$ the _altitude_ of a point $(x,y)$. A Dyck path of length $2n$ is
_nondecreasing_ if, viewed horizontally, the sequence of altitudes of the
valleys is nondecreasing.

######  Definition 5.5.

A _mountain_ of a nondecreasing Dyck path $w$ of length $2n$ is the subpath
from a valley to the next valley on the right, or from the last valley to the
endpoint $(2n,0)$. The _magnitude_ of a mountain is a pair of positive
integers $(d,e)$ such that $d,e\geq 1$ are the numbers of vectors $\vec{u}$
and $\vec{v}$ in the mountain’s representation.

######  Proposition 5.6.

A nondecreasing Dyck path can be viewed as a consecutive of $k$ mountains with
mountain magnitudes $(d_{i},e_{i})$ where $d_{i}\geq e_{i}$ respectively,
except the last mountain where we have $d_{k}\leq e_{k}$.

###### Proof.

The altitudes of the valleys are nondecreasing, implying $d_{i}\geq e_{i}$.
The altitude of the last valley is nonnegative so $d_{k}\leq e_{k}$. ∎

######  Example 5.7.

Figure 11 shows an example of a nondecreasing Dyck path whose length of 16
corresponds to consecutive mountains

$(d_{1},e_{1})=(2,2),\quad(d_{2},e_{2})=(2,2),\quad(d_{3},e_{3})=(3,1),\quad(d_{4},e_{4})=(1,3).$
(5.1)

Let $S_{n}$ be the set of all nondecreasing Dyck paths of length $2n$.

######  Definition 5.8.

We define a disjoint partition $A_{n},B_{n},C_{n}$ of $S_{n}$ as follows:

  * •

paths in $A_{n}$ have the last mountain in the form $(d_{k},e_{k})$ with
$d_{k}\geq 2$,

  * •

paths in $B_{n}$ have the last two mountain in the form
$(d_{k-1},e_{k-1}),(d_{k},e_{k})$ with $d_{k-1}=e_{k-1}$ and $d_{k}=1$,

  * •

paths in $C_{n}$ have the last two mountain in the form
$(d_{k-1},e_{k-1}),(d_{k},e_{k})$ with $d_{k-1}>e_{k-1}$ and $d_{k}=1$.

$d_{1}$$e_{1}$$d_{2}$$e_{2}$$d_{3}$$e_{3}$ Figure 11: A nondecreasing Dyck
path of length 16

######  Lemma 5.9.

We have the following recurrence relations:

$\displaystyle|A_{n}|$ $\displaystyle=|S_{n-1}|,$ (5.2) $\displaystyle|B_{n}|$
$\displaystyle=|S_{n-1}|,$ (5.3) $\displaystyle|C_{n}|$
$\displaystyle=|B_{n-1}|+|C_{n-1}|.$ (5.4)

###### Proof.

Consider the map $A_{n}\to S_{n-1}$ defined by

$\bigg{(}(d_{1},e_{1}),...,(d_{k},e_{k})\bigg{)}\mapsto\bigg{(}(d_{1},e_{1}),...,(d_{k}-1,e_{k}-1)\bigg{)}.$
(5.5)

It is clearly injective, with the inverse given by

$\bigg{(}(d_{1},e_{1}),...,(d_{k},e_{k})\bigg{)}\mapsto\bigg{(}(d_{1},e_{1}),...,(d_{k}+1,e_{k}+1)\bigg{)}$

which is well-defined because $d_{k}+1\geq 2$.

Next, the map $B_{n}\to S_{n-1}$ defined by

$\bigg{(}(d_{1},e_{1}),...,(d_{k-1},e_{k-1}),(1,e_{k})\bigg{)}\mapsto\bigg{(}(d_{1},e_{1}),...,(d_{k-1},d_{k-1}+e_{k}-1)\bigg{)}$
(5.6)

is clearly injective with the inverse given by

$\bigg{(}(d_{1},e_{1}),...,(d_{k-1},e_{k-1})\bigg{)}\mapsto\bigg{(}(d_{1},e_{1}),...,(d_{k-1},d_{k-1}),(1,e_{k-1}-d_{k-1}+1)\bigg{)}$

which is well-defined because $(d_{k-1},e_{k-1})$ is the last mountain, so
$e_{k-1}\geq d_{k-1}$ and

$e_{k-1}-d_{k-1}+1\geq 1.$

Finally consider the map $C_{n}\to B_{n-1}\sqcup C_{n-1}$ defined by

$\bigg{(}(d_{1},e_{1}),...,(d_{k-1},e_{k-1}),(1,e_{k})\bigg{)}\mapsto\bigg{(}(d_{1},e_{1}),...,(d_{k-1}-1,e_{k-1}),(1,e_{k}-1)\bigg{)}.$
(5.7)

Since $d_{k-1}>e_{k-1}\implies d_{k-1}-1\geq e_{k-1}$, it is clearly well-
defined and injective. The inverse is given by

$\bigg{(}(d_{1},e_{1}),...,(d_{k-1},e_{k-1}),(1,e_{k})\bigg{)}\mapsto\bigg{(}(d_{1},e_{1}),...,(d_{k-1}+1,e_{k-1}),(1,e_{k}+1)\bigg{)},$

which is well-defined because $d_{k-1}\geq e_{k-1}\implies d_{k-1}+1>e_{k-1}$.
∎

######  Theorem 5.10.

We have the following recurrence relation for $n>1$:

$|S_{n+1}|=3|S_{n}|-|S_{n-1}|.$ (5.8)

In particular the number of nondecreasing Dyck paths of length $2n$ is
$F_{2n-1}$.

###### Proof.

Applying Lemma 5.9, we have:

$\displaystyle|S_{n+1}|$ $\displaystyle=|A_{n+1}|+|B_{n+1}|+|C_{n+1}|$
$\displaystyle=|S_{n}|+|S_{n}|+(|B_{n}|+|C_{n}|)$
$\displaystyle=2|S_{n}|+(|S_{n}|-|A_{n}|)$ $\displaystyle=3|S_{n}|-|S_{n-1}|.$

We also have the initial conditions $|S_{2}|=F_{3}=2$ and $|S_{3}|=F_{5}=5$,
hence by Lemma 4.5 $|S_{n}|=F_{2n-1}$ as required. ∎

##  6 Bijective correspondences

In this section, we construct explicitly the one-to-one correspondences in
both directions among three combinatorial objects shown in Figure 1 including

  * •

perfect matchings on the snake graph $G_{T,\gamma_{n+3}}$ of annulus with 2
marked points,

  * •

compatible pairs on the maximal Dyck path $\mathcal{D}^{(n+1)\times n}$,

  * •

nondecreasing Dyck paths with a length of $2n+4$.

###  6.1 Perfect matchings and compatible pairs

Using the notation from Figure 9 and Figure 10, define

$\displaystyle\phi:\\{\text{perfect matching on }G_{T,\gamma_{n+3}}\\}$
$\displaystyle\to\\{\text{compatible pairs on }\mathcal{D}^{(n+1)\times n}\\}$
(6.1) $\displaystyle P$ $\displaystyle\mapsto(S_{1},S_{2})$

by the following rules:

  * •

$u_{0}\in S_{1}\iff A_{0}A_{1},B_{0}B_{1}\in P$

  * •

$u_{i}\in S_{1}\iff A_{2i}A_{2i+1},B_{2i}B_{2i+1}\in P,\forall
i\in\\{1,2,...,n\\}$

  * •

$v_{i}\in S_{2}\iff A_{2i-1}A_{2i},B_{2i-1}B_{2i}\in P,\forall
i\in\\{1,2,...,n\\}$

######  Example 6.1.

When $n=6$, consider the following perfect matching on $G_{T,\gamma_{9}}$,

$\displaystyle P=$
$\displaystyle\\{A_{0}A_{1},B_{0}B_{1},A_{2}B_{2},A_{3}B_{3},A_{4}A_{5},B_{4}B_{5},A_{6}B_{6},$
(6.2) $\displaystyle
A_{7}B_{7},A_{8}B_{8},A_{9}A_{10},B_{9}B_{10},A_{11}A_{12},B_{11}B_{12},A_{13}B_{13}\\}$

(see Figure 9). It responds to the compatible pair $(S_{1},S_{2})$ on
$\mathcal{D}^{7\times 6}$ where

$S_{1}=\\{u_{0},u_{2}\\},\quad\quad S_{2}=\\{v_{5},v_{6}\\}$ (6.3)

(see Figure 10) with the correspondence highlighted with the same colors on
both figures.

######  Theorem 6.2.

The map $\phi$ gives a one-to-one correspondence between perfect matchings on
$G_{T,\gamma_{n+3}}$ and compatible pairs on $\mathcal{D}^{(n+1)\times n}$.

To prove the theorem, we first give the following lemma.

######  Lemma 6.3.

The map $\phi$ is well-defined.

###### Proof.

If $u_{i}\in S_{1}$ then $A_{2i}A_{2i+1},B_{2i}B_{2i+1}\in P$. Thus by
definition of a perfect matching,

  * •

$A_{2i-1}A_{2i},B_{2i-1}B_{2i}\notin P\implies v_{i}\notin S_{2}$,

  * •

$A_{2i+1}A_{2i+2},B_{2i+1}B_{2i+2}\notin P\implies v_{i+1}\notin S_{2}$.

Therefore,

$\\{j-i|u_{i}\in S_{1},v_{j}\in S_{2}\\}\cap\\{0,1\\}=\emptyset$

which implies that $(S_{1},S_{2})$ is a compatible pair on
$\mathcal{D}^{(n+1)\times n}$ by Lemma 4.4. ∎

Note that the rules of $\phi$ are defined on both directions, so we also
obtain the inverse map $\phi^{-1}$ by construction. Note that the vertical
edges on $P$ are uniquely determined by the horizontal edges.

######  Example 6.4.

We consider again Example 6.1, with the horizontal edges given by

$\\{A_{0}A_{1},B_{0}B_{1},A_{4}A_{5},B_{4}B_{5},A_{9}A_{10},B_{9}B_{10},A_{11}A_{12},B_{11}B_{12}\\}\subset
P$ (6.4)

corresponding to the compatible pair
$(S_{1},S_{2})=(\\{u_{0},u_{2}\\},\\{v_{5},v_{6}\\})$. The vertical edges

$\\{A_{2}B_{2},A_{3}B_{3},A_{6}B_{6},A_{7}B_{7},A_{8}B_{8},A_{13}B_{13}\\}\subset
P$ (6.5)

is determined uniquely by the horizontal edges of $P$.

Next, we show that $\phi$ is injective by proving the following lemma.

######  Lemma 6.5.

The inverse map $\phi^{-1}$ is well-defined.

###### Proof.

We need to prove that if $P$ is a subgraph of $G_{T,\gamma_{n+3}}$
corresponding to a compatible pair $(S_{1},S_{2})$ by (6.1), then $P$ is a
perfect matching. By the observation above, this is equivalent to showing that
every vertex belongs to at most one horizontal edge.

  * •

If $A_{2i-1}A_{2i},B_{2i-1}B_{2i}\in P$, then $v_{i}\in S_{2}$, so,

$u_{i-1},u_{i}\notin S_{1}\implies
A_{2i-2}A_{2i-1},B_{2i-2}B_{2i-1},A_{2i}A_{2i+1},B_{2i}B_{2i+1}\notin P.$

  * •

If $A_{2i}A_{2i+1},B_{2i}B_{2i+1}\in P$, then $u_{i}\in S_{1}$, so,

$u_{v_{i}},v_{i+1}\notin S_{2}\implies
A_{2i-1}A_{2i},B_{2i-1}B_{2i},A_{2i+1}A_{2i+2},B_{2i+1}B_{2i+2}\notin P.$

Therefore, the vertices $A_{2i},B_{2i},A_{2i+1},B_{2i+1}$ belong to at most
one horizontal edge. ∎

###### Proof of Theorem.

By the lemmas, the map $\phi$ is injective. Since the cardinalities

$\displaystyle F_{2n+3}$ $\displaystyle=\text{ number of perfect matching on
}G_{T,\gamma_{n+3}}$ $\displaystyle=\text{ number of compatible pair on
}\mathcal{D}^{(n+1)\times n}$

are the same by Theorem 3.9 and Theorem 4.6, the map $\phi$ gives a one-to-one
correspondence with inverse $\phi^{-1}$. ∎

###  6.2 Compatible pairs and nondecreasing Dyck paths

Using the notation from Section 4 and Section 5, we construct the map

$\theta:\\{\text{compatible pair on }\mathcal{D}^{(n+1)\times
n}\\}\to\\{\text{nondecreasing Dyck path of length }2n+4\\}$ (6.6)

in four steps as follows.

  * Step 1:

A compatible pair on $\mathcal{D}^{(n+1)\times n}$ is equivalent to a sequence
of $n+1$ letters from $\\{O,U,V\\}$ by the following rules:

    * –

if $u_{0}\in S_{1}$, then the first letter is $U$, otherwise, the first letter
is $O$,

while for $1\leq i\leq n$,

    * –

if $u_{i}\notin S_{1},v_{i}\notin S_{2}$, then the $i^{th}$ letter is $O$,

    * –

if $u_{i}\in S_{1},v_{i}\notin S_{2}$, then the $i^{th}$ letter is $U$,

    * –

if $u_{i}\notin S_{1},v_{i}\in S_{2}$, then the $i^{th}$ letter is $V$.

Note that the sequence is well-defined because we cannot have $u_{i}\in S_{1}$
and $v_{i}\in S_{2}$ simultaneously on a compatible pair. Moreover, if
$u_{i}\in S_{1}$ then $v_{i+1}\notin S_{2}$, which means that the letter $U$
cannot be followed by the letter $V$.

  * Step 2:

We can always divide a sequence of letters into blocks of the form

$[U,...,U,O,V,...,V]$

(except for the last block, it can be empty or contain only a sequence of
$U$’s) such that

    * –

each block contains exactly one letter $O$,

    * –

there is only a consecutive number of $U$’s (maybe zero) before the letter
$O$,

    * –

there is only a consecutive number of $V$’s (maybe zero) after the letter $O$.

Suppose the number of letter $O$ is $k$, then there are $k+1$ blocks. For
$1\leq i\leq k$, let

    * –

$a_{i}\geq 0$ be the number of letters $U$ in the $i^{th}$ block,

    * –

$b_{i}\geq 0$ be the number of letters $V$ in the $i^{th}$ block.

  * Step 3:

Then we construct $k+1$ mountains, where for $1\leq i\leq k$, the $i^{th}$
mountain has magnitude

$(d_{i},e_{i}):=(a_{i}+b_{i}+1,a_{i}+1),$

while the last mountain has magnitude

$(d_{k+1},e_{k+1}):=\left(n+2-\sum_{i=1}^{k}(a_{i}+b_{i}+1),n+2-\sum_{i=1}^{k}(a_{i}+1)\right).$
(6.7)

  * Step 4:

Connect these $k+1$ mountains together, we get a nondecreasing Dyck path of
length $2n+4$.

######  Theorem 6.6.

The map $\theta$ gives a one-to-one correspondence between the compatible
pairs on $\mathcal{D}^{(n+1)\times n}$ and nondecreasing Dyck paths of length
$2n+4$.

######  Example 6.7.

When $n=6$, $(S_{1},S_{2})=(\\{u_{0},u_{2}\\},\\{v_{5},v_{6}\\})$ is a
compatible pair on $\mathcal{D}^{7\times 6}$, see Figure 10. This compatible
pair is equivalent to the sequence of 7 letters

$(U,O,U,O,O,V,V).$

We divide it into four blocks

$[U,O],\quad[U,O]\quad[O,V,V],\quad[].$

These blocks correspond to the mountains with magnitudes $(2,2),(2,2),(3,1)$,
while the last mountain has magnitude $(1,3)$, see Figure 11.

To prove the theorem, we have the following lemmas.

######  Lemma 6.8.

The map $\theta$ is well-defined.

###### Proof.

The corresponding Dyck path is nondecreasing because for any $1\leq i\leq k$,

$d_{i}=a_{i}+b_{i}+1\geq a_{i}+1=e_{i}.$

Furthermore, the corresponding Dyck path has a length of $2n+4$ because

$\sum_{i=1}^{k+1}d_{i}=\sum_{i=1}^{k+1}e_{i}=n+2.$

∎

The inverse map $\theta^{-1}$ is determined by reversing the steps of the map
$\theta$. From a nondecreasing Dyck path with $k+1$ mountains $(d_{i},e_{i})$
of length $2n+4$, we have

$a_{i}=e_{i}-1,\quad\quad b_{i}=d_{i}-e_{i}$

for any $1\leq i\leq k$. Next, we construct $k$ blocks ($1\leq i\leq k$)

$[\;\;\underbrace{U,...,U}_{a_{i}}\;,O,\;\underbrace{V,...,V}_{b_{i}}\;\;]$

while the last block just includes $d_{k+1}-1$ letters $U$. After that, we get
a sequence of $d_{1}+d_{2}+...+d_{k}+(d_{k+1}-1)=n+1$ letters. Then there is a
compatible pair $(S_{1},S_{2})$ that is equivalent to this sequence by the
correspondence in Step 1 above.

######  Lemma 6.9.

The map $\theta^{-1}$ is well-defined.

###### Proof.

Note that the first letter in the sequence is $O$ or $U$. Moreover, by the way
of connecting the blocks, there is no letter $U$ followed by a letter $V$. So
the sequence is indeed induced from a compatible pair. ∎

###### Proof of Theorem.

By the lemmas, the map $\theta$ is injective. Since the cardinalities

$\displaystyle F_{2k+3}$ $\displaystyle=\text{number of compatible pair on
}\mathcal{D}^{(n+1)\times n}$ $\displaystyle=\text{number of nondecreasing
Dyck path of length }2n+4$

are the same by Theorem 4.6 and Theorem 5.10, the map $\theta$ gives a one-to-
one correspondence with inverse $\theta^{-1}$. ∎

###  6.3 Perfect matchings and nondecreasing Dyck paths

The map

$\psi:\\{\text{perfect matching on
}G_{T,\gamma_{n+3}}\\}\to\\{\text{nondecreasing Dyck path of length }2n+4\\}$
(6.8)

can be expressed as a composition $\psi=\theta\circ\phi$. However, to make it
explicit, we construct it directly instead of using composition. The
construction is similar to that of the map $\theta$, by modifying step 1.

  * Step 1’:

A perfect matching on the snake graph $G_{T,\gamma_{n+3}}$ is equivalent to a
sequence of $n+1$ letters from $\\{O,U,V\\}$ by the following rules:

    * –

iIf $A_{0}A_{1},B_{0}B_{1}\in P$, then the first letter is $U$, otherwise, the
first letter is $O$,

while for $1\leq i\leq n$,

    * –

if $A_{2i}B_{2i}\in P$, then the $i^{th}$ letter is $O$,

    * –

if $A_{2i}A_{2i+1},B_{2i}B_{2i+1}\in P$, then the $i^{th}$ letter is $U$,

    * –

if $A_{2i-1}A_{2i},B_{2i-1}B_{2i}\in P$, then the $i^{th}$ letter is $V$.

Similar to the arguments given in Section 6.2, $\psi$ is well-defined and
gives a one-to-one correspondence between the perfect matchings on the snake
graph $G_{T,\gamma_{n+3}}$ associated with annulus with two marked points, and
the nondecreasing Dyck paths of length $2n+4$.

## References

  * [1] M. Cheung, M. Gross, G. Muller, G. Musiker, D. Rupel, S. Stella, and H. Williams.  The greedy basis equals the theta basis: A rank two haiku.  Journal of Combinatorial Theory, Series A, 145:150–171, 2017.
  * [2] B. Davison and T. Mandel.  Strong positivity for quantum theta bases of quantum cluster algebras.  Inventiones mathematicae, 226:725–843, 2021.
  * [3] E. Deutsch and H. Prodinger.  A bijection between directed column-convex polyominoes and ordered trees of height at most three.  Theoretical computer science, 307(2):319–325, 2003.
  * [4] S. Fomin, M. Shapiro, and D. Thurston.  Cluster algebras and triangulated surfaces. part i: Cluster complexes.  Acta Mathematica, 201(1):83–146, 2008.
  * [5] S. Fomin and A. Zelevinsky.  Cluster algebras i: foundations.  Journal of the American Mathematical Society, 15(2):497–529, 2002\.
  * [6] S. Fomin and A. Zelevinsky.  $y$-systems and generalized associahedra.  Annal of Mathematics, 158:977–1018, 2003.
  * [7] S. Fomin and A. Zelevinsky.  Cluster algebras iv: coefficients.  Compositio Mathematica, 143(1):112–164, 2007.
  * [8] M. Gross, P. Hacking, S. Keel, and M. Kontsevich.  Canonical bases for cluster algebras.  Journal of American Mathematical Society, 31(2):497–608, 2018.
  * [9] R. Kedem.  $q$-systems as cluster algebra.  Journal of Physics A: Mathematical and Theoretical, 41(19):194011, 2008.
  * [10] K. Lee, L. Li, and A. Zelevinsky.  Greedy elements in rank 2 cluster algebras.  Selecta Mathematica, 20(1):57–82, 2014.
  * [11] K. Lee and R. Schiffler.  Positivity for cluster algebras of rank 3.  Publications of the Research Institute for Mathematical Sciences, 49(3):601–649, 2013.
  * [12] G. Musiker and R. Schiffler.  Cluster expansion formulas and perfect matchings.  Journal of Algebraic Combinatorics, 32(2):187–209, 2010.
  * [13] G. Musiker, R. Schiffler, and L. Williams.  Positivity for cluster algebras from surfaces.  Advances in Mathematics, 227(6):2241–2308, 2011.
  * [14] T. Nakanishi.  Periodicities in cluster algebras and dilogarithm identities.  “Representations of algebras and related topics”, Proceedings to ICRA XIV, Tokyo, pages 407–444, 2011.
  * [15] R. Schiffler.  On cluster algebras arising from unpunctured surfaces ii.  Advances in Mathematics, 223(6):1885–1923, 2010.
  * [16] P. Sherman and A. Zelevinsky.  Positivity and canonical bases in rank 2 cluster algebras of finite and affine types.  arXiv preprint math/0307082, 2003.
  * [17] L. Williams.  Cluster algebras: an introduction.  Bulletin of the American Mathematical Society, 51(1):1–26, 2014\.
  * [18] A. Zelevinsky.  What is a cluster algebra.  Notices of the AMS, 54(11):1494–1495, 2007.