Fully Packed Loop configurations in a triangle
and Littlewood Richardson coefficients

Philippe Nadeau

Fakultät für Mathematik, Universität Wien, Nordbergstraße 15, A-1090 Wien, AUSTRIA.

**Abstract.** We are interested in Fully Packed Loops in a triangle (TFPLs), as introduced by Caselli at al. and studied by Thapper. We show that for Fully Packed Loops with a fixed link pattern (refined FPL), there exist linear recurrence relations with coefficients computed from TFPL configurations. We then give constraints and enumeration results for certain classes of TFPL configurations. For special boundary conditions, we show that TFPLs are counted by the famous Littlewood Richardson coefficients.

**Résumé.** Nous nous intéressons aux configurations de “Fully Packed Loops” dans un triangle (TFPL), introduites par Caselli et al. et étudiées par Thapper. Nous montrons que pour les Fully Packed Loops avec un couplage donné, il existe des relations de récurrence linéaires dont les coefficients sont calculés à partir de certains TFPLs. Nous donnons ensuite des contraintes et des résultats énumératifs pour certaines familles de TFPLs. Pour certaines conditions au bord, nous montrons que le nombre de TFPL est donné par les coefficients de Littlewood Richardson.

**Keywords:** Razumov Stroganov conjecture, Fully Packed Loop, Littlewood-Richardson coefficients

# 1 Introduction

The recently proved Razumov-Stroganov correspondence [RS04, CS10] states that the ground state components $\psi_\pi$ of the so called *O(1) loop model* are equal to the refined Fully Packed Loop number $A_\pi$, where $\pi$ is a link pattern (see Section 1.1 for definitions on FPLs). Although certain general expressions have been developed for the $\psi_\pi$'s from which results could be obtained (see [ZJ] and references therein), explicit formulas for the $A_\pi$'s are known only in certain very special cases of link patterns (cf. [ZJ06]).

The purpose of this article is to study the numbers $A_\pi$ thanks to the decomposition found in [CKLN06] which involves the counting of FPLs in a triangle (TFPLs). More recently, the paper [Tha07] developed new ideas and conjectures concerning these TFPLs, and was the original motivation for the present paper. We will actually first prove a conjecture of [Tha07] about certain recurrence relations for the numbers $A_\pi$ that involve coefficients computed from TFPLs. Then we will start the study of TFPL configurations themselves, gathering several of their properties, the most striking being Theorem 4.3 which shows that a certain subclass of TFPLs turns out to be enumerated by Littlewood Richardson coefficients.

This work is thus a starting point in the study of TFPLs. Our results will show that these are not only interesting by themselves, but are also a promising tool in order to obtain explicit recurrences or expressions for the refined FPL numbers $A_\pi$.
In the rest of this section we define FPL configurations, and notions related to words and partitions. In Section 2 FPLs in a triangle are defined, and we prove Theorem 2.5 about linear recurrence relations for the numbers $A_π$. In Section 3, we prove certain properties and constraints of TFPL numbers, giving in particular a very nice new proof of Theorem 3.1 from [CKLN06]. Finally, we prove Theorem 4.3 mentioned above in Section 4.

## 1.1 Fully Packed Loop configurations

We fix a positive integer $n$, and let $G_n$ be the square grid with $n^2$ vertices; we impose also periodic boundary conditions on $G_n$, which means that we select every other external edge on the grid, starting by convention with the topmost on the left side, and we will number these $2n$ external edges counterclockwise. A Fully Packed Loop (FPL) configuration $F$ of size $n$ is defined as a subgraph of $G_n$ such that each vertex of $G_n$ is incident to two edges of $F$. An example of configuration is given on Figure 1 (left). We let $A_n$ be the total number of FPL configurations on the grid $G_n$. It is well known that FPL configurations are in bijection with alternating sign matrices (cf. [Pro01] for instance), and thus we have the famous enumeration proved independently by Zeilberger [Zei96] and Kuperberg [Kup96]:

$$A_n = \prod_{i=0}^{n-1} \frac{(3i + 1)!}{(n + i)!}$$

<figure><img src="image_1.png" /><figcaption>Fig. 1: A FPL configuration of size 7.</figcaption></figure>

Define a link pattern $\pi$ of size $n$ as a matching on $\{1, \dots, 2n\}$ of $n$ pairwise noncrossing pairs $\{i, j\}$ between these $2n$ points, which means that there are no integers $i < j < k < l$ such that $\{i, k\}$ and $\{j, l\}$ are both in $\pi$. A FPL configuration on $G_n$ naturally defines nonintersecting paths between its external edges, so we can define the link pattern $\pi(F)$ as the set of pairs $\{i, j\}$ where $i, j$ label external edges which are the extremities of the same path in $F$. For instance, if $F$ is the configuration of Figure 1, then $\pi(F)$ is the link pattern shown on its right, represented as a chord diagram.

