You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: 'We give a simple explanation why the stationary state of the 1D TASEP model with open boundaries is related to the Catalan numbers. Our construction is based on planar binary trees and provides a combinatorial solution of the stationary state. We discuss the relation to permutation/Catalan tableaux approaches in an appendix.'
author:
- Xiangyu Cao
title: 'TASEP and Planar Binary Trees: A Combinatorial Approach'
---

Introduction
============

The Totally Asymmetric Simple Exclusion Process with open boundary condition(open–boundary TASEP) is one of the first interacting driven lattice gas models whose *stationary state* has been obtained exactly [@zeilberger; @derrida; @derrida2]; The stationary state of a driven, out–of–equilibrium particle system is unknown, contrary to a system at equilibrium for which one can write down the Boltzmann distribution. In fact, the open–boundary TASEP belongs to a large family of stochastic models whose stationary state can be calculated by algebraic–integrability techniques, notably the matrix product Ansatz [@matrix]. On the other hand, the stationary state of these models has rich combinatorial structures. In particular the stationary weights of the open–boundary TASEP are known to be closely related to Catalan numbers. This relation has been interpreted using Catalan tableaux(see Viennot et. al. [@viennot]) or more generally using permutation tableaux([@corteel2; @corteel3]). Duchi and Schaeffer([@duchi]) constructed a TASEP model with one hidden line to derive the stationary measure combinatorially. Corteel et. al. managed to do so using lattice paths([@corteel]) or permutation tableaux ([@corteel4]) for more general partially asymmetric exclusion processes. The relation to tableaux combinatorics can also lead to determinant formulae for probabilities ([@mandel]).

Here we would like to record another simple combinatorial approach to the open–boundary TASEP stationary state, based on binary trees. Although binary trees are also used in Angel’s combinatorial approach ([@angel]) to the TASEP with two species of particles(for a definition see [@matrix], Sect. 4), our approach is more closely related to permutation/Catalan tableaux approaches, and particularly close to that of [@corteel4]. The appendix \[app:tableaux\] will be devoted to discussing this relation while the rest of this note will be self–contained.

#### **[Setup and main result.]{}** {#setup-and-main-result. .unnumbered}

