# Tableaux combinatorics for two-species PASEP probabilities

Olya Mandelshtam

► To cite this version:

Olya Mandelshtam. Tableaux combinatorics for two-species PASEP probabilities. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp.685-696, 10.46298/dmtcs.2458 . hal-01337782

HAL Id: hal-01337782

https://hal.science/hal-01337782

Submitted on 27 Jun 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Tableaux combinatorics for two-species PASEP probabilities

Olya Mandelshtam¹†

¹ Department of Mathematics, University of California, Berkeley, USA

**Abstract.** The goal of this paper is to provide a combinatorial expression for the steady state probabilities of the two-species PASEP. In this model, there are two species of particles, one “heavy” and one “light”, on a one-dimensional finite lattice with open boundaries. Both particles can hop into adjacent holes to the right and left at rates 1 and $q$. Moreover, when the heavy and light particles are adjacent to each other, they can switch places as if the light particle were a hole. Additionally, the heavy particle can hop in and out at the boundary of the lattice. Our first result is a combinatorial interpretation for the stationary distribution at $q = 0$ in terms of certain multi-Catalan tableaux. We provide an explicit determinantal formula for the steady state probabilities, as well as some general enumerative results for this case. We also describe a Markov process on these tableaux that projects to the two-species PASEP, and hence directly explains the connection between the two. Finally, we extend our formula for the stationary distribution to the $q = 1$ case, using certain two-species alternative tableaux.

**Résumé.** Le but de ce document est de fournir une expression combinatoire décrivant les probabilités de l’état d’équilibre de PASEP à deux espèces. Dans ce modèle, il existe deux espèces de particules, une “lourde” et une “légère”, disposées sur un réseau fini unidimensionnel. Les deux particules peuvent sauter dans les trous adjacents à droite et à gauche, avec des probabilités proportionnelles à 1 et $q$. Par ailleurs, lorsque les particules lourdes et légères sont à côté l’une de l’autre, elles peuvent changer de place, comme si la particule légère était un trou. En outre, la particule lourde peut sauter dans et hors de la frontière du réseau. Notre premier résultat est une interprétation combinatoire de la distribution stationnaire dans le cas $q = 0$, en termes de certains tableaux “multi-Catalan”. Nous proposons une formule explicite déterminantale pour les probabilités stationnaires, ainsi que plusieurs résultats énumératifs généraux pour ce cas. Nous décrivons aussi un processus de Markov sur ces tableaux, qui se projette sur le PASEP à deux espèces, et qui fournit donc directement une connexion entre les deux. Enfin, nous exprimons notre formule pour la distribution stationnaire dans le cas $q = 1$, en utilisant certains tableaux alternatifs de deux espèces.

**Keywords:** PASEP, multispecies, tableaux

## 1 Introduction

The Partially Asymmetric Simple Exclusion Process (PASEP) is a well-studied model that describes the dynamics of particles hopping on a finite one-dimensional lattice on $n$ sites with open boundaries, with

<footnote>†Email: olya@math.berkeley.edu</footnote>
the rule that at most one particle hops at a time. Figure 1 shows the parameters of this process, with the Greek letters denoting the rates of the hopping particles. Processes of this flavor have been studied in many contexts, in particular for their connections to some very nice combinatorics. For instance, see [2] and the references therein.

In this work we consider the two-species PASEP with “heavy” and “light” particles, which we call types 2 and 1 respectively. Both types of particles can hop to the right or left into an adjacent hole with rates 1 and q. Furthermore, heavy particles can enter from the left and exit on the right of the lattice, and they can treat the light particles as holes and swap places with them also at rates 1 and q. Since the light particles cannot enter or exit, their number stays fixed. In particular, when we fix the number of type 1 particles to be zero, we recover the original PASEP. The two-species process was studied by Uchiyama in [4], and a Matrix Ansatz solution and corresponding matrices gave exact expressions for the steady state distribution of the system.

**Fig. 1:** The parameters of the PASEP.

<figure><img src="image_2.png" /><figcaption>Fig. 1: The parameters of the PASEP.</figcaption></figure>