**Definition 1.1 ($A_\pi$ and $A_\pi$)** Let $\pi$ be a link pattern. The set $A_\pi$ is defined as the set of all FPL configurations $F$ of size $n$ such that $\pi(F) = \pi$. We also let $A_\pi := |A_\pi|$.
**Wieland's theorem:** Given a link pattern $\pi$, consider the rotated link pattern $r(\pi)$ defined by $\{i, j\} \in r(\pi)$ if and only if $\{i-1, j-1\} \in \pi$, where indices are taken modulo $2n$. A beautiful result of Wieland [Wie00] states that $A_{\pi} = A_{r(\pi)}$, by giving a bijection between $A_{\pi}$ and $A_{r(\pi)}$.

**Nested arches and $A_{\pi}(m)$:** Given a link pattern $\pi$ on $\{1, \dots, 2n\}$, and an integer $m \ge 0$, let us define $\pi \cup m$ as the link pattern on $\{1, \dots, 2(n+m)\}$ given by the "nested" pairs $\{i, 2n+2m+1-i\}$ for $i=1 \dots m$, and the pairs $\{i+m, j+m\}$ for each $\{i, j\} \in \pi$. We will want to study the numbers $A_{\pi \cup m}$ as functions of $m$, so we introduce the notation $A_{\pi}(m) := A_{\pi \cup m}$.

## 1.2 Words, Ferrers diagrams, link patterns

We consider finite words on the alphabet with two letters 0 and 1, simply named words. For $u$ a word, we let $|u|_0$ denote its number of zeros, $|u|_1$ its number of ones, and $|u| = |u|_0 + |u|_1$ its total length.

**Proposition 1.2** Given nonnegative integers $k, \ell$, there is a bijection between words $\sigma$ such that $|\sigma|_0 = k$ and $|\sigma|_1 = \ell$, and Ferrers diagrams fitting in the rectangle with $k$ rows and $\ell$ columns.

**Proof:** This is very standard. Given such a word $\sigma = \sigma_1 \cdots \sigma_{k+\ell}$, construct a path on the square lattice by drawing a North step when $\sigma_i = 0$ and an East step when $\sigma_i = 1$, for $i$ from 1 to $k+\ell$. Then complete the picture by drawing a line up from the starting point, and a line left of the ending point; the resulting region enclosed in the wanted Ferrers diagram; see Figure 2 for an example. $\square$

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** Bijection between words and Ferrers diagrams.</figcaption></figure>

Since we do not want to introduce too much notation, we use the bijection of Proposition 1.2 to identify words and their corresponding Ferrers diagrams in the rest of the article. The conjugate $\sigma^*$ of $\sigma = \sigma_1 \cdots \sigma_n$ is the word of length $n$ defined by $\sigma_i^* := 1 - \sigma_{n+1-i}$. Clearly we have $(\sigma^*)^* = \sigma$. The degree of $\sigma$ is the number of indices $i < j$ such that $(\sigma_i, \sigma_j) = (1, 0)$, and is noted $d(\sigma)$; it is the number of boxes in the Ferrers diagram representation. For instance we have $d(\sigma) = 9$ for the example of Figure 2.

Suppose that $\sigma, \tau$ are words that verify $|\sigma|_0 = |\tau|_0$ and $|\sigma|_1 = |\tau|_1$, so that they form Ferrers diagrams included in a common rectangle by Proposition 1.2. We define $\sigma \le \tau$ if $\sigma$ is included in $\tau$ in the diagram representation: this is equivalent to $\sigma_{\le i} \le \tau_{\le i}$ for all indices $i$, where $\sigma_{\le i} = \sum_{j \le i} \sigma_j$. If $\sigma \le \tau$, we define the skew shape $\tau/\sigma$ as the set of boxes that are in $\tau$ but not in $\sigma$; if there are no two boxes in the same column, then $\tau/\sigma$ is a horizontal strip, and we write $\sigma \to \tau$. We define a semistandard Young tableau of shape $\sigma$, and length $N \ge 0$ to be a sequence $(\sigma_i)_{i=0 \dots N}$ of words such that $\sigma_0 = 0 \to \sigma_1 \dots \to \sigma_N = \sigma$, where 0 is the empty partition. This is equivalent to the standard definition, i.e. a filling of the boxes of the diagram $\sigma$ by positive integers not bigger than $N$, nondecreasing across each row from left to right and increasing down each column.
Suppose that $u$ is a box in the diagram $\sigma$, which is in the $k$th row from the top and $\ell$th column from the left. The content $c(u)$ of $u$ is defined as $\ell - k$, while its hook-length $h(u)$ is defined as the number of boxes in $\sigma$ which are below $u$ and in the same column, or right of $u$ and in the same row ($u$ itself being counted just once); define also $H_{\sigma} = \prod h(u)$ where the product is over all cells $u$ of the diagram $\sigma$. We have then the hook content formula, which states that the number of semistandard Young tableaux of shape $\sigma$ and length $N \ge 0$ is given by the following polynomial in $N$ with leading term $\frac{1}{H_{\sigma}} N^{d(\sigma)}$:

$$SSYT(\sigma, N) := \frac{1}{H_{\sigma}} \prod_{u \in \sigma} (N + c(u)) \qquad (1)$$

**Link patterns and the set $D_n$:** A link pattern $\pi$ on $\{1, \dots, 2n\}$ can also be considered as a word of length $2n$, where for each pair $\{i, j\}$ in $\pi$ we set $\pi_i = 0$ and $\pi_j = 1$. Such words $\pi$ form the following subset of $\{0, 1\}^{2n}$:

**Definition 1.3 ($D_n$)** We denote by $D_n$ the set of words $\sigma$ of length $2n$, such that $|\sigma|_0 = |\sigma|_1 = n$, and each prefix $u$ of $\sigma$ verifies $|u|_0 \ge |u|_1$.

These are known as Dyck words, and counted by the Catalan number $|D_n| = C_n := \frac{1}{n+1} \binom{2n}{n}$. Note that $(D_n, \le)$ is a poset, with smallest element $0_n := 0^n 1^n$ and greatest element $1_n := (01)^n$. We will identify link patterns with words in $D_n$.

<figure><img src="image_3.png" /><figcaption>Fig. 3: The word 0010100111 $\in D_5$ as a diagram and a link pattern.</figcaption></figure>

# 2 FPL in a triangle and linear recurrence relations

In all this section $n$ will be a fixed positive integer.

## 2.1 FPL configurations in a triangle

We will here recall briefly the triangle arising in [CKLN06, Tha07], and refer to these works for more detail; we also advise the reader to look at Figure 4 while reading the definitions. We define the triangle $T^n$ as the subset of $\mathbb{Z}^2$ consisting of the points of coordinates $(x, y)$ which verify $x \ge y \ge 0$ and $x + y \le 4n - 2$, with $2n$ external edges below all vertices $(2i, 0)$ for $i = 0, \dots, 2n - 1$, and horizontal edges between $(i, i)$ and $(i+1, i)$, and between $(4n - 2 - i - 1, i)$ and $(4n - 2 - i, i)$ for $i = 0, \dots, 2n - 2$, see left of Figure 4, where the edges in bold are the forced edges just described.

We consider the triangle with some extra conditions given by $\sigma, \tau$ words in $D_n$: if $\sigma = \sigma_1 \dots \sigma_{2n}$, we add a vertical edge below $(i-1, i-1)$ for each $i$ such that $\sigma_i = 0$, while if $\tau = \tau_1 \dots \tau_{2n}$, we add
a vertical edge below $(2n - 2 + i, 2n - i)$ for each $i$ such that $\tau_i = 1$. Note that $\sigma$ and $\tau$ have to be interpreted differently than in [Tha07].

**Definition 2.1** A FPL configuration $f$ in a triangle (TFPL) with boundary conditions $\sigma, \pi, \tau$ in $D_n$ is a graph on $T^n$, where vertical edges on the left and right boundary are given by $\sigma$ and $\tau$ as above. All vertices (except on the left and right boundaries) are imposed to be of degree 2, and we have furthermore (1) the 2n bottom external edges must be linked by paths in $T^n$ according to the link pattern $\pi$, and (2) the paths starting on the left boundary must end on the right boundary; cf Figure 4 for an example. The set of these TFPLs is denoted $\mathcal{T}_{\sigma, \tau}^{\pi}$, and we define $t_{\sigma, \tau}^{\pi}$ as the cardinality $|\mathcal{T}_{\sigma, \tau}^{\pi}|$.

<figure><img src="image_4.png" /><figcaption>Fig. 4: Boundary conditions for FPL in a triangle.</figcaption></figure>

## 2.2 Linear recurrences for refined FPL numbers

The link between FPLs and TFPLs is given by the following formula from [CKLN06]: for $m \ge 0$,

$$A_{\pi}(m) = \sum_{\sigma, \tau \in \mathcal{D}_n} \mathrm{SSYT}(\sigma, n) \cdot t_{\sigma, \tau}^{\pi} \cdot \mathrm{SSYT}(\tau^*, m - 2n + 1), \quad (2)$$

Following Thapper [Tha07], we now consider endomorphisms of $\mathcal{CD}_n$, the vector space of formal complex linear combinations of elements of $D_n$. We will write such endomorphisms $g$ as matrices in the canonical basis $D_n$, so that, if $\sigma, \tau \in D_n$, we denote by $g_{\sigma\tau}$ the coefficient of $\sigma$ in the expansion of $g(\tau)$. Then we define $\mathbf{b}$ by $\mathbf{b}_{\sigma\tau} = 1$ if $\sigma \to \tau$, and $\mathbf{b}_{\sigma\tau} = 0$ otherwise. We define $\tilde{\mathbf{b}}$ by $\tilde{\mathbf{b}}_{\sigma\tau} = 1$ if $\tau^* \to \sigma^*$ and $\tilde{\mathbf{b}}_{\sigma\tau} = 1$ otherwise. Given $\pi \in D_n$, we also let $(\mathbf{t}^{\pi})_{\sigma\tau} = t_{\sigma, \tau}^{\pi}$. By definition of semistandard Young Tableaux, we have $\mathrm{SSYT}(\sigma, n) = (\mathbf{b}^n)_{0_n\sigma}$ and $\mathrm{SSYT}(\tau^*, m - 2n + 1) = (\tilde{\mathbf{b}}^{m-2n+1})_{\tau 0_n}$. So we can rewrite Equation (2) as

