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...
(Not a real answer, just a conjecture)
Let $w$ be the Pansiot word on $4$ letters defined here :
J.J. Pansiot, A propos d'une conjecture de F. Dejean sur les répétitions dans les mots, Discrete Applied Mathematics Volume 7, Issue 3, March 1984, Pages 297–311
in French, or also in
J. Moulin Ollagnier, Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters, Theoretical Computer Science, Volume 95, Issue 2, 30 March 1992, Pages 187–205.
This word proves Dejean's Conjecture for $4$ letters, that is:
it avoids fractional repetitions of exponent greater than $7/5$, and so it is also three-halves-free.
$$w=abcdbadcbdacdbcadcbacdabdcadbcdacbadcabdacdbadcbdabcadbacdab...$$
Conjecture Theorem
Let $h(a)=aabbaccabc$, $h(b)=aacbacbacc$, $h(c)=abbaaccbbc$, $h(d)=abcaacbbcc$.
Then $h(w)$ is a three-halves-free word on $3$ letters.
I checked up to size 412030. I do not tried to prove the result, but maybe the proof is simple and "standard" (suppose that the image has a three-halves, then prove that the pre-image has a three-halve).
edit:
The proof is easy. $h$ is $10$-uniform and is synchronizing, that is for every $x,y,z\in\{a,b,c,d\}$, $h(x)$ is not a proper infix of $h(yz)$. Thus, if a factor $XYX$ of $h(w)$ is a three-halve, then either $XYX$ is small (of size at most $18\times 3$), or $\vert X \vert = \vert Y \vert$ is a multiple of $10$. There are only a finite number of "small" factors to check.
Now, if we are in the second case, and if $\vert X \vert$ if big (at least $42$), then $XYX$ has a unique de-substitution in $w$, and $w$ has a factor $X'Y'X'$ with $\vert Y' \vert / \vert X' \vert > 2/5$. Thus $w$ has a repetition of exponent greater that $7/5$, and we have a contradiction with the fact that $w$ is a Dejean word (i.e. it is $7/5+$-free).
Best Answer
Here are some deep facts relating to binary cfw's:
1) The set of right infinite binary cube-free words is a perfect set in the topological sense: For any given such sequence, there is a distinct one which agrees with it to the nth letter. In particular, there are uncountably many binary cfw's.
2) Given any finite binary sequence, it is decidable whether it extends to an infinite binary cube-free word.
3) The number of (finite) binary cfw's of length n grows exponentially with n.
These results (and analogous ones for k-power free words over various alphabets) are proved in
http://dl.acm.org/citation.cfm?id=873885 and http://www.sciencedirect.com/science/article/pii/0195669895900519