More formally, the two-species PASEP is a Markov chain, whose states are words of length $n$ in the letters $\{D, E, A\}$, where D and A represent the particles of types 2 and 1, and E represents a hole. We also use the following notation for a state: locations are labeled 1 through $n$, and $\tau_i \in \{0, 1\}$ and $\sigma_i \in \{0, 1\}$ are the particle indicators for particles 2 and 1 respectively, with the pair $(\tau, \sigma)$ representing a state. For example, the state AEDDA is represented by $(\tau, \sigma) = ((0, 0, 1, 1, 0), (1, 0, 0, 0, 1))$. We write Prob$((\tau, \sigma))$ or equivalently Prob($X$) for $X$ a word in $\{D, E, A\}^*$ to describe the steady state probability of state $X$.

Figure 2 shows the parameters of the two-species process. More precisely, the transitions in the Markov chain are the following, with $X$ and $Y$ arbitrary words in $\{D, E, A\}^*$.

$$ \begin{array}{ccc} XAEY & \underset{q}{\overset{1}{\rightleftharpoons}} & XEAY & XDEY & \underset{q}{\overset{1}{\rightleftharpoons}} & XEDY & XDAY & \underset{q}{\overset{1}{\rightleftharpoons}} & XADY \\ EX & \underset{\alpha}{\overset{\beta}{\rightleftharpoons}} & DX & XD & \underset{\beta}{\overset{\alpha}{\rightleftharpoons}} & & & & & \end{array} $$

where by $X \xrightarrow{u} Y$ we mean that the transition from $X$ to $Y$ has probability $u/(n+1)$, $n$ being the length of $X$ (and also $Y$).

<figure><img src="image_3.png" /><figcaption>Fig. 2: The parameters of the two-species PASEP. The black particles are of type 2, and the grey ones are of type 1.</figcaption></figure>

Due to (2.9) of [4], the following Matrix Ansatz solution holds for the two-species PASEP:

**Theorem 1.1 (Uchiyama, 2008)** Let $(\tau, \sigma)$ represent a state of the two-species PASEP of length $n$ with $r$ particles of type 1. Suppose there are matrices $D, E$, and $A$ and vectors $\langle w |$ and $| v \rangle$ which satisfy the following conditions

$$ DE = D+E+qED, \quad DA = A+qAD, \quad AE = A+qEA, \quad \langle w|E = \frac{1}{\alpha}\langle w|, \quad D|v\rangle = \frac{1}{\beta}|v\rangle $$
then

$$ \mathrm{Prob}((\tau, \sigma)) = \frac{1}{Z_{n,r}} \langle w | \prod_{i=1}^{n} \tau_i D + \sigma_i A + (1 - \tau_i)(1 - \sigma_i) E | v \rangle $$

where $Z_{n,r}$ is the coefficient of $y^r$ in $\langle w | (D + yA + E)^n | v \rangle$.

This result generalizes a previous Matrix Ansatz solution for the regular PASEP of Derrida et. al. in [1].

In his paper, Uchiyama provides matrices that satisfy the conditions of Theorem 1.1. These matrices contain terms that are neither positive or rational, but the matrix product yields steady state probabilities in the form of polynomials in $\alpha, \beta$, and $q$ with positive integer coefficients. Therefore we would hope for a combinatorial interpretation of these probabilities, with results akin to those of Corteel and Williams [3] for the original PASEP. Such results could yield explicit general formulas for both the desired probabilities and the partition function. A combinatorial solution to the two-species problem could furthermore lead to a solution for a more general process, which would also be a stronger result than the one of [4].

The goal of this paper is to provide some combinatorial solutions to this two-species problem for some special cases. In Section 2 of this paper, we describe certain tableaux which we call multi-Catalan tableaux that give an interpretation for the steady state distributions of the two-species PASEP at $q = 0$. In Section 3 we provide some enumerative results for the multi-Catalan tableaux. In Section 4 we describe a Markov process on the multi-Catalan tableaux that projects to the two-species PASEP at $q = 0$, and which gives another proof of our main result in Section 2. Finally, in Section 5 we define some more general multi-Catalan tableaux that give an interpretation for the steady state distributions of the two-species PASEP at $q = 1$.