$$A_{\pi}(m) = (\mathbf{b}^n \mathbf{t}^{\pi} \tilde{\mathbf{b}}^{m-2n+1})_{0_n 0_n} \quad (3)$$

We have then the following Proposition conjectured by Thapper [Tha07, Conjecture 3.4]:

**Theorem 2.2**

$$\mathbf{b}\mathbf{t}^{\pi} = \mathbf{t}^{\pi}\tilde{\mathbf{b}} \quad \text{for all } \pi \in \mathcal{D}_n. \quad (4)$$
**Proof (Sketch):** As shown by Thapper, the coefficients on the left and right side enumerate some configurations in “extended” triangles. By studying Wieland’s rotation (cf. Section 1.1), it is possible to show that this can be applied in these extended triangles, and that it indeed exchanges bijectively left and right extended triangles. Note that one has to apply either $H_0$ or $H_1$ in Wieland’s original notation in [Wie00], and not the composition $H_0 \circ H_1$: this shifts the link pattern $\pi$, and one has to check that the boundary conditions $\sigma$ and $\tau$ are indeed preserved. $\square$

Now we can apply the commutation relation (4) repeatedly in Equation (3), and obtain $A_\pi(m) = (\mathbf{b}^{m-n+1}\mathbf{t}^\pi)_{0_n0_n}$ which can be expanded as $\sum_{\sigma \in \mathcal{D}_n} \text{SSYT}(\sigma, m-n+1) \cdot t_{\sigma, 0_n}^\pi$; this involves only TFPLs with $\tau = 0_n$, so if we introduce $\mathbf{t}$ as $(\mathbf{t})_{\sigma\pi} = t_{\sigma, 0_n}^\pi$ we get:

**Proposition 2.3** For all integers $m \ge 0$, we have $A_\pi(m) = (\mathbf{b}^{m-n+1}\mathbf{t})_{0_n\pi}$.

We can now use the beautiful idea of Thapper: by Theorem 3.1, the coefficients $t_{\sigma, 0_n}^\pi$ of $\mathbf{t}$ are integers, equal to 0 unless $\sigma \le \pi$, and such that $t_{\pi, 0_n}^\pi = 1$. This means that, if we give the basis $\mathcal{D}_n$ a linear order extending $\le$, then the matrix of $\mathbf{t}$ is upper triangular with ones on its diagonal. It is thus invertible, with its inverse $\mathbf{t}^{-1}$ being also triangular with ones on its diagonal, and with integer entries. We can thus define:

**Definition 2.4** We define the matrix $\mathbf{c}$ by $\mathbf{c} := \mathbf{t}^{-1}\mathbf{b}\mathbf{t}$.

We can now state the main result of this section, conjectured by Thapper [Tha07, Proposition 3.5]:

**Theorem 2.5** For any $\pi \in \mathcal{D}_n$, we have the polynomial identity:

$$A_{\pi}(m) = \sum_{\alpha \in \mathcal{D}_n} \mathbf{c}_{\alpha\pi} A_{\alpha}(m-1)$$

**Proof:** By Proposition 2.3 and the definition of $\mathbf{c}$, we get for any $m$

$$A_{\pi}(m) = (\mathbf{b}^{m-n+1}\mathbf{t})_{0_n\pi} = (\mathbf{b}^{m-n}\mathbf{t}\mathbf{c})_{0_n\pi} = \sum_{\alpha \in \mathcal{D}_n} (\mathbf{b}^{m-n}\mathbf{t})_{0_n\alpha} \mathbf{c}_{\alpha\pi},$$

from which the result follows, again by Proposition 2.3. $\square$

We remark that the coefficients $c_{\alpha\pi}$ are not the unique integers verifying Theorem 2.5. But first, we have a uniform definition for them. Second, there is evidence that they are “good” coefficients, based on data communicated to the author by J. Thapper: these numbers are quite small (they are between $-1$ and $2$ for $n=5$, while the supremum of $\mathbf{t}$ exceeds 80000), and we conjecture that they verify $c_{\alpha\pi} = c_{\alpha^*\pi^*}$, that $c_{\alpha\pi}$ only depends on the skew shape $\pi/\alpha$, and many other properties. It seems that there is hope that these coefficients have a direct combinatorial characterization.

# 3 Some properties of TFPL configurations

In this Section we will prove certain enumerative questions related to TFPL configurations. In particular we give a new proof of the following theorem, which was essential in Section 2.2:

