# 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?

• These could be called modified Yamanouchi words Mar 5 '18 at 20:54
• When you say "number of times $a$ appears before $b$", do you mean you count occurrences of $ab$? Mar 6 '18 at 10:17
• No, we just count the times that $a$ appears before $b$, they need not to be adjacent, like $"aaacbbcacb"$ is allowed because $a$ appears more times than each $b$, and $a$ and $b$ appear more times than $c$
– luw
Mar 7 '18 at 2:10

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.