2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ These could be called modified Yamanouchi words $\endgroup$ – Duchamp Gérard H. E. Mar 5 '18 at 20:54
  • $\begingroup$ When you say "number of times $a$ appears before $b$", do you mean you count occurrences of $ab$? $\endgroup$ – Vladimir Dotsenko Mar 6 '18 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$ – luw Mar 7 '18 at 2:10
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – luw Mar 7 '18 at 2:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.