*Acknowledgement.* I would like to thank Sylvie Corteel and Lauren Williams for suggesting this problem to me, and for their invaluable advice and support. The hospitality of LIAFA where this research was done, and the Chateaubriand Fellowship awarded by the Embassy of France in the United States that supported this stay in Paris are also gratefully acknowledged.

## 2 Multi-Catalan tableaux

The Multi-Catalan tableaux are inspired by the well-known “alternative tableaux” whose weight-generating functions provide the steady state probabilities for the states of the regular PASEP.

**Definition 2.1** A multi-Catalan tableau of size $n$ is a filling of a Young diagram of shape $\{n, n-1, \dots, 1\}$ with the symbols $\alpha, \beta$, and $x$ as follows:

1. Every box on the diagonal must contain an $\alpha, \beta$, or $x$.

2. A box that sees an $\alpha$ to its right and a $\beta$ below must contain an $\alpha$ or $\beta$.

3. A box that sees an $\alpha$ to its right and an $x$ below must contain a $\beta$.

4. A box that sees an $x$ to its right and a $\beta$ below must contain an $\alpha$.

5. Every other box must be empty.
In the definition above, when we refer to the symbol that a box “sees” to its right or below, we mean the first symbol encountered in the same row or column, respectively. For example, in the first tableau of Figure 3, $x$ is the first symbol that the $\beta$ in the top row sees below it. Finally, note that Rule 5 implies that all boxes in the same row and left of a $\beta$ must be empty, and also that all boxes in the same column and above an $\alpha$ must be empty.

**Definition 2.2** The weight $wt(T)$ of a multi-Catalan tableau $T$ the product of the $\alpha$'s and $\beta$'s it contains.

**Definition 2.3** The type of the tableau $T$ is the word in $\{D, E, A\}^*$ that is read off from the diagonal from top to bottom, by assigning a $D$ to $\alpha$, an $E$ to $\beta$, and an $A$ to $x$.

**Theorem 2.1** Consider the two-species PASEP on a lattice of $n$ sites. Let $X$ be a state described by a word in $\{D, E, A\}^n$. Then the steady state probability of state $X$ is

$$ \mathrm{Prob}(X) = \frac{1}{Z_{n,r}^0} \sum_T wt(T), $$

where the sum is over all multi-Catalan tableaux $T$ such that $type(T) = X$, and where $Z_{n,r}^0 = \sum_T wt(T)$ for $T$ ranging over multi-Catalan tableaux of size $n$ whose type has exactly $r$ $A$'s.

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** These are all possible multi-Catalan tableaux of type DEEAE. Their weights are $\alpha^4\beta^4$, $\alpha^3\beta^4$, and $\alpha^2\beta^4$ respectively.</figcaption></figure>

We show as an example all valid tableaux and their weights for the word DEEAE in Figure 3. Theorem 2.1 implies that

$$ \mathrm{Prob}(\mathrm{DEEAE}) = \frac{1}{Z_{5,1}^0} (\alpha^4\beta^4 + \alpha^3\beta^4 + \alpha^2\beta^4). $$

**Definition 2.4** A $D$-row is a row whose right-most box contains an $\alpha$, and an $A$-row is one whose right-most box contains an $x$. An $E$-column is a column whose bottom-most box contains a $\beta$, and an $A$-column is one whose bottom-most box contains an $x$. Then a $DE$ box is one that lies in a $D$ row and an $E$ column, (and correspondingly for $DA$, $AE$, and $AA$ boxes).

Note that we can ignore the rows with right-most box containing a $\beta$ or columns with bottom-most box containing an $\alpha$ because they are automatically required to be empty according to Definition 2.1.

To connect back to the two-species TASEP, let a state of the TASEP be described by a word $X$ in $\{D, E, A\}^n$. Then we fill a Young diagram of shape $\{n, n-1, \dots, 1\}$ as follows: from top to bottom, we fill the diagonal with symbols $\alpha, \beta$, and $x$ by reading the word $X$ from left to right, and placing an $\alpha$ for a $D$, a $\beta$ for an $E$, and an $x$ for an $A$. Then any valid filling of the rest of the shape will result in a multi-Catalan tableau of type $X$.
## 2.1 Condensed multi-Catalan tableaux

We provide a condensed version of the characterization of the multi-Catalan tableaux, which offers a more
natural proof of our results.

