A family of words counted by the Catalan numbers 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 and his Catalan addendum, 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:

  
*
  
*Has anyone seen these words, or some equivalent objects, before?
  
*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:


*

*For all $k\le n-1$, $w_{k+1}\ge w_k-1$.

*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: I'm not sure if the following helps, but you can count such sequences by the number of $0$s, $1$s, $2$s, etc. If you have a composition of $n$, $n = c_0 + c_1 + \ldots +c_k$ with $c_i \ge 1$ then the number of such sequences is $$\prod_{i=1}^k  \bigg({c_{i} + c_{i-1} - 1\choose c_{i}}- 1\bigg)$$. That is, if you ignore all values which are greater than $i$, the number of ways of placing the $i$s is ${c_{i} + c_{i-1} - 1\choose c_{i}}- 1$. You can place the $i$s in clumps to the left of the non-initial $i-1$s or the end, distributing $c_i$ $i$s into $c_{i-1}$ locations, except that not everything can go at the end.
There is a way to turn such a sequence into a restricted sequence of parentheses so that each $i$ corresponds to a pair of parentheses at level $i$. For each $0$, insert $()$. Then for each $1$ between the $k$th $0$ and the next/end, insert $()$ into the pair corresponding to the $k$th $0$. 
For example: $0102210032$. I'll show the parentheses added in each step as square brackets.
$c_0 = 4: [][][][]$  
$c_1 = 2 = 1+1+0+0: ([])([])()()$
$c_2 = 3 = 2+1: (([][]))(([]))()()$
$c_3 = 1 = 0+1+0: ((()([])))((()))()()$
This resembles some of the restrictions on Dyck paths of length $n$ counted by $C_{n-1}$ in the Catalan addendum. 
A: This answer summarizes partial progress which was interesting enough to lead to its own question.
Consider sequences which only obey your first condition. Call these $L$-words. ($L$ stands for Lukasiwiecz, because they are more or less the partial sums of the sequences studied by Lukaswiecz.)
There are Catalan many $L$-words. Given an $L$-word, let $p$ be the number of pairs $(i,i+1)$ for which your second rule is violated. So we want to count pairs with $p=0$. Also, let $q+1$ be the number of occurrences of $0$ in the $L$-word. Here is a table:
$$\begin{matrix}
L-\mbox{word} & p & q \\
000 & 0 & 2 \\
010 & 0 & 1 \\
001 & 1 & 1 \\
011 & 1 & 0 \\
012 & 2 & 0 \\
\end{matrix}$$
It appears that the number of $L$-words of length $n$ with given values of $p$ and $q$ only depends on $(p+q, n)$! See my question for more.
A: This is only a partial answer, and may very well be a dead end, but
at least it's long-winded.
First consider only binary words.  In this case, condition 1 is
vacuous and the only length-$n$ words omitted are of the form
$0^a1^{n-a}$ for $a \geq 1$.  This leaves $2^n-n$ valid such words.
Here's a simple bijection (probably already written down somewhere)
from this set of binary words to Dyck paths of semilength $n$ having
at most one long ascent (i.e., at most one maximal sequence of at
least two consecutive up steps): Suppose the word $w$ has $1$ at positions
$i_1 < i_2 < \cdots < i_k$.  Then $w$ maps to a Dyck path that starts
with $i_1-1$ copies of $UD$, followed by its long ascent, followed in
turn by intermittent $U$s marked by the $i_j$.  Specifically, $w$ maps
to $$D = (UD)^{i_1-1}U^{n-i_1-k+2}Dv_{i_1+1}v_{i_1+2}\cdots v_{n}$$
where $v_j = UD$ if $j = i_m$ for some $m$ and $v_j = D$ otherwise.
The important point here is that the length of the long ascent is determined by the number of $0$s following the initial $1$.
Let's broaden scope a little, but do so from the Dyck path side.
Consider Dyck paths for which any long ascent has at most (i.e.,
exactly) two $U$ steps.  These can be mapped to words satisfying
conditions 1 and 2 (I think) in an invertible manner.  Start
scanning the Dyck path from the left, writing down $0$s for each $UD$.
At the first ascent (necessarily of the form $UUD$), write a $1$.  For
each subsequent column, up to the first return to $y=x$ after
this point, write down the number of area cells in that column.
After that first return, write down the number of area cells plus $1$.
For example (placing a period at the first return after the first long
ascent), $UDUUDUUDDUDUUDDD.UUDDUDUUDUDD$ maps to $01211210.211221$.
For the general case, some of the long ascents are going to be longer than length $2$.  My hope is that one can keep track of how the various long ascents have been lengthened using the values of $w$ corresponding to the additional $D$ steps that must be present to have a Dyck path.
A: 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


*

*$a_{k+1} \geq a_k−1$,

*If $a$ contains an $i \geq 1$, then the first $i$ lies between two $i−1$s.


$a$ satisfies Property $B$ if


*

*$a_{k+1} \leq a_k+1$,

*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


*

*$a_1 = 0$.

*$a_{k+1} \leq a_k+1$,

*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 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...