**Theorem 3.1** Let $\sigma, \pi, \tau$ be in $\mathcal{D}_n$. Then $t_{\sigma, \tau}^\pi = 0$ unless $\sigma \le \pi$. Moreover, if $\sigma = \pi$, then $t_{\pi, 0_n}^\pi = 1$ and $t_{\pi, \tau}^\pi = 0$ for $\tau \ne 0_n$.

It was proved first in [CKLN06, Section 7] in a very technical way, while here our proof (see Section 3.2) is much shorter and illuminating.
## 3.1 Oriented TFPL configurations

The vertices of $\mathcal{T}_n$ can be partitioned in lines: for $i \in \{1, \dots, 2n\}$, we define $E_i$ as the vertices of $\mathcal{T}^n$ such that $x+y = 2i-2$, and for $i \in \{1, \dots, 2n-1\}$, we define $O_i$ as the vertices of $\mathcal{T}^n$ such that $x+y = 2i-1$. The case $n=3$ is given on Figure 5. Now let us suppose we have boundary configurations $\sigma, \tau, \pi$ on the triangle $\mathcal{T}_n$. We first define an orientation for all edges around the triangle as follows. On the left boundary, we orient edges to the right and upwards; on the right boundary, we orient them to the right and downwards; for the $2n$ vertical external edges on the bottom, we orient the one attached to $(2i-2, 0)$ upwards if $\pi_i = 0$, and downwards if $\pi_i = 1$, for $i \in \{1, \dots, 2n\}$. Now given a TFPL configuration $f$ in $\mathcal{T}_{\sigma, \tau}^{\pi}$, we now orient all remaining edges so that each vertex of degree 2 have one incoming edge and one outgoing edge. This condition determines clearly the orientation of edges in a path of $f$ joining external edges, and by convention we orient the closed paths of $f$ clockwise. In this way we associate to each configuration $f \in \mathcal{T}_{\sigma, \tau}^{\pi}$ an oriented configuration that we will denote by $\text{or}(f)$.

<figure><img src="image_5.png" /><figcaption>Fig. 5: Lines $E_i$ and $O_i$.</figcaption></figure>

## 3.2 Proof of Theorem 3.1

**Definition 3.2** ($\mathcal{N}_i(f)$ and $N_i(f)$) Let $\sigma, \tau, \pi$ be in $\mathcal{D}_n$, $f$ be a configuration in $\mathcal{T}_{\sigma, \tau}^{\pi}$, and $i$ be an integer in $\{1, \dots, 2n-1\}$. We define $\mathcal{N}_i(f)$ as the set of oriented edges in $\text{or}(f)$ which are directed from a vertex in $O_i$ to a vertex in $E_i$. We also define $N_i(f) = |\mathcal{N}_i(f)|$, and $N_0(f) = 0$ by convention.

These oriented edges are circled in the example of Figure 5, and we get $N_i(f) = 0, 1, 1, 1, 0$ for $i = 1, 2, 3, 4, 5$ respectively. We can now state the key lemma:

**Lemma 3.3** Let $\sigma, \tau, \pi$ be in $\mathcal{D}_n$, and $f$ a configuration in $\mathcal{T}_{\sigma, \tau}^{\pi}$. Then

$$N_i(f) - N_{i-1}(f) = \pi_i - \sigma_i, \quad \text{for } i = 1, \dots, 2n-1. \qquad (5)$$

**Proof:** We consider the oriented configuration $\text{or}(f)$. The $i$ vertices of $E_i$ have one incoming edge, except $(i-1, i-1)$ when $\sigma_i = 1$. If this incoming edge comes from $O_i$ it is an element of $\mathcal{N}_i(f)$; let $X_i(f)$ be the other incoming edges, and $x_i(f) := |X_i(f)|$. We have then

$$N_i(f) + x_i(f) + \sigma_i = i. \qquad (6)$$
Similarly, consider the $i-1$ vertices on the line $O_{i-1}$: each of them has exactly one outgoing edge, and if this edge goes to the line $E_{i-1}$ it is by definition in $N_{i-1}(f)$. We form the set $Y_i(f)$ with the other outgoing edges of $O_{i-1}$, and let $y_i(f) := |Y_i(f)|$. We obtain here

$$N_{i-1}(f) + y_i(f) = i - 1. \qquad (7)$$

Now the sets $Y_i(f)$ and $X_i(f)$ coincide except in the case $\pi_i = 0$, where there is an external edge incoming in $(2i - 2, 0) \in E_i$ (by definition of the orientation) and therefore belongs to $X_i$ and not to $Y_i$. Thus $x_i(f) = y_i(f) + (1 - \pi_i)$ and by injecting this in Equations (6) and (7) we deduce Equation (5). $\square$

We can now give the proof of the first half of Theorem 3.1. If we sum the relations (5) for $i$ going from 1 to $j$, then for any $j \in \{1, \dots, 2n\}$ we obtain $\pi_{\le j} - \sigma_{\le j} = N_j(f)$. Since this is nonnegative, this proves that $\sigma \le \pi$ (cf. Section 1.2), and we are done. The second part of Theorem 3.1 is much easier, see the end of Section 7 in [CKLN06].