In what follows let $n>0$ be a positive integer. The $n$-site open–boundary TASEP is a continuous time Markov chain whose configuration space is $\{\bullet,\circ\}^n$. A state $\mathcal{C}$ therein is a string of length $n$ of $\bullet / \circ$’s and describes the particle occupancy of $n$ sites. Its dynamics is determined by the following *transition rates* $$W(\mathcal{C} \rightarrow \mathcal{C}') = \begin{cases} 
\alpha, & \text{ if } \mathcal{C} = \circ\mathcal{A}, \mathcal{C}' = \bullet\mathcal{A}; \\
\beta,  & \text{ if } \mathcal{C} = \mathcal{A}\bullet, \mathcal{C}' = \mathcal{A} \circ; \\
1,      & \text{ if } \mathcal{C} = \mathcal{A} \bullet\circ\mathcal{A}'; \mathcal{C}' = \mathcal{A} \circ\bullet \mathcal{A}'; \\
0,      & \text{ otherwise. }
\end{cases}$$ where $\alpha, \beta\in (0,1]$ are parameters and $\mathcal{A},\mathcal{A}'$ represent arbitrary $\circ$/$\bullet$ strings. A nontrivial question is to determine the *stationary measure* of such a system for any $n$. This amounts to finding ${\mathbb{P}^\mathrm{st}}_n\{\mathcal{C}\}$ such that for any configuration $\mathcal{C}$, $${\mathbb{P}^\mathrm{st}}_n\{\mathcal{C}\} \sum_{\mathcal{C}'} W(\mathcal{C} \rightarrow\mathcal{C}') = 
 \sum_{\mathcal{C}'} {\mathbb{P}^\mathrm{st}}_n\{\mathcal{C}'\} W(\mathcal{C}' \rightarrow{C}).$$

Let us denote ${\mathcal{T}}_n$ the set of plane binary trees with $(n+2)$-endpoints. Their cardinality is given by the Catalan numbers ${\left\vert{\mathcal{T}}_n\right\vert} = C_{n+1} = \frac{1}{n+2} \binom{2n+2}{n+1}$ ([@stanley]). For example the $5$ elements of $\mathcal{T}_2$ shown in figure \[trees2\].

  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   ![Elements of $\mathcal{T}_2$, their weights and their induced configuration. The marks $\blacksquare$ will be explained in the text.[]{data-label="trees2"}](trees.1 "fig:")   ![Elements of $\mathcal{T}_2$, their weights and their induced configuration. The marks $\blacksquare$ will be explained in the text.[]{data-label="trees2"}](trees.2 "fig:")   ![Elements of $\mathcal{T}_2$, their weights and their induced configuration. The marks $\blacksquare$ will be explained in the text.[]{data-label="trees2"}](trees.4 "fig:")   ![Elements of $\mathcal{T}_2$, their weights and their induced configuration. The marks $\blacksquare$ will be explained in the text.[]{data-label="trees2"}](trees.3 "fig:")   ![Elements of $\mathcal{T}_2$, their weights and their induced configuration. The marks $\blacksquare$ will be explained in the text.[]{data-label="trees2"}](trees.5 "fig:")
                                                                                   $\alpha^{-2}$                                                                                                                                                                   $\alpha^{-1}$                                                                                                                                                                   $\beta^{-1}$                                                                                                                                                                    $\beta^{-2}$                                                                                                                                                               $\alpha^{-1}\beta^{-1}$
  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

On ${\mathcal{T}}_n$ we shall define a *reduction map* $R: {\mathcal{T}}_n \rightarrow \{\bullet,\circ\}^n$ and a *weight function* $\mu: {\mathcal{T}}_n \rightarrow {\mathbb{R}}^+$ as follows:

-   For $T \in {\mathcal{T}}_n$, $R(T) := (t_1, \dots, t_n)$ (called its *reduced configuration*) and $t_k$ is determined by the $(k+1)$-th endpoint of $T$ counting from left: $t_k = \bullet$ if it is a left descendent(its edge is of up-right direction) and $t_k = \circ$ if it is a right descendent(its edge is of up-left direction). The leftmost and rightmost endpoints are not concerned. For $n=2$, from left to right in figure \[trees2\], $R(T)$’s are $\circ\circ,\bullet\circ,\bullet\circ, \bullet\bullet$ and $\circ\bullet$. $R$ is surjective but in general not one–to–one: For example $R^{-1}\{\bullet\circ\}$ has $2$ elements.

-   $\mu(T) := \alpha^{-l(T)} \beta^{-r(T)}$ where $l(T)$(respectively $r(T)$) is the number of vertices on the path between the leftmost(rightmost, respectively) endpoint and the root. For example, $\mu\begin{pmatrix} \includegraphics[scale=0.15]{trees3.5}\end{pmatrix} = \alpha^{-2}$ and weights of elements in ${\mathcal{T}}_2$ are shown in \[trees2\].

\[prop:main2\] The stationary measure of the $n$-TASEP with parameter $\alpha,\beta$ is given by $${\mathbb{P}^\mathrm{st}}_n\{\mathcal{C}\} = (Z_n)^{-1} \sum_{T\in R^{-1} \{\mathcal{C}\}} \mu(T)$$ where $\mu(T) = \alpha^{-l(T)} \beta^{-r(T)} $ where $l(T)$($r(T)$) is the number of vertices between the leftmost(rightmost) endpoint of $T$ and the its root. $Z_n = \sum_{T\in{\mathcal{T}}_n} \mu(T)$ is the normalisation factor.

The rest of the note is devoted to a combinatorial proof of the above proposition. For the sake of transparency, we shall prove it first for the special case of $\alpha = \beta = 1$ in Sect. \[sec:special\]. The general case is considered in Sect. \[sec:general\].

Case of $\alpha = \beta = 1$ {#sec:special}
============================

In this section we focus on the case of $\alpha = \beta = 1$, *i.e.*, and consider the following restriction of Proposition \[prop:main2\]:

\[prop:main\] The stationary probability of the $n$-TASEP with $\alpha = \beta = 1$ is induced by the uniform measure on ${\mathcal{T}}_n$ $${\mathbb{P}^\mathrm{st}}_n\{\mathcal{C}\} = \frac{{\left\vert R^{-1} \{\mathcal{C}\} \right\vert}}{{\left\vert{\mathcal{T}}_n\right\vert}}.$$ (Here and below, ${\left\vertX\right\vert}$ denotes the cardinal of the set $X$.) In other words, for any state $\mathcal{C}\in \{\bullet, \circ\}^n$, we have the flux balance equation $$\label{eqn:bilan}
 {\left\vert R^{-1} \{\mathcal{C}\}\right\vert} \sum_{\mathcal{C}'} W(\mathcal{C} \rightarrow\mathcal{C}') = 
 \sum_{\mathcal{C}'} {\left\vert R^{-1} \{\mathcal{C}'\}\right\vert} W(\mathcal{C}' \rightarrow\mathcal{C}).$$

Since $\alpha=\beta=1$, $W(\mathcal{C} \rightarrow\mathcal{C}')$ is either $0$ or $1$, so both sides of equation \[eqn:bilan\] are integers, which suggests a combinatorial proof. Indeed, we shall interpret either side of (\[eqn:bilan\]) as the size of a set, and construct a bijection between them.

On a plane binary tree, we define a *last branching vertex* to be a non–endpoint vertex whose descendents are both endpoints. The last branching vertices were all marked with $\blacksquare$’s in the figure \[trees2\]. We define a *marked* plane binary tree is a plane binary tree with *only one* of its last branching vertices marked with a $\blacksquare$. We denote ${\widehat{\mathcal{T}}}_n$ the set of marked binary trees of $(n + 2)$ end-points and let $f:{\widehat{\mathcal{T}}}_n \rightarrow {\mathcal{T}}_n$ be the map that forgets the marking. For $n > 1$, we have ${\left\vert{\widehat{\mathcal{T}}}_n\right\vert} > {\left\vert{\mathcal{T}}_n\right\vert}$ since $f$ is subjective but not one–to–one. For example, ${\widehat{\mathcal{T}}}_2$ has $6$ elements as listed below:

![Elements of ${\widehat{\mathcal{T}}}_2$. Note that the last two elements in figure \[mtrees2\] are mapped by $f$ to the same element of ${\mathcal{T}}_2$(namely, the last one in figure \[trees2\]).[]{data-label="mtrees2"}](trees.1 "fig:") ![Elements of ${\widehat{\mathcal{T}}}_2$. Note that the last two elements in figure \[mtrees2\] are mapped by $f$ to the same element of ${\mathcal{T}}_2$(namely, the last one in figure \[trees2\]).[]{data-label="mtrees2"}](trees.2 "fig:") ![Elements of ${\widehat{\mathcal{T}}}_2$. Note that the last two elements in figure \[mtrees2\] are mapped by $f$ to the same element of ${\mathcal{T}}_2$(namely, the last one in figure \[trees2\]).[]{data-label="mtrees2"}](trees.4 "fig:") ![Elements of ${\widehat{\mathcal{T}}}_2$. Note that the last two elements in figure \[mtrees2\] are mapped by $f$ to the same element of ${\mathcal{T}}_2$(namely, the last one in figure \[trees2\]).[]{data-label="mtrees2"}](trees.3 "fig:")\
![Elements of ${\widehat{\mathcal{T}}}_2$. Note that the last two elements in figure \[mtrees2\] are mapped by $f$ to the same element of ${\mathcal{T}}_2$(namely, the last one in figure \[trees2\]).[]{data-label="mtrees2"}](trees.6 "fig:") ![Elements of ${\widehat{\mathcal{T}}}_2$. Note that the last two elements in figure \[mtrees2\] are mapped by $f$ to the same element of ${\mathcal{T}}_2$(namely, the last one in figure \[trees2\]).[]{data-label="mtrees2"}](trees.7 "fig:")

${\widehat{\mathcal{T}}}_3$ has $20$ elements(while ${\mathcal{T}}_3$ has $14$), we draw them in the appendix \[app:t3\].(In general, one can show that ${\mathcal{T}}_n$ has $\binom{2n}{n}$ elements. But we will not need this result for the following)

Now we make a crucial observation that follows from the above definitions: The last branching vertices of a tree $T$ correspond to the active bonds(places where a transition to another configuration is possible) of its reduced configuration $R(T)$. As a consequence, we have the following

Suppose $\alpha = \beta = 1$. For any $\mathcal{C} \in \{\bullet,\circ\}^n$ and $T\in R^{-1}\{\mathcal{C}\}$, we have $\sum_{\mathcal{C}'} W(\mathcal{C} \rightarrow\mathcal{C}') = {\left\vertf^{-1}\{T\}\right\vert}$. As a consequence, for any $\mathcal{C} \in \{\bullet,\circ\}^n$, $$\label{eq:lhs}
{\left\vert R^{-1} \{\mathcal{C}\}\right\vert} \sum_{\mathcal{C}'} W(\mathcal{C} \rightarrow\mathcal{C}') = {\left\vert (Rf)^{-1}\{\mathcal{C}\}\right\vert}.$$

Thus we managed to see the left hand side of \[eqn:bilan\] as the size of a set. Next, we shall describe a map $ \pi: {\widehat{\mathcal{T}}}_n \rightarrow {\widehat{\mathcal{T}}}_n $ which we will prove to be a bijection, and such that the right hand side of \[eqn:bilan\] is the size of the set $ (Rf\pi)^{-1}\{\mathcal{C}\}$, which is bijected to $ f^{-1}R^{-1}\{\mathcal{C}\}$ by $\pi$. This would conclude the proof of Proposition \[prop:main\].

Consider a marked tree $\widehat{T}$. Since the tree root is never a last branching vertex (for $n>0$), its marked last branching vertex $v$ is either a left descendent or a right descendent (of its ascendent). Suppose for the moment that $v$ is a right descendent. To obtain $\pi(\widehat{T})$, we remove the segment linking $v$ and its left descendent, glue it to the next right-descendent endpoint to its right and mark the new vertex. For example:

$\pi:$ $\begin{matrix}\includegraphics[scale=0.4]{trees3.23}\end{matrix}$ $\longmapsto$ $\begin{matrix}\includegraphics[scale=0.4]{trees3.24} \end{matrix}$

To illustrate, the moved segment is drawn in bold.

In the special case where $v$ has the rightmost endpoint of the tree as descendent, the above operation cannot be done. In this case, we glue the removed segment to the rightmost left-descendent endpoint of the tree and mark the new vertex, for example

$\pi:$ $\begin{matrix}\includegraphics[scale=0.5]{trees.8}\end{matrix}$ $\longmapsto$ $\begin{matrix}\includegraphics[scale=0.5]{trees.9}\end{matrix}$

Note that in this second (boundary) case the moved segment changes direction as opposed to the first case.

So we have defined $\pi$ when the marked last branching vertex is a right descendent. For the alternative possibility, we just need to swap the words “left” and “right” in the recipe described above (Equivalently, one may say that we complete the definition of $\pi$ in the unique way so that it preserves the left–right symmetry). We illustrate below $\pi$ for $n = 2$ (see appendix \[app:t3\] for $n = 3$).

$\begin{matrix}\includegraphics[scale=0.5]{trees.1}\end{matrix}$ $\longmapsto$ $\begin{matrix}\includegraphics[scale=0.5]{trees.2}\end{matrix}$ $\longmapsto$ $\begin{matrix}\includegraphics[scale=0.5]{trees.7}\end{matrix}$ $\longmapsto$ $\begin{matrix}\includegraphics[scale=0.5]{trees.1}\end{matrix}$,\
$\begin{matrix}\includegraphics[scale=0.5]{trees.3}\end{matrix}$ $\longmapsto$ $\begin{matrix}\includegraphics[scale=0.5]{trees.4}\end{matrix}$ $\longmapsto$ $\begin{matrix}\includegraphics[scale=0.5]{trees.6}\end{matrix}$ $\longmapsto$ $\begin{matrix}\includegraphics[scale=0.5]{trees.3}\end{matrix}$.

One sees that they are permutations(bijections). This is true in general:

\[lem:bij\] $\pi: {\widehat{\mathcal{T}}}_n \rightarrow {\widehat{\mathcal{T}}}_n$ is a bijection.

In fact we can describe its inverse $\sigma$ in a similar manner. To obtain $\sigma(\widehat{T})$ from $\widehat{T}$, assuming that the marked last branching vertex $v$ is a right(left) descendent, remove the segment linking $v$ and its left(right) descendent, glue it to the next right(left)-descendent endpoint to its left(right); when it is impossible to do so, move it to the leftmost(rightmost) endpoint (changing its direction). In either case, mark the new vertex. This construction guarantees that $\sigma$ and $\pi$ are inverse to each other.

Now let us take a pair $\widehat{T} = \pi (\widehat{T}')$ and consider their respective reduced states $ \mathcal{C} = Rf(\widehat{T})$ and $\mathcal{C}'= Rf(\widehat{T}')$. One can observe by construction of $\pi$ that $W(\mathcal{C}'\rightarrow \mathcal{C}) \neq 0$(in fact equal to $1$ provided $\alpha = \beta = 1$) for any such pair $\widehat{T}$ and $\widehat{T}'$.

Conversely, for any pair of states $\mathcal{C},\mathcal{C}'$ such that $W(\mathcal{C}' \rightarrow \mathcal{C}) \neq 0$ ($=1$ in the case $\alpha = \beta = 1$), there are exactly ${\left\vertR_n^{-1}\{\mathcal{C}'\}\right\vert}$ marked trees $\widehat{T}'$ such that $Rf\pi(\widehat{T}') = \mathcal{C}$. In fact, for each $T' \in R^{-1} \{\mathcal{C}'\}$, there is one and only one $\widehat{T}'$ such that $f(\widehat{T}') = T'$ and that $Rf\pi(\widehat{T}') = \mathcal{C}$: It is the one obtained by marking the last branching vertex corresponding to the active bond involved in the transition $\mathcal{C}' \rightarrow \mathcal{C}$.

We have thus shown the following:

For any $\mathcal{C},\mathcal{C}' \in \{0,1\}^{n}$, the set $\mathcal{F}(\mathcal{C}' \rightarrow \mathcal{C})$ defined as $$\mathcal{F}(\mathcal{C}' \rightarrow \mathcal{C}) := (Rf)^{-1}\{\mathcal{C}'\} \bigcap (Rf\pi)^{-1}\{\mathcal{C}\}$$ is non-empty if and only if $W(\mathcal{C}' \rightarrow \mathcal{C}) \neq 0$. In this case its cardinal is equal to that of $R^{-1}\{\mathcal{C}'\}$. Thus, when $\alpha = \beta = 1$ we have $$\label{eq:flux}
{\left\vert\mathcal{F}(\mathcal{C}' \rightarrow \mathcal{C})\right\vert}  =  {\left\vertR^{-1}\{\mathcal{C}'\}\right\vert} W(\mathcal{C}' \rightarrow \mathcal{C}).$$

Summing the above equation over $\mathcal{C}'$, we have for any $\mathcal{C} \in \{ \bullet, \circ\}^{n}$ $$\label{eqn:rhs}
{\left\vert(Rf\pi)^{-1}\{\mathcal{C}\}\right\vert} = \sum_{\mathcal{C}'} {\left\vert (Rf)^{-1}\{\mathcal{C}'\} \bigcap (Rf\pi)^{-1}\{\mathcal{C}\} \right\vert} = 
\sum_{\mathcal{C}'} {\left\vert R^{-1} \{\mathcal{C}'\}\right\vert} W(\mathcal{C}' \rightarrow\mathcal{C})$$ which is promised before. Now combining equations (\[eq:lhs\]), the bijectiveness of $\pi$ (lemma \[lem:bij\]) and the equation \[eqn:rhs\]) gives $${\left\vert R^{-1} \{\mathcal{C}\}\right\vert} \sum_{\mathcal{C}'} W(\mathcal{C} \rightarrow\mathcal{C}') = {\left\vert(Rf)^{-1}\{\mathcal{C}\}\right\vert} = 
{\left\vert(Rf\pi)^{-1}\{\mathcal{C}\}\right\vert} =  \sum_{\mathcal{C}'} {\left\vert R^{-1} \{\mathcal{C}'\}\right\vert} W(\mathcal{C}' \rightarrow\mathcal{C}),$$ which proves Proposition \[prop:main\]. Notice that summing eq.(\[eq:flux\]) over $\mathcal{C}$ gives eq. (\[eq:lhs\]), so it is in fact the only ingredient for proving Proposition \[prop:main\] besides the bijectiveness of $\pi$.

General $\alpha,\beta$ {#sec:general}
======================

Now that combinatorial constructions are independent of the value of $\alpha$ and $\beta$, to adapt our proof to arbitrary values of $\alpha$ and $\beta$, we need to assign weights to marked trees so that a weighted version of (\[eq:flux\]) holds. We define $\hat{\mu}:{\widehat{\mathcal{T}}}_n \rightarrow {\mathbb{R}}^+$ as $\hat{\mu}(\widehat{T}) = \alpha^{-l'(\widehat{T})} \beta^{-r'(\widehat{T})}$ where $l'(\widehat{T})$(respectively $r'(\widehat{T})$) counts the same vertices as do $l(T)$($r(T)$ respectively) *except* the marked one when it is there: For example when $\widehat{T} = \begin{matrix} \includegraphics[scale=0.3]{trees3.20} \end{matrix}$, $\hat{\mu} \left(\widehat{T}  \right) = \alpha^{-1}\beta^{-1}$ while $\mu(f(\widehat{T})) = \alpha^{-1}\beta^{-2}$. $\mu$ ($\hat{\mu}$ respectively) defines a measure on (the power set of) ${\mathcal{T}}_n$ (respectively ${\widehat{\mathcal{T}}}_n$) in the obvious way and we shall denote the measure again by $\mu$($\hat{\mu}$ respectively).

To show Proposition \[prop:main2\], all we need is the following two properties of $\mu$ and $\hat{\mu}$, which can be readily checked :

1.  For any $\widehat{T} \in \mathcal{F}(\mathcal{C}' \rightarrow \mathcal{C})$, $\hat{\mu}(\widehat{T}) = \mu(f(\widehat{T})) W(\mathcal{C}' \rightarrow \mathcal{C})$.

2.  For any $\widehat{T} \in {\widehat{\mathcal{T}}}_n$, $\hat{\mu}(\widehat{T}) = \hat{\mu}(\pi(\widehat{T}))$.

Property (a) implies the following variant of (\[eq:flux\]) $$\label{eqn:flux2}
\hat{\mu} (\mathcal{F}(\mathcal{C}' \rightarrow \mathcal{C}))  = \mu(R^{-1} \{\mathcal{C}'\})W(\mathcal{C}'\rightarrow \mathcal{C}).$$ Summing it over $\mathcal{C}'$ gives $$\hat{\mu}((Rf\pi)^{-1}\{\mathcal{C}\}) = \sum_{\mathcal{C}'}  \mu(R^{-1} \{\mathcal{C}'\}) W(\mathcal{C}' \rightarrow\mathcal{C})$$ which generalises eq. (\[eqn:rhs\]), while summing (\[eqn:flux2\]) over $\mathcal{C}$(and switching variable names $\mathcal{C}$ and $\mathcal{C}'$) gives $$\hat{\mu}((Rf)^{-1}\{\mathcal{C}\}) = \sum_{\mathcal{C}'} \mu(R^{-1} \{\mathcal{C}\}) W(\mathcal{C} \rightarrow\mathcal{C}')$$ which generalises eq. (\[eq:lhs\]). Now property (b) implies $$\hat{\mu}((Rf)^{-1}\{\mathcal{C}\}) = \hat{\mu}((Rf\pi)^{-1}\{\mathcal{C}\} ),$$ hence $$\sum_{\mathcal{C}'}  \mu(R^{-1} \{\mathcal{C}\} ) W(\mathcal{C} \rightarrow\mathcal{C}') =  \sum_{\mathcal{C}'} \mu(R^{-1} \{\mathcal{C}'\}) W(\mathcal{C}' \rightarrow\mathcal{C}).$$ That is, the stationary measure of the $n$-site TASEP is given by $ {\mathbb{P}^\mathrm{st}}_n\{\mathcal{C}\} = (Z_n)^{-1} \mu(R^{-1} \{\mathcal{C}\})$, where $Z_n = \mu({\mathcal{T}}_n)$, as claimed in Proposition \[prop:main2\].

Conclusion
==========

In this note we have considered a combinatorial solution of the open boundary TASEP stationary state in terms of planar binary trees. We can summarise our approach as two points. First, the (nontrivial) stationary measure on the configuration space is induced by a simple measure on the space of plane binary trees (in the case of $\alpha = \beta = 1$ the latter measure is uniform). Second, the balance equation is given a bijective proof(at least in the $\alpha = \beta = 1$ case): every term therein is interpreted as the cardinal of a set, and equality comes from the construction of a bijection.

Let us mention briefly some models whose stationary state can be obtained by a variant of the approach presented above, leaving details for future work. One can adapt this approach to the periodic boundary condition TASEP with one second class particle(for an introduction see [@matrix], Sect. 4) with only a slight modification of $\pi$. Essentially the same construction works when there are $k$ second class particles: For this we need to consider $k$-tuples of planar binary trees. The latter construction works also for a special case of open boundary two–species TASEP where the second class particles are neither injected nor extracted, as first considered in [@2species]. An interesting question is whether it is possible to generalise our approach to the multi–species TASEP, whose stationary state has been obtained combinatorially by Martin and Ferrari in [@multi], but with a queueing–theory–inspired construction.

Elements of ${\widehat{\mathcal{T}}}_3$ and the permutation $\pi$ {#app:t3}
=================================================================

We first enumerate all elements of ${\widehat{\mathcal{T}}}_3$. They are organised in the following manner

-   A configuration $\mathcal{C}\in \{\bullet, \circ\}^3$ is followed by the elements of $f^{-1}R^{-1}\{\mathcal{C}\}$.

-   Elements having the same image under $f$ are put in a parenthesis.

<!-- -->

-   $\circ\circ\circ$: $\begin{pmatrix} \includegraphics[scale=0.35]{trees3.1}\end{pmatrix}$

-   $\bullet\bullet\bullet$: $\begin{pmatrix} \includegraphics[scale=0.35]{trees3.8} \end{pmatrix}$

-   $\circ\circ\bullet$: $\begin{pmatrix} \includegraphics[scale=0.35]{trees3.19}    & \includegraphics[scale=0.35]{trees3.21} \end{pmatrix}$

-   $\circ\bullet\bullet$: $\begin{pmatrix} \includegraphics[scale=0.35]{trees3.22}  & \includegraphics[scale=0.35]{trees3.20}   \end{pmatrix}$

-   $\bullet\circ\circ$: $\begin{pmatrix}  \includegraphics[scale=0.35]{trees3.2}\end{pmatrix}$ $\begin{pmatrix} \includegraphics[scale=0.35]{trees3.4}\end{pmatrix}$ $\begin{pmatrix} \includegraphics[scale=0.35]{trees3.10}  \end{pmatrix}$

-   $\bullet\bullet\circ$: $\begin{pmatrix} \includegraphics[scale=0.35]{trees3.9}\end{pmatrix}$ $\begin{pmatrix}  \includegraphics[scale=0.35]{trees3.11}\end{pmatrix}$ $\begin{pmatrix} \includegraphics[scale=0.35]{trees3.3}\end{pmatrix}$

-   $\circ\bullet\circ$: $\begin{pmatrix}\includegraphics[scale=0.35]{trees3.6}&
                        \includegraphics[scale=0.35]{trees3.7}\end{pmatrix}$ $\begin{pmatrix}\includegraphics[scale=0.35]{trees3.18} &
                         \includegraphics[scale=0.35]{trees3.16} \end{pmatrix}$

-   $\bullet\circ\bullet$: $\begin{pmatrix} \includegraphics[scale=0.35]{trees3.15}
                       & \includegraphics[scale=0.35]{trees3.17} \end{pmatrix}$ $\begin{pmatrix} \includegraphics[scale=0.35]{trees3.14} &
                         \includegraphics[scale=0.35]{trees3.13} \end{pmatrix}$

Next we describe $\pi: {\widehat{\mathcal{T}}}_3 \rightarrow {\widehat{\mathcal{T}}}_3$. It is a permutation, and we depict each of its cycles in one row: $\pi$ maps each element to the one to its right, and the rightmost element to the leftmost.

$\begin{matrix}\includegraphics[scale=0.35]{trees3.1}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.2}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.7} \end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.21} \end{matrix}$\
$\begin{matrix}\includegraphics[scale=0.35]{trees3.6}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.3}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.17} \end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.4}\end{matrix}$\
$\begin{matrix}\includegraphics[scale=0.35]{trees3.18}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.11}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.13}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.10}\end{matrix}$\
$\begin{matrix} \includegraphics[scale=0.35]{trees3.22}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.8}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.9}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.14}\end{matrix}$\
$\begin{matrix}\includegraphics[scale=0.35]{trees3.19}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.15}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.20}\end{matrix}$ $\mapsto$ $\begin{matrix}\includegraphics[scale=0.35]{trees3.16} \end{matrix}$\

