count the number of words in a set Consider the words obtained from the alphabet $\{a,b,c\}$, we require that for each $b$ in the word, the number of times that $a$ appears before $b$ should be greater or equal to the number of times that $b$ appears, and the number of times that $a$ and $b$ appear before $c$ should be greater or equal to the number of times that $c$ appears.(For example: $aaabb$ and $aabccc$ are allowed, but $abb$ and $aabcccc$ are not allowed). How to count the words in terms of length?
 A: Consider such a word $w$ of lenght $n$. It is easy to see that the letters $a$ and $b$ in $w$ form a truncated Dyck word: if the number of letters $a$ is $i$ and the number of letters $b$ is $j\leq i$, then there are $\frac{i-j+1}{i+1}\binom{i+j}{j}$ such truncated Dyck words. Similarly, if we replace in $w$ each $a$ or $b$ with the same letter $c'$, then the resulting word over $\{c',c\}$ is a truncated Dyck word; if the number of letters $c$ is $k\leq i+j$, then the number of such truncated Dyck words is $\frac{i+j-k+1}{i+j+1}\binom{i+j+k}{k}$.
Hence, the number of distinct words $w$ of length $n$ equals 
$$\sum_{i+j+k=n\atop i\geq j,\ i+j\geq k} \frac{i-j+1}{i+1}\binom{i+j}{j} \frac{i+j-k+1}{i+j+1}\binom{i+j+k}{k} $$
$$=\sum_{j=0}^{\lfloor n/2\rfloor} \sum_{i=\max\{j,\lceil n/2\rceil - j\}}^{n-j} 
\frac{(i-j+1)(2(i+j)-n+1)}{(i+1)(i+j+1)}\binom{n}{i,\ j,\ n-i-j}.$$
For numerical values and references, see OEIS A151266. It also shows connection with walks in 2D lattice, where words correspond to points $(\#a-\#b, \#a+\#b-\#c)$ with nonnegative coordinates, and thus appending a letter $a$, $b$, $c$ to a word corresponds to steps $(1,1)$, $(-1,1)$, $(0,-1)$, respectively.
