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?
3
-
2$\begingroup$ These could be called modified Yamanouchi words $\endgroup$– Duchamp Gérard H. E.Commented Mar 5, 2018 at 20:54
-
$\begingroup$ When you say "number of times $a$ appears before $b$", do you mean you count occurrences of $ab$? $\endgroup$– Vladimir DotsenkoCommented Mar 6, 2018 at 10:17
-
$\begingroup$ 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$ $\endgroup$– luwCommented Mar 7, 2018 at 2:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Mar 6, 2018 at 5:21
-
$\begingroup$ Thank you! This is a great explanation. Actually the connection you pointed out is my original question, and I just tried to solve it using words counting. (If you consider the endpoint and the length of path, the number of times that each step appear is fixed, only order matters. Since I want the path to stay in the first quadrant, there are those restrictions of words) $\endgroup$– luwCommented Mar 7, 2018 at 2:29