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

7more comments