In Figure 4, we demonstrate by example the conversion from a staircase multi-Catalan tableau to a con-
densed multi-Catalan tableau. Specifically, we begin by drawing a lattice path with steps south and west
by reading the diagonal of the staircase tableau from top to bottom. For an $\alpha$, we draw a step south and
label it with a D, for a $\beta$ we draw a step west and label it with an E, and for an $x$ we draw a pair of
steps west and south and label them both with an A. The shape obtained will be the same as if we were
to remove the diagonal from the staircase, and then collapse all the DE, DA, AE, and AA boxes. In the
resulting tableau, a D-row now ends with an edge that has the label D, an A-row ends with an edge with
the label A, and the E- and A-columns are analogous.

In general, to obtain a partition from a word $X$ in $\{D, E, A\}^*$, we apply the definition below.

**Definition 2.5** The partition $\lambda(X)$ associated to a word $X$ is obtained by reading $X$ from left to right, and drawing a step south for $D$, a step west for $E$, and a pair of steps west then south for $A$. This path with south and west steps is declared to be the southeast border of a Young diagram of shape $\lambda(X)$.

**Remark 2.1** The type of the condensed version of the multi-Catalan tableau $T$ is the word in $\{D, E, A\}^*$ that is read from the labels on the boundary from top to bottom, but with $A$ counted only once for each pair of west and south $A$ edges.

The weight of the condensed tableau is the weight of the symbols inside it times the weight of the boundary, which is obtained by giving each $D$ boundary edge weight $\alpha$ and each $E$ boundary edge weight $\beta$.

<figure><img src="image_5.png" /><figcaption>**Fig. 4:** The staircase multi-Catalan tableau on the left and its corresponding condensed multi-Catalan tableau on the right have type *DDDEADEA* and weight $\alpha^6\beta^6$. The condensed tableau is precisely the collapsing together of the white boxes from the staircase tableau.</figcaption></figure>

Since the staircase version of the multi-Catalan tableaux is in simple bijection with the condensed version,
we will call them both multi-Catalan tableaux, and refer to them interchangeably.

We now give a proof of Theorem 2.1.

**Proof (Theorem 2.1):** The Matrix Ansatz of Theorem 1.1 implies that the steady state probabilities for the two-species PASEP satisfy certain recurrences (that in turn determine all probabilities). The strategy of
<figure><img src="image_6.png" /><figcaption>Fig. 5: The chosen corner is a DE box.</figcaption></figure>

our proof is to show that the weight generating function for multi-Catalan tableaux of fixed type satisfies the same recurrences.

We define a corner of the tableau to be a box that is both the right-most box of some row and the bottom-most box of some column. We also define weight for a word $X$ in $\{D, E, A\}^*$ by

$$\text{weight}(X) = \sum_{T} wt(T)$$

where the sum is over all multi-Catalan tableaux $T$ such that $\text{type}(T) = X$.

For a tableau of size $n$, we will choose any corner and remove either the row or column at that corner to reduce to a tableau of size $n-1$. Depending on whether the corner is of type DE, DA, or AE, we have one of the following three cases.

**The chosen corner is a DE box.** In this case, that box must contain either an $\alpha$ or a $\beta$, so we can decompose the tableau into two cases as in Figure 5. If that box contains an $\alpha$, then all the boxes above it are empty, and so its entire column has no effect on the rest of the tableau. Thus any filling of this tableau can be obtained from a filling of a tableau with that column removed. Similarly, if that box contains a $\beta$, then the boxes to its left must be empty, and so its entire row has no effect on the rest of the tableau. Hence any filling of this tableau can be obtained from filling a tableau with that row removed. Let us represent the state of our tableau with the word $XDEY$, with $X$ and $Y$ arbitrary words in $\{D, E, A\}^*$. Consequently, we have the sum of the weights of the fillings:

$$\alpha^n \beta^n \text{weight}(XDEY) = \alpha^{n-1} \beta^{n-1} \text{weight}(XDY)(\alpha\beta) + \alpha^{n-1} \beta^{n-1} \text{weight}(XEY)(\alpha\beta)$$

which matches the first Matrix Ansatz hypothesis. Here the factors of $\alpha^n \beta^n$ come from the coefficient that appears in the normalizing factor of a PASEP of size $n$.