## 3.3 Common prefixes and suffixes

We just showed that TFPLs exist only when $\sigma \le \pi$ (and $\tau \le \pi$ by symmetry), and that in case of equality $\sigma = \pi$ there is just one configuration, when $\tau = 0_n$. It is natural to ask what happens when $\sigma$ is smaller than $\pi$ but “close” to it, and one possible answer is the following:

**Theorem 3.4** Let $\pi, \sigma, \tau \in D_n$, and suppose that there exist words $u, \sigma', \pi', v$ such that $\sigma = u\sigma'v$ and $\pi = u\pi'v$ (concatenation of words). Let $a = |u|_0 + |v|_0$ and $b = |u|_1 + |v|_1$. Then $t_{\sigma, \tau}^{\pi} = 0$ unless $\tau$ is of the form $\tau = 0^a\tau'1^b$.

The proof is quite technical and will be omitted here. It involves a slight variant of de Gier’s lemma on fixed edges [dG05, Lemma 8], in which we make use of the oriented TFPL configurations of Section 3.1.

There is one special case emerging naturally in the proof, which is when $\pi' = 1^{n-b}0^{n-a}$; note that this means that $\pi/\sigma$ is a rotated diagram, i.e. a skew shape which is the (translated of) a Ferrers diagram after a half turn. In this case, each vertex of $T_n$ can be shown to be incident to at least one fixed edge, and another observation of de Gier can be used to show that the enumeration of $T_{\sigma, \tau}^{\pi}$ is then reduced to a tiling problem, whose solution in our case can be written under the form of a single determinant of size $\min(n-a, n-b)$. So if $\pi/\sigma$ is a row or a column of cells, we get a single binomial coefficient.

## 3.4 Extremal TFPL configurations

We recall that $d(\sigma)$ is the number of boxes in the Ferrers diagram of $\sigma$.

**Proposition 3.5** One has $t_{\sigma, \tau}^{\pi} = 0$ unless $d(\sigma) + d(\tau) \le d(\pi)$. Furthermore, for every $\pi \in D_n$ we have

$$\frac{1}{H_{\pi}} = \sum_{\substack{\sigma, \tau \in D_n \\ d(\sigma) + d(\tau) = d(\pi)}} t_{\sigma, \tau}^{\pi} \cdot \frac{1}{2^{d(\sigma)} H_{\sigma}} \cdot \frac{1}{2^{d(\tau)} H_{\tau}}. \qquad (8)$$

We reproduce the argument of [Tha07, Lemma 3.7] which is the first part of the proposition.

**Proof:** As Equation (2) shows, $A_{\pi}(m)$ is polynomial in $m$, and using Theorem 3.1 and (1), it is easy to deduce as in [CKLN06] that it is a polynomial with leading term $\frac{1}{H_{\pi}}m^{d(\pi)}$. Now using relation (4) and
assuming *m* is an even integer, we can get from (3) that $A_\pi(m) = (\mathbf{b}^{m/2}\mathbf{t}^\pi \tilde{\mathbf{b}}^{m/2-n+1})_{0_n 0_n}$, i.e.

$$ \sum_{\sigma, \tau \in D_n} \mathrm{SSYT}(\sigma, m/2) \cdot t_{\sigma, \tau}^{\pi} \cdot \mathrm{SSYT}(\tau^*, m/2 - n + 1). $$

This is also polynomial in *m*, and thus the coefficients of degree $> d(\pi)$ must vanish, which implies the first part of the proposition. The second part follows by taking the coefficient of degree $d(\pi)$ in this last expression, which is necessarily equal to $\frac{1}{H_\pi}m^{d(\pi)}$. $\square$

We will call extremal the TFPL configurations verifying $d(\sigma) + d(\tau) = d(\pi)$.

# 4 TFPL and Littlewood Richardson coefficients

In this section we will show that the coefficients $t_{\sigma, \tau}^{\pi}$ when $d(\sigma)+d(\tau) = d(\pi)$ are given by the Littlewood Richardson coefficients.

## 4.1 Littlewood Richardson coefficients and puzzles

We refer to [Sta99] for background on symmetric functions. Let $x = (x_1, x_2, \dots)$ be commuting in-determinates, and let $\Lambda(x)$ be the ring of symmetric functions in $x$. Schur functions $s_\lambda(x)$ ($\lambda$ a Ferrers diagram) form a basis of $\Lambda(x)$, and the Littlewood-Richardson (LR) coefficients $c_{\lambda, \mu}^{\nu}$ are defined as the coefficients in the expansion of their products $s_\mu(x)s_\nu(x) = \sum_\lambda c_{\mu, \nu}^{\lambda} s_\lambda(x)$. The LR coefficient $c_{\lambda, \mu}^{\nu}$ is 0 unless $\lambda \ge \mu, \nu$ and $d(\mu) + d(\nu) = d(\lambda)$. Schur functions can be defined combinatorially in terms of semistandard Young tableaux, and in this case it is clear that, under the specialization $x_i = 1$ for $i = 1 \dots N$ and $x_i = 0$ otherwise, $s_\lambda(x)$ is equal to SSYT($\lambda, N$).

