Permutations associated to Dyck paths that are enumerated by Catalan numbers

Edit: The following proposed condition was incorrect; the Dyck path UUDUDUDUDD gives a counterexample.

Although I have not yet proven it, experimental results suggest that a permutation $\sigma$ is a Dyck permutation if and only if the following conditions are satisfied:

1. $\sigma$ is fixed-point free.
2. $\sigma$ is connected.
3. There exists no pair $(i, j)$ such that $i < j < \sigma(i) < \sigma(j)$.
4. There exists no pair $(i, j)$ such that $i > j > \sigma(j) > \sigma(i)$.

It can be proved as follows that the total number of permutations satisfying conditions (1)–(4) is the Catalan number.

For a Dyck path, let $(i_1, j_1), \dots, (i_m, j_m)$ be the corners of its Cartan matrix. For $a \in \{1, 2, \dots, n+1\}$, define $$ S(a) = |\{k \mid j_k \leq a\}| - |\{k \mid i_k < a\}|. $$ Then define the permutation $\sigma$ by $$ \sigma(i) = \begin{cases} j_k & \text{if } i = i_k,\\ \min\{a \mid i < a,\ S(i) = S(a)\} & \text{if } i \notin \{i_1, \dots, i_m\}. \end{cases} $$ This permutation $\sigma$ satisfies conditions (1)–(4). Conversely, for any permutation $\sigma$ that satisfies conditions (1)–(4), one can construct a Dyck path whose corners are precisely the pairs $(i, \sigma(i))$. In this way, permutations satisfying conditions (1)–(4) correspond bijectively to Dyck paths, and their number is the Catalan number.

Unfortunately, I was not able to prove that the bijection given in the above proof coincides with the correspondence arising from the Bruhat decomposition. Given a Dyck permutation $\sigma$, the pairs $(i, \sigma(i))$ with $i > \sigma(i)$ correspond exactly to the corners of the Cartan matrix, so condition (4) is satisfied. If one can prove that condition (3) always holds, then we can show that $$ \{\text{Dyck permutations}\} = \{\text{permutations satisfying (1)-(4)}\} $$ by comparing the number of elements.

I decided to consider a particular case, in hope that this will give some clues for the general case.

The particular Dyck paths I propose to consider can be called "fully returning" Dyck paths, they are those $[c_1,c_2,...,c_n]$ which satisfy the condition $$ \text{if $c_i>2$ then $c_{i+1}=c_i-1$.} $$ Such a path is uniquely determined by the set $S=\{i\mid c_{i-1}=2\}\subseteq\{2,...,n\}$; and this is arbitrary subset with $n\in S$. Indeed if elements of this set are $i_1<i_2<\cdots<i_k=n$ then the path necessarily is $$ [i_1,i_1-1,...,2,i_2-i_1+1,i_2-i_1,...,2,i_3-i_2+1,...,2,...,i_k-i_{k-1}+1,...,2,1]. $$ On the other hand, the permutation corresponding to a set $S$ with elements $i_1<i_2<\cdots<i_k$ where $i_1>1$ and $i_k=n$ is the cycle given by $$ j_1(=1)\mapsto j_2\mapsto\cdots\mapsto j_l\mapsto i_k(=n)\mapsto i_{k-1}\mapsto\cdots\mapsto i_2\mapsto i_1\mapsto1 $$ where $j_1<j_2<\cdots<j_l$ are elements of the complement $\{1,...,n\}\setminus S$.

Thus permutations corresponding to fully returning Dyck paths are those cycles $\sigma$ which satisfy $$ \sigma(\operatorname{desc}(\sigma))=\{1\}\cup\operatorname{desc}(\sigma)\setminus\{n\} $$ where $\operatorname{desc}(\sigma)$ is the descent set of $\sigma$, $$ \operatorname{desc}(\sigma)=\{i\mid\sigma(i)<i\}. $$ Such permutations are uniquely determined by their descent sets, which might be arbitrary sets that can occur as a descent set of a permutation, i. e. subsets $S$ of $\{1,...,n\}$ with $1\notin S$ and $n\in S$.

Also decided to add an illustration for the "almost fully returning" case. To this Dyck path

corresponds this permutation

(click if want to enlarge)

I am not an expert in the field, so perhaps I will express in many words some well-known facts --- sorry for that.

I will get some intrinsic description of Dyck permutations; however, I am not sure whether it is satisfactory for you.

!. I will write the Bruhat decomposition of $C_D$ in the form $P=U_1C_DU_2$, where $U_1$ and $U_2$ are upper-triangular matrices. In this case, $U_1C_D$ is a matrix such that, if we denote by $\sigma(i)$ the leading position in row $i$, then $\sigma$ is a permutation; moreover, it is exactly the Dyck permutation $\sigma_D$ corresponding to $D$. We start with an explicit construction of such $\sigma$ and $U_1$ for a given Cartan matrix $C_D$.

The $i$th row of $C_D$ contains ones at the segment of positions $\{j_i+1,j_i+2,\dots,i\}$ where $j_1=0$, $j_i<i-1$ for $i>1$ and $j_1\leq j_2\leq\dots\leq j_n$. Construct a graph $G$ on the vertex set $V=\{0,1,\dots,n\}$ with edge set $\{g_1,g_2,\dots,g_n$}; the edge $g_i$ connects $j_i\to i$ for each $i=1,2,\dots,n$. The graph is directed, as this provides a convenient language (of in- and out-edges); however, when we will speak about the paths in this graph, we will mean paths disregarding directions of the edges; similarly, the (connected) components will be the weak connected components.