**The chosen corner is a DA box.** In this case, that box necessarily contains a $\beta$, so the boxes to its left are empty and the entire row has no effect on the rest of the tableau. Thus we can describe this tableau in terms of a filling of the smaller tableau with that row removed. Let us represent the state of our tableau with the word $XDAY$, with $X$ and $Y$ arbitrary words in $\{D, E, A\}^*$. Thus we obtain the sum of the weights of the fillings:

$$\alpha^n \beta^n \text{weight}(XDAY) = \alpha^{n-1} \beta^{n-1} \text{weight}(XAY)(\alpha\beta),$$

which matches the second Matrix Ansatz hypothesis.
<figure><img src="image_7.png" /><figcaption>Fig. 6: (a) The chosen corner is a DA box or (b) the chosen corner is an AE box.</figcaption></figure>

**The chosen corner is a AE box.** This case is similar to the one above, except that there is necessarily an $\alpha$ in the corner box, which allows the entire column to be removed.

Similar arguments check the transitions at the boundary.

<figure><img src="image_8.png" /></figure>

## 3 Enumeration of multi-Catalan tableaux

Some enumerative results on regular Catalan tableaux were given in the author's work on the regular PASEP [5] that can be extended to the multi-Catalan tableaux. Building on these results, we can deduce the following.

**Theorem 3.1** The number of multi-Catalan tableaux corresponding to a two-species PASEP at $q = 0$ of size $n$ and with $r$ particles of type 1 is

$$Z_{n,r}^{0}(\alpha = \beta = 1) = \frac{2(r+1)}{n+r+2} \binom{2n+1}{n-r}.$$

**Theorem 3.2** The number of two-species multi-Catalan tableaux corresponding to a two-species PASEP at $q = 0$ of size $n$ and with $r$ particles of type 1 and $k$ particles of type 2 is

$$\frac{r+1}{n+1} \binom{n+1}{k} \binom{n+1}{l}.$$

Note that the expression in Theorem 3.1 is the convolution of Catalan numbers, and the expression in Theorem 3.2 is the convolution of Narayana numbers.

We define size($T$) to be the semiperimeter of the tableau $T$. Let $G_{(\alpha, \beta)}(z) = \sum_{T} z^{\text{size}(T)} wt(T)$ be the weight generating function for multi-Catalan tableaux $T$ whose type has zero A's.

$$G_{(\alpha, \beta)}(z) = \left( \frac{1}{1 - \frac{1}{2\alpha}(1 - \sqrt{1 - 4z\alpha\beta})} \right) \left( \frac{1}{1 - \frac{1}{2\beta}(1 - \sqrt{1 - 4z\alpha\beta})} \right) \\ = \frac{2\alpha^2\beta^2(1-z) + (\alpha\beta - \alpha - \beta)(1 + \sqrt{1 - 4z\alpha\beta})}{2(\alpha^2 - \alpha + z)(\beta^2 - \beta + z)}.$$