If one introduces $s_\lambda(x, y)$ as the Schur function in variables $x_1, x_2, \dots, y_1, y_2, \dots$ then it is shown in [Sta99, p.341] that $s_\lambda(x, y) = \sum_{\mu, \nu} c_{\mu, \nu}^{\lambda} s_\mu(x) s_\nu(y)$. By specializing at $x_i = y_i = 1$ for $i = 1 \dots m$ and $x_i = y_i = 0$ for $i > m$, we get a polynomial identity in $m$ which in top degree can be written as:

$$ \frac{1}{H_{\lambda}} = \sum_{\mu, \nu} c_{\mu, \nu}^{\lambda} \cdot \frac{1}{2^{d(\mu)}} H_{\mu} \cdot \frac{1}{2^{d(\nu)}} H_{\nu}. \qquad (9) $$

The LR coefficients are easily seen to be nonnegative integers by character theory [Sta99, p.355]; many combinatorial descriptions of them are also known, the most famous being the original Littlewood Richardson rule [LR34]. We will here use the (slightly adapted) Knutson Tao puzzles [KTW04, KT03]:

**Definition 4.1 (Knutson Tao puzzle)** Let $n$ be an integer, and $\sigma, \pi, \tau$ words in $D_n$. Consider a triangle with edge size $2n$ on the regular triangular lattice, where unit edges on left, bottom and right side are labelled by $\sigma, \pi, \tau$ respectively. A Knutson-Tao (KT) puzzle with boundary $\sigma, \pi, \tau$ is a labeling of each internal edge of the triangle with 0,1 or 2, such that the labeling induced on each of the $(2n)^2$ unit triangles is composed either of three 0, or of three 1, or has 0, 1, 2 in counterclockwise order.

The exhaustive list of all authorized labelings of triangles is given on the left of Figure 6, and on the right we have an example of a puzzle with boundaries $\sigma = 00011011$, $\pi = 00110101$, $\tau = 00011011$. It turns out that KT puzzles give a combinatorial interpretation for LR coefficients.

**Theorem 4.2 ([KTW04, KT03])** KT-puzzles with boundary $\sigma, \pi, \tau$ are counted by $c_{\sigma, \tau}^{\pi}$.
<figure><img src="image_6.png" /><figcaption>Fig. 6: Authorized triangles in a KT puzzle, and an example.</figcaption></figure>

## 4.2 The enumeration of extremal TFPL configurations

We can finally state our final result:

**Theorem 4.3** Given $\sigma, \pi, \tau$ such that $d(\sigma) + d(\tau) = d(\pi)$, we have $t_{\sigma, \tau}^{\pi} = c_{\sigma, \tau}^{\pi}$.

The proof consists in a bijective correspondence $\Phi$ from KT-puzzles with boundary $\sigma, \pi, \tau$ to TFPLs in $T_{\sigma, \tau}^{\pi}$. The definition is local: each piece of a puzzle is transformed into a small part of a TFPL configuration. In fact, we will define directly a bijection to oriented configurations (defined in 3.1). The rules are described on Figure 7: non horizontal edges of unit triangles give rise to vertices in $T_n$, while the horizontal ones are sent on lines $y = i + 1/2$. After every triangle of a puzzle $P$ has been transformed (see Figure 8, left), delete the original puzzle, and rescale the graph obtained so that vertices lie on a square grid. To finish, remove the superfluous horizontal edges that appear along the left boundary, double the length of the bottom vertical edges: the resulting graph on $T_n$ is by definition $\Phi(P)$: see Figure 8 again.

<figure><img src="image_7.png" /><figcaption>Fig. 7: The local transformations of the bijection $\Phi$.</figcaption></figure>

**Lemma 4.4** For any puzzle $P$ with boundary $\sigma, \pi, \tau$, $\Phi(P)$ is an (oriented) TFPL configuration in $T_{\sigma, \tau}^{\pi}$.

**Proof:** It is easily seen (albeit a bit tedious) to check by inspection of Figure 7 that the edges created on the left and right boundaries of $\Phi(P)$ correspond indeed to $\sigma$ and $\tau$, and that the bottom external edges
are also present, all of them with their correct orientation. It is also the case, once again by inspection,
that the graph $\Phi(P)$ is such that each of its vertices has one incoming edge and one outgoing.

Paths starting from the left side end up on the right side: indeed, the only other possibility is that such
a path $p$ ends on the bottom side (the left side is not possible because of conflicting orientations); but this
case is easily dismissed, because in the region of $\mathcal{T}_n$ above $p$, there would remain less incoming edges (on
the left boundary) than outgoing edges (on the right boundary), which is absurd.