Set $U=\{j_1,j_2,\dots,j_n\}$ (refarded as a set but not multiset). Then (i) each vertex $i>0$ has exactly one in-edge (coming from a smaller vertex), (ii) each vertex not in $U$ has zero out-edges, (iii) the out-neighbours of $0$ are of the form $\{1,2,\dots,q\}$ for some $q\geq 2$, and (iv) all out-neighbourd of $0\neq j\in U$ are of the form $\{p,p+1,\dots,q\}$ for some $j+1<p\leq q$. Moreover, (v) the larger $j\in U$ is, the larger are its our-neighbours.

In particular, our graph is a tree rooted at $0$, where the vertices of $U$ are exactly non-leaves.

For $i\in V$, denote by $G_i$ the spanning subgraph of $G$ with edges $\{g_{i+1},g_{i+2},\dots,g_n\}$. In particularm, $G_n$ has no edges, and $G_0=G$. In each component of $G_i$, choose the maximum vertex, and let $M_i$ be the set of those vertices. Then $|M_i|=i+1$, and $\{n\}=M_0\subset M_1\subset \dots\subset M_n=V$. Denote $M_i\setminus M_{i-1}=\{m_i\}$.

Claim. $\sigma_D(i)=m_i+1$.

Proof. Clearly, $\sigma$ is a permutation of $\{1,2,\dots,n\}$; so we need to construct a matrix $U_1$ such that $U_1C_D$ has the required form.

In order to construct the $i$th row of $U_1$, we need to represent some row with the leading position $\sigma(i)=m_i+1$ as a linear combination of the rows $i,i+1,\dots,n$ of $C_D$ (taking row $i$ with a nonzero coefficient).

When we pass from $G_i$ to $G_{i-1}$, we add an edge corresponding to row $i$ of $C_D$, and two components merge into one; one of them had maximum element $m_i$, another one had maximum element $n_i>m_i$. Now, in $G_i$, there is a path $e_1e_2\dots e_k$ joining $m_i$ to $n_i$ (and passint through the added edge). This path corresponds to a desired linear combination: if $e_s$ corresponds to the row $i_s$, we take this row with coefficient $1$ if this edge in our path is traversed in the direction $j_{i_s}\to i_s$, and $-1$ otherwise. The resulting linear combination provides the row with zeroes and ones, with ones exactly at positions $\{m_i+1,m_i+2,\dots,n_i\}$, as desired. $\Box$

Further we will also use the notion of $n_i$ introduced in this proof.

2. Let us analyze a bit the obtained permutation. Consider an arbitrary $1\leq i\leq n$.

Case 1. Assume first that $j_{i+1}>j_i$ (so, in particular, $i>1$). This means that, in $G$, $i$ is the maximal out-neighbour of $j_i$. Hence, the vertex $j_i$ has no out-neighbours in $G_i$, so $j_i\in M_i$. On the other hand, in $G_{i-1}$ it has an out-neighbour, so $j_i\notin M_{i-1}$; therefore, $j_i=m_i=\sigma(i)-1$ and $\sigma_D(i)=j_i+1<i$ (as $i>1$).

Case 2. Now assume that $j_{i+1}=j_i$. Then, when we pass from $G_i$ to $G_{i-1}$, we connect a component containing $i$ with a component containing $j_i$; the latter also contans $i+1$, so we definitely have $m_i\geq i$ and hence $\sigma_D(i)>i$.

In particular, we have seen that $\sigma$ indeed has no fixed points. Moreover, the mapping $i\mapsto j_i$ (and hence the Dyck path $D$) can be completely reconstructed from the set $F(\sigma)$ of all pairs $(i,\sigma(i)$ with $\sigma(i)<i$ as follows. Choose the minimal $\mu_i\geq i$ such that $\sigma(\mu_i)<\mu_i$. Then $j_i=\sigma(i')-1$.

Notice also that, if we want to get a Dyck path, we need exactly two additional constraints: (a) $j_i<i-1$ for all $i>1$, and (b) if $(i_1,\sigma(i_1))$ and $(i_2,\sigma(i_2))$ are two elements in $F(\sigma)$ with $i_1<i_2$, then also $\sigma(i_1)<\sigma(i_2)$.

This shows the way how to recognize whether $\sigma$ is a Dyck permutation. By $\sigma$ (having no fixed points0, we construct the set $$ F(\sigma)=\{(i,\sigma(i))\colon \sigma(i)<i\} $$ By this set, we reconstruct the mapping $i\mapsto j_i$, check whether it obeys (a) and (b) (obtaining a Dyck path $D$ if they are satisfied), and check whether $\sigma=\sigma_D$ for the obtained $D$.

3. To make this a bit more explicit, we may notice the following.

Condition (b) is easily verifiable for a permutation $\sigma$. Condition (a) merely means that, if $1<\sigma(i)<i$, then there is an $i'$ strictly between $\sigma(i)$ and $i$ such that $\sigma(i')<i'$ (and hence $\sigma(i')<\sigma(i)$ by (b)).

Now, how to check that $\sigma_D=\sigma$. Denote the mapping $i\mapsto j_i$ obtained from $F(\sigma)$ by $\tau$ (in fact, the graph $G$ will contain exactly the edges of the form $\tau(i)\to i$), and revall the notion of $\mu_i$ introduced in the definition of that mapping. Denote $$ Q(i)=\{a\colon \tau^k(a)=i \quad\text{for some $k\geq 0$}\}. $$ Then, for every $i$ with $\sigma(i)>i$, we need to check the following condition. Let $$ m=\max Q(i), \quad n=\max\bigcup_{i<a\leq \mu_i}Q(a). $$ Then $\sigma(i)=\min\{m,n\}+1$.