Note that $G_{(1,1)}(z) = \frac{1-2z-\sqrt{1-4z}}{2z^2}$, which is the generating function for the Catalan numbers, enumerates the unweighted multi-Catalan tableaux of type with zero A's.
**Theorem 3.3** Let $MCT_{(\alpha,\beta)}(z, y) = \sum_{T} wt(T)z^{size(T)}y^{\#A's in type(T)}$, where $T$ ranges over multi-Catalan tableaux. Then

$$MCT_{(\alpha,\beta)}(z, y) = \frac{G_{(\alpha,\beta)}(z)}{1 - yG_{(1,1)}(z)}.$$

It is easy to see that Theorem 3.1 follows from the above for $\alpha = \beta = 1$.

For the next theorem, we make some more precise definitions to describe the structure of the multi-Catalan tableaux.

**Definition 3.1** We represent a word $X$ in $\{D, E, A\}^n$ with exactly $r$ A's by a list of $r+1$ words in $\{D,E\}^*$, where each word of the list is the longest possible continuous sub-word of $X$ that does not contain an A. We call this list of D-E sub-words $(X_1, \dots, X_{r+1})$. We then represent that list by a list of partitions $\Lambda = (\Lambda_1, \dots, \Lambda_{r+1})$, where the partition $\Lambda_i = \lambda(X_i)$ is the shape obtained from applying Definition 2.5 to the ith D-E word.

As an example for the above, the tableau in Figure 4 has type DDDEADEA, which can be rewritten as a list of three D-E words (DDDE, DE, $\emptyset$). Then the list of partitions is $\Lambda = ((1, 1, 1), (1), (\emptyset))$.

For our final result in this section, we define the matrix $A_{\lambda}^{\alpha,\beta} = (A_{ij})_{1\le i,j\le k}$, where $\lambda$ is some partition $(\lambda_1, \dots, \lambda_k)$, and

$$A_{ij} = \beta^{j-i} \alpha^{\lambda_i - \lambda_{j+1}} \left( \binom{\lambda_{j+1}}{j-i} + \beta \binom{\lambda_{j+1}}{j-i+1} \right) + \beta^{j-i} \alpha^{\lambda_i - \lambda_j} \sum_{\ell=0}^{\lambda_j - \lambda_{j+1} - 1} \alpha^{\ell} \left( \binom{\lambda_j - \ell - 1}{j-i-1} + \beta \binom{\lambda_j - \ell - 1}{j-i} \right).$$

From [5]. weight($X$) = $\det A_{\lambda(X)}^{\alpha,\beta}$ for $X$ a word in $\{D, E\}^*$ corresponding to state of the two-species PASEP with zero type 1 particles.

**Theorem 3.4** Consider the two-species PASEP of size $n$ at $q = 0$, and a state $X$ with exactly $r$ type 1 particles. Let $\Lambda = (\Lambda_1, \dots, \Lambda_{r+1})$ be the list of partitions that corresponds to $X$ according to Definition 3.1. Let $\Lambda_i$ have $k_i$ rows and $m_i$ columns. Then:

$$Prob(X) = \frac{1}{Z_{n,r}^0} \alpha^{n-m_1} \beta^{n-k_{r+1}} \det A_{\Lambda_1}(\alpha, 1) \det A_{\Lambda_{r+1}}(1, \beta) \prod_{i=2}^{r} \det A_{\Lambda_i}(1, 1)$$

where $Z_{n,r}^0 = [z^n y^r] MCT_{(\alpha,\beta)}(z, y)$ of Theorem 3.3.

# 4 A Markov chain on the multi-Catalan tableaux that projects to the two-species PASEP at $q = 0$

In this section we construct a Markov chain on the multi-Catalan tableaux that provides a second proof of Theorem 2.1 and generalizes the construction of Corteel and Williams from [6]. We start by defining projection for Markov chains, from [6, Definition 3.20].

**Definition 4.1** Let $M$ and $N$ be Markov chains on finite sets $X$ and $Y$, and let $F$ be a surjective map from $X$ to $Y$. We say that $M$ projects to $N$ if the following properties hold:
• If $x_1, x_2 \in X$ with $\text{Prob}_M(x_1 \to x_2) > 0$, then $\text{Prob}_M(x_1 \to x_2) = \text{Prob}_N(F(x_1) \to F(x_2))$.

• If $y_1$ and $y_2$ are in $Y$ and $\text{Prob}_N(y_1 \to y_2) > 0$, then for each $x_1 \in X$ such that $F(x_1) = y_1$, there is a unique $x_2 \in X$ such that $F(x_2) = y_2$ and $\text{Prob}_M(x_1 \to x_2) > 0$; moreover, $\text{Prob}_M(x_1 \to x_2) = \text{Prob}_N(y_1 \to y_2)$.

This means that: if $M$ projects to $N$ via the map $F$, then the steady state probability that $N$ is in state $y$ is equal to the sum of the steady state probabilities over all the states $x \in \{z \in X | F(z) = y\}$. In our case, $N$ is the two-species PASEP at $q=0$, and $M$ is the Markov chain on the multi-Catalan tableaux which we describe below. Corteel and Williams defined a Markov chain on permutation tableaux (in bijection with alternative tableaux) that projects to the PASEP. In the two-species PASEP at $q=0$, we have an analogous result using similar transitions.

We describe the process by considering the cases of the possible transitions out of some multi-Catalan tableau $T$ which corresponds to the two-species PASEP state $X$ for which $\text{type}(T) = X$. We begin with the transitions that don't involve particles entering or exiting at the boundary. A transition on state $X$ at location $i$ corresponds to a transition at the corner box in $T$ that has its east edge precisely the $i$th edge of the southeast border (from top to bottom). Figure 7 shows a transition location in a two-species PASEP word $X$ along with the corresponding corner of some multi-Catalan tableau of type $X$.

<figure><img src="image_9.png" /><figcaption>Fig. 7: The tableau corner involved in the transition $DDEAEA \to DEDAEA$.</figcaption></figure>

Now, to obtain a transition at the desired corner, we first strip off the labels on the boundary, then perform certain column or row removal and re-insertion, and finally reapply new labels. We describe the column/row procedure below for the two possible cases for the Greek symbol that corner box could contain.

<figure><img src="image_10.png" /><figcaption>Fig. 8: An example of the row removal and re-insertion procedure for the two possible cases in the transition corner.</figcaption></figure>

**The corner contains a $\beta$.** Remove the row containing the corner (which necessarily is a horizontal stack of empty boxes with a $\beta$ on the right), cut off one of the empty boxes, and insert the row (with the $\beta$ still
at the right of it) in the bottom-most location possible so that the resulting shape is still a Young shape. Figure 8 (a) shows an example. If the row originally had a single box, cutting off a box means it becomes an empty row, and so it should be placed at the south end of the shape with the rest of the empty rows.

**The corner contains an α.** Remove the column containing the corner (which necessarily is a stack of empty boxes above an α), cut off one of the empty boxes, and insert the column (with the α still at the bottom of it) in the right-most location possible so that the resulting shape is still a Young shape. Figure 8 (b) shows an example. If the column originally had a single box, cutting off a box means it becomes an empty column, and so it should be placed at the east end of the shape with the rest of the empty columns.

Now we put the labels back on the edges of the boundary after exchanging the relevant two letters in the labelling word. For example, if the original state was DEA, and a type 2 particle hopped to get the state EDA, then the labels on the boundary change from DEA to EDA.

**Transitions at the boundary.** For an arbitrary PASEP word $X$ in $\{D, A, E\}^*$, we describe the transition that corresponds to the PASEP transition $EX \to DX$ on a tableau $T$ of type $EX$. $T$ must necessarily have at least one empty column on its right, so after stripping off the labels of the tableau, we remove the right-most empty column and instead insert a row with a $\beta$ in its right-most box, of maximal possible length such that the semi-perimeter stays fixed, but at the lowest position possible for that length. Finally, we apply the labeling word $DX$ to the boundary edges. The transition $XD \to XE$ is similar.

<figure><img src="image_11.png" /><figcaption>**Fig. 9:** The state diagram of a two-species PASEP at $q = 0$ of size 3 and with one particle of type 1. Here the words in $\{0,1,2\}^3$ represent the states, with 0 representing a hole, 1 representing particle 1, and 2 representing particle 2.</figcaption></figure>

Figure 9 shows an example of the transitions on all the states of size 3 with one particle of type 1.

**Theorem 4.1** *The Markov chain on multi-Catalan tableaux projects to the two-species PASEP at $q = 0$.*

# 5 Two-species tableaux for $q = 1$

The goal of this section is to give a combinatorial formula for the two-species PASEP for $q = 1$. To this end, we define *two-species alternative tableaux*.
<figure><img src="image_12.png" /><figcaption>Fig. 10: An illustration of the rules in Definition 5.1 for the filling of a two-species alternative tableau.</figcaption></figure>

**Definition 5.1** A two-species alternative tableau of size $n$ is a filling of a Young diagram of shape $\{n, \dots, 1\}$ with the symbols $\alpha, \hat{\alpha}, \beta, \hat{\beta}, q, \hat{q}, u, \hat{u}$ according to the rules below, which are shown in Figure 10.

* every box on the diagonal must contain an $\alpha, \beta$, or $x$.

* a box that sees an $\alpha$ to its right and a $\beta$ below must contain an $\alpha, \beta$, or $q$.

* a box that sees an $\alpha$ to its right and a $\beta$ below must contain an $\hat{\alpha}$ or $q$.

* a box that sees an $\alpha$ to its right and a $\beta$ below must contain a $\hat{\beta}$ or $q$.

* every box in the same column and above an $\alpha$ must contain a $u$, and every box in the same row and left of a $\beta$ must contain a $u$.

* for every pair of $\hat{\alpha}$'s and $\hat{\beta}$'s ($\hat{\alpha}$ left of $\hat{\beta}$) such that the number of A-rows and A-columns between them is not equal, put a $u$ at the intersection of the $\hat{\alpha}$ column and the $\hat{\beta}$ row.

* for every pair $\hat{\alpha}$'s and $\hat{\beta}$'s ($\hat{\alpha}$ left of $\hat{\beta}$) such that the number of A-rows and A-columns between them is equal, we must put either a $\hat{q}$ or a $\hat{u}$ at the intersection of the $\hat{\alpha}$ column and the $\hat{\beta}$ row.

* the placement of the $\hat{q}$ and $\hat{u}$ above must satisfy that there is no instance of $\hat{q} \hat{u}$ or $\hat{u} \hat{q}$.

* every other box must contain a $u$.

In these fillings, the $u$'s are simply place-holders for the empty boxes, and the $\hat{u}$'s are place-holders that enforce valid placement of the $\hat{q}$'s. An easy way to construct these fillings is to place the Greek symbols and $q$'s starting from the boxes closest to the diagonal and moving inwards. Once these symbols are placed everywhere possible, we define an $\hat{\alpha}$-column to be the boxes directly above an $\hat{\alpha}$, and a $\hat{\beta}$-row to be the boxes directly to the left of a $\hat{\beta}$. We then identify the boxes that lie at the intersections of the $\hat{\alpha}$-columns and the $\hat{\beta}$-rows, and fill them appropriately with $\hat{q}$'s, $\hat{u}$'s, or $u$'s. The rest of the tableau is automatically filled with $u$'s.

**Definition 5.2** The type of the two-species alternative tableau is read off of the diagonal from top to bottom, by reading an $\alpha$ as D, a $\beta$ as E, and an $x$ as A. The weight of the tableau is the product of the symbols in the filling in the form of a monomial in $\alpha$ and $\beta$, where we set $u = \hat{u} = 1$, $\hat{\alpha} = \alpha$, $\hat{\beta} = \beta$, and $\hat{q} = q = 1$.
<figure><img src="image_13.png" /><figcaption>Fig. 11: A two-species alternative tableau of type DDDEADEA and weight $\alpha^6\beta^6$. The shaded boxes are ones that are automatically empty due to the labels on the diagonal.</figcaption></figure>

The following theorem is analogous to the main result of Section 2, Theorem 2.1.

**Theorem 5.1** Consider the two-species PASEP at $q = 1$, and let $X$ be a state represented by a word in $\{D, E, A\}^n$ with precisely $r$ A's. Then the steady state probability of $X$ is

$$ Prob(X) = \frac{1}{Z_{n,r}^1} \sum_T wt(T), $$

where the sum is over all two-species alternative tableaux $T$ such that $type(T) = X$, and where $Z_{n,r}^1 = \sum_T wt(T)$, for $T$ ranging over all two-species alternative tableaux of size $n$ whose type has exactly $r$ A's.

## References

[1] B. Derrida, M. Evans, V. Hakim, V. Pasquier. Exact solution of a 1D asymmetric exclusion model using a matrix formulation, J. Phys. A: Math. Gen. 26, 1493–1517 (1993).

[2] S. Corteel and L. Williams. Tableaux combinatorics for the asymmetric exclusion process, Advances in Applied Mathematics, Volume 39, Issue 3, 293–310 (2007).

[3] S. Corteel and L. Williams. Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials. Duke Math. J., 159: 385–415, (2011).

[4] M. Uchiyama. Two-Species Asymmetric Simple Exclusion Process with Open Boundaries. Math Stat. Mech., (2007).

[5] O. Mandelshtam. A determinantal formula for Catalan tableaux and TASEP probabilities. arxiv:1310.7059, (2013).

[6] S. Corteel and L. Williams. A Markov chain on permutations which projects to the PASEP. Int. Math. Res. Not., (2007).