In recent work with Michael Albert and Nik Ruškuc, a family of words has arisen which is counted by the Catalan numbers. I've looked at Richard Stanley's [Catalan exercises in EC2](http://www-math.mit.edu/~rstan/ec/catalan.pdf) and his [Catalan addendum](http://www-math.mit.edu/~rstan/ec/catadd.pdf), but I don't see anything that looks to be clearly equivalent, and a bijection to Dyck paths isn't jumping out at me. So I have two questions:



> 
> 1. Has anyone seen these words, or some equivalent objects, before?
> 2. Do you see a nice bijection between these words and any family of "classic" Catalan objects such as Dyck paths or noncrossing partitions?
> 
> 
> 


Let $w$ be a word of length $n$ over the natural numbers (including $0$). Then $w$ lies in our family if it satisfies two rules:


1. For all $k\le n-1$, $w\_{k+1}\ge w\_k-1$.
2. If $w$ contains an $i\ge 1$, then the first $i$ lies between two $i-1$s.


(The word "between" does not imply contiguity, so rule 2 means that when we read $w$ from left to right, we should see an $i-1$ before we see the first $i$, and then at some point after that we should see another $i-1$.)


The number of words of length $n$ that satisfy these conditions is equal to the $n-1$st Catalan number.


For example, the only word of length $2$ that satisfies these rules is $00$, for length $3$ there are two such words, $000$ and $010$, for length $4$ there are five,
$$
0000, 0010, 0100, 0101, 0110,
$$
and for length $5$ there are $14$,
$$
00000, 00010, 00100, 00101, 00110, 01000, 01001,
$$
$$
01010, 01011, 01021, 01100, 01101, 01110, 01210.
$$



A family of words counted by the Catalan numbers
Below my modified answer containing a complete bijection between the above sequences and Dyck paths:


Let $a = (a\_1,\ldots,a\_n)$ be a sequence of $n$ integers. $a$ satisfies Property $A$ if it satisfies your two conditions above. This is


1. $a\_{k+1} \geq a\_k−1$,
2. If $a$ contains an $i \geq 1$, then the first $i$ lies between two $i−1$s.


$a$ satisfies Property $B$ if


1. $a\_{k+1} \leq a\_k+1$,
2. If $a$ contains an $i \geq 1$, then the first $i$ lies between two $i−1$s.


Interchanging neighbours that do not satisfy Property $B1$ does not interfere with Property $A2 = B2$ and should provide a bijection between sequences with Property $A$ and those with Property $B$. E.g. for $n=6$ there are $8$ Property $A$ sequences that do not satisfy Property $B1$:
$$001021, 011021, 010021, 010210, 010211, 010212, 012102, 010221.$$
Interchanges $0$'s and $2$'s where necessary gives
$$001201, 011201, 012001, 012010, 012011, 012012, 012120, 012201.$$


$a$ satisfies Property $C$ if


1. $a\_1 = 0$.
2. $a\_{k+1} \leq a\_k+1$,
3. If $a$ contains an $i\geq 1$, then there is an $i-1$ after the first $i$,


Properties $B$ and $C$ are equivalent since $B2$ implies that $a\_1 = 0$. This then implies that every $i \in a$ has an $i-1$ somewhere to its left, and we can drop this part of condition $B2$ to obtain Property $C3$.


$a$ satisfies Property $D$ if it satisfies $C1$ and $C2$. Sequences with Property $D$ are item $u$ on Stanley's list, and are in natural bijection to Dyck paths (which are here lattice paths from $(0,0)$ to $(n,n)$ that never go below the diagonal $x=y$) by sending a path $D$ to the sequence $a$ where $a\_k$ is the number of complete boxes between $D$ and the diagonal at height $i$ (this is a well-known bijection).


Since Property $C$ is strictly stronger than Property $D$, we now have reached an embedding of Sequences of length $n$ with Property $A$ into Dyck paths of length $2n$.


Next, we apply the ''zeta map'' $\zeta$ as defined in [Jim Haglund's book](http://math.upenn.edu/~jhaglund/books/qtcat.pdf) on $q,t$-Catalan numbers on page 50. 
This map is defined by given a sequence $a = (a\_1,\ldots,a\_n)$ satisfying Property $D$, it returns a Dyck path as follows:


* first, build an intermediate Dyck path (the "bounce path") consisting of $d\_1$ north steps, followed by $d\_1$ east steps, followed by $d\_2$ north steps and $d\_2$ east steps, and so on, where $d\_i$ is the number of $i-1$'s within $a$. For example, given $a = (0,1,2,2,2,3,1,2)$, we build the path $NE\ NNEE\ NNNNEEEE\ NE$ (this is the dashed path on the right of Figure 3 in the reference).
* Next, the rectangles between two consecutive peaks are filled. Observe that such the rectangle between the $k$th and the $(k+1)$st peak must be filled by $d\_k$ east steps and $d\_{k+1}$ north steps. In the above example, the rectangle between the second and the third peak must be filled by $2$ east and $4$ north steps, the $2$ being the number of $1$'s in $a$, and $4$ being the number of $2$'s. To fill such a rectangle, scan through the sequence $a$ from left to right, and add east or north steps whenever you see a $k-1$ or $k$, respectively. So to fill the $2 \times 4$ rectangle, we look for $1$'s and $2$'s in the sequence and see $122212$, so this rectangle gets filled with $ENNNEN$.


The complete path we obtain in thus $NENNENNNENEEENEE$. This map sends the dinv statistic (this is, the number of pairs $k<\ell$ with $a\_k-a\_\ell \in \{0,1\} $) to the area, where the area below the bounce path comes from those pairs with $a\_k-a\_\ell = 0$, and the parts in between from the pairs with $a\_k-a\_\ell = 1$). Moreover, an inner touch point is reached if and only if all $i$'s come after all $i-1$'s within $a$ for any $i$. In the example, this happens only for $0$'s and $1$'s, thus giving one touch point.


Given the last observation, we see that $a$ satisfies Property $C3$ if and only if $\zeta(a)$ touches the diagonal only in the very beginning and in the very end, and nowhere in between.


So we thus reached a bijection between sequences satisfying Property $A$ and Dyck paths that do not have inner returns to the diagonal.


Finally, stripping off the first north and the last east step yields a Dyck path of length $2n-2$, and we have obtained a complete bijection.


In order make every step in my bijection visible, I provided a Sage worksheet implementing each step for a better understanding: <http://sage.lacim.uqam.ca/home/pub/21/>


If anything is unclear or wrong, please let me know so I can try to fix it...


