The set of all the words of length $n$ over any alphabet with the forbidden subword $aa\dots a$ where the letter $a$ is fixed


Rade Doroslovački




The paper gives a special construction of those words of length $n$ over any alphabet $A=\{a_1,a_2,\dots,a_m\}$ in which the subword consisting of $k$ consecutive $a$'s is forbidden, where letter $a$ is fixed from alphabet $A$. This construction gives the number of all these words. This number of words is counted in two different ways, which gives some new families of combinatorial identities.