Relation with Catalan Tableaux {#app:tableaux}
==============================

This appendix comments briefly the relation of our planar binary tree construction with the combinatorial solution of open–boundary TASEP(and more general partially asymmetric processes) stationary measure by Corteel and Williams ([@corteel4]). We shall construct a simple correspondence between planar binary trees and Catalan tableaux, on which the above cited work is based(when restricted to the TASEP).

Be definition, *Catalan tableaux* are Young diagrams filled with $0$ and $1$’s($0/1$ tableaux) fulfilling two properties:

1.  On each column there is exactly one $1$, with the exception of the leftmost column where there is no $1$.

2.  There are no $0$ that has a $1$ above it in the same column and a $1$ left to it in the same row. (The Young diagram is drawn in the down–right quadrant)

The *index* of of a Catalan tableaux is defined as $\lambda_1 + \lambda_1^t - 1$, where $\lambda = (\lambda_1 \geq \lambda_2 \geq \dots)$ is the partition of the underlying Young diagram and $\lambda^t$ the transpose. For example, $\begin{matrix} \includegraphics[scale=0.6]{trees3.30} \end{matrix}$ is a Catalan tableaux of index $5$ while $\begin{matrix} \includegraphics[scale=0.6]{trees3.29} \end{matrix}$ is *not* a Catalan tableaux since it violates the second defining property.

Catalan tableaux were considered as a special case of permutation tableaux in [@perm], where it is shown that the number of Catalan tableaux of index $n$ is the Catalan number $C_n$. There has been a combinatorial proof of this result by constructing a bijective correspondence with binary trees in [@viennot]. Our definition can be seen to be equivalent to the Definition 2.1 of [@viennot] by removing the column without $1$’s.

Here we propose another simple bijection, from ${\mathcal{T}}_n$ onto the set of Catalan tableaux of index $n + 1$. We shall describe it as a procedure of obtaining a $0/1$ tableaux from a plane binary tree in $3$ steps. As a running example we take $T = \begin{matrix}
\includegraphics[scale=0.35]{trees3.5}
\end{matrix}   \in {\mathcal{T}}_3$.

1.  We first draw a lattice path in the $2D$ square lattice, starting from anywhere, as we read *all* endpoints of $T$ from left to right: We move one unit to the right(respectively, one unit up) each time we read a left–descendent(right–descendent, respectively). Note that the lattice path has length $n+2$, the first(last) step is always to the right(up, respectively), so that we can form a Young diagram $\lambda(T)$ by adding a vertical segment from the starting point and a horizontal line from the ending point. For example, $$\lambda\begin{pmatrix}
    \includegraphics[scale=0.35]{trees3.5}
    \end{pmatrix} = \begin{matrix}
    \includegraphics[scale=0.55]{trees3.25} \end{matrix}.$$ Here the lattice path is drawn in bold. (Remark that $\lambda(T)$ depends only on the reduced configuration $R(T)$)

2.  Then we rotate the binary tree by $\pi / 4$ and embed it conformally into the Young diagram $\lambda(T)$ as illustrated $$\begin{matrix}
    \includegraphics[scale=0.35]{trees3.5}
    \end{matrix} \leadsto   \begin{matrix}
    \includegraphics[scale=0.6]{trees3.26} \end{matrix}$$ such that each endpoint is at the centre of its corresponding lattice path segment.

3.  Finally, to obtain the $0/1$ tableaux, we fill a $1$ into every square inside which the pattern $\begin{matrix}\includegraphics[scale=0.6]{trees3.27}\end{matrix}$ occurs and filling a $0$ into any other square, So the above example gives the tableaux $$\begin{matrix}
    \includegraphics[scale=0.35]{trees3.5}
    \end{matrix} \longmapsto   \begin{matrix}
    \includegraphics[scale=0.6]{trees3.26} \end{matrix} \longmapsto  \begin{matrix}
    \includegraphics[scale=1.2]{trees3.28} \end{matrix}.$$

So far we have defined a map, which we denote $\phi$, from ${\mathcal{T}}_n$ to a certain set of $0$/$1$ tableaux. One can show that

$\phi$ is a bijection between ${\mathcal{T}}_n$ and the set of Catalan tableaux of index $n + 1$.

Equipped with this Catalan tableaux $\leftrightarrow$ plane binary tree correspondence, one can reformulate the combinatorial approach to the TASEP stationary state of Corteel and Williams in [@corteel4](more general partially asymmetric processes were considered there using permutation tableaux; one can see that the special case of TASEP corresponds to considering only Catalan tableaux) in terms of planar binary trees: By doing so we recognised that the Markov chain dynamics that the authors of [@corteel4] defined on the set of Catalan tableaux can be obtained by using the $\pi$ bijection defined in this note. However, we have refrained from defining a Markov chain dynamics on ${\mathcal{T}}_n$ (although it can be done).

The author is indebted to his advisor Kirone Mallick for his patient help during the preparation of this work. He thanks <PRESIDIO_ANONYMIZED_PERSON> for valuable suggestions and for fruitful discussions, which have led to the Appendix \[app:tableaux\] in particular.

[1]{} L. Shapiro, D. Zeilberger, 1982, *A Markov chain occurring in enzyme kinetics*, J. Math. Biology 15 , 351 –357. B. Derrida, E. Domany and D. Mukamel, 1992, *An exact solution of a one-dimensional asymmetric exclusion model with open boundaries,* J. Stat. Phys. 69, 667. B. Derrida, M. R. Evans, V. Hakim, V. Pasquier, 1993, *Exact solution of a 1D asymmetric exclusion model using a matrix formulation*, J. Phys. A: Math. Gen. 26, 1493. R. A. Blythe and M. R. Evans, 2007, *Nonequilibrium steady states of matrix-product form: a solver’s guide*, J. Phys. A:Math. Theor. 40, R333. O. Angel, *The stationary measure of a 2-type totally asymmetric exclusion process*, J. Comb. Theory A 113 , 625 (2006). E. Duchi, G. Schaeffer, *A combinatorial approach to jumping particles*, J. Combin. Theory Ser. A 110 (2005), 1–29. S.Corteel, R.Brak, A.Rechnitzer,J. Essam, 2005, *A combinatorial derivation of the PASEP stationary state*, FPSAC’05, Taormina. S. Corteel, L. K. Williams, 2007, *Tableaux combinatorics for the asymmetric exclusion process.* Advances in applied mathematics, 39(3), 293-310. S. Corteel, L. K. Williams, 2011, *Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials*, Duke Mathematical Journal, 159(3), 385-415. S. Corteel, L. K. Williams, 2007, *A Markov Chain on Permutations which Projects to the PASEP*, International mathematics research notices, Vol 2007. O. Mandelstam, 2013. *A Determinantal Formula for Catalan Tableaux and TASEP Probabilities*. arXiv preprint arXiv:1310.7059. X.G. Viennot, 2007, *Canopy of binary trees, Catalan tableaux and the asymmetric exclusion process*, in Proc. FPSAC07 (Formal Power Series and Algebraic Combinatorics), Tienjin, Chine, 2007, 12 pp. A. Ayyer, J. L. Lebowitz, and E. R. Speer, *On the Two Species Asymmetric Exclusion Process with Semi-Permeable Boundaries*, J. Stat. Phys. 135 (2009), 1009–1037. P. A. Ferrari and J. B. Martin, *Stationary distributions of multi-type totally asymmetric exclusion processes*, Ann. Probab. 35, 807 (2007). R. Stanley, *Enumerative Combinatorics,* Vol. 2, Cambridge, 1999. E. Steingrimsson and L.K. Williams, *Permutation tableaux and permutation patterns*, arXiv:math.CO/0507149, J. Combinatorial Th. A.,114 (2007) 211-234.