Finally, one needs to check that the paths connecting the bottom external edges follow the link pattern
$\pi$, and this is more subtle. We already checked that the orientation of these external edges is correct; we
must also show that the paths go globally "from left to right", that is they should not connect two external
edges such that the left one is directed downwards and the right one upwards. Now such a bad path would
necessarily possess a subpath consisting of an up step followed by one or more steps to the left, followed
by one downstep; but a quick look at the rules of Figure 7 reveals that a step to the left is either preceded
by a down step, or followed by an up step, and thus bad paths cannot appear in $\Phi(P)$. A similar reasoning
to the one for paths between the left and right boundaries then shows that paths between bottom external
edges follow the link pattern $\pi$; this finally proves that $\Phi(P)$ is in $\mathcal{T}_{\sigma,\tau}^{\pi}$. $\square$

<figure><img src="image_8.png" /><figcaption>Fig. 8: Example of the bijection $\Phi$.</figcaption></figure>

**Proof of Theorem 4.3:** The previous lemma showed that $\Phi$ is well defined. It is also clear that $\Phi$ is injective, because the ten configurations of oriented edges on Figure 7 are all different, and thus from a puzzle $\Phi(P)$ one can reconstruct the labeling of all edges, i.e. the puzzle $P$. Note the importance of orienting configurations here, because without them some of the local configurations become identified. The injectivity implies by Theorem 4.2 that $t_{\sigma,\tau}^{\pi} \le c_{\sigma,\tau}^{\pi}$. Now comparing Equations (8) and (9) tells us that for a fixed $\pi$, $\sum_{\sigma,\tau} c_{\sigma,\tau}^{\pi} X_{\sigma\tau} = \sum_{\sigma,\tau} t_{\sigma,\tau}^{\pi} X_{\sigma\tau}$ for certain positive coefficients $X_{\sigma\tau}$, the sum being over $\sigma, \tau$ such that $d(\sigma) + d(\tau) = d(\pi)$. Together with the injectivity of $\Phi$, this proves that $t_{\sigma,\tau}^{\pi} = c_{\sigma,\tau}^{\pi}$ and $\Phi$ is in fact bijective, completing the proof of the theorem. $\square$

Acknowledgements

The author would like to thank Johan Thapper for sharing his data on TFPLs.
References

[CKLN06] F. Caselli, C. Krattenthaler, B. Lass, and P. Nadeau. On the number of fully packed loop configurations with a fixed associated matching. *Electron. J. Combin.*, 11(2):Research Paper 16, 43 pp. (electronic), 2004/06.

[CS10] Luigi Cantini and Andrea Sportiello, *Proof of the Razumov-Stroganov conjecture*, arXiv:1003.3376v1.

[dG05] Jan de Gier. Loops, matchings and alternating-sign matrices. *Discrete Math.*, 298(1-3):365-388, 2005.

[KT03] Allen Knutson and Terence Tao. Puzzles and (equivariant) cohomology of Grassmannians. *Duke Math. J.*, 119(2):221-260, 2003.

[KTW04] Allen Knutson, Terence Tao, and Christopher Woodward. The honeycomb model of $GL_n(C)$ tensor products. II. Puzzles determine facets of the Littlewood-Richardson cone. *J. Amer. Math. Soc.*, 17(1):19-48 (electronic), 2004.

[Kup96] Greg Kuperberg. Another proof of the alternating-sign matrix conjecture. *Internat. Math. Res. Notices*, (3):139-150, 1996.

[LR34] Dudley E. Littlewood and Archibald Read Richardson. Group characters and algebra. *Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character (The Royal Society)*, 233:99-141, 1934.

[Pro01] James Propp. The many faces of alternating-sign matrices. In *Discrete models: combinatorics, computation, and geometry (Paris, 2001)*, Discrete Math. Theor. Comput. Sci. Proc., AA, pages 043-058 (electronic). Maison Inform. Math. Discrèt. (MIMD), Paris, 2001.

[RS04] A. V. Razumov and Yu. G. Stroganov. Combinatorial nature of the ground-state vector of the $O(1)$ loop model. *Teoret. Mat. Fiz.*, 138(3):395-400, 2004.

[Sta99] Richard P. Stanley. *Enumerative combinatorics. Vol. 2*, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.

[Tha07] Johan Thapper. Refined counting of fully packed loop configurations. *Sém. Lothar. Combin.*, 56:Art. B56e, 27 pp. (electronic), 2006/07.

[Wie00] Benjamin Wieland. A large dihedral symmetry of the set of alternating sign matrices. *Electron. J. Combin.*, 7:Research Paper 37, 13 pp. (electronic), 2000.

[Zei96] Doron Zeilberger. Proof of the alternating sign matrix conjecture. *Electron. J. Combin.*, 3(2):Research Paper 13, approx. 84 pp. (electronic), 1996. The Foata Festschrift.

[ZJ] Paul Zinn-Justin. Six-Vertex, Loop and Tiling models: Integrability and Combinatorics. Habilitation thesis, arXiv:0901.0665.

[ZJ06] Paul Zinn-Justin. Proof of the Razumov-Stroganov conjecture for some infinite families of link patterns. *Electron. J. Combin.*, 13(1):Research Paper 110, 15 pp, 2006.