The set of all the words of length $n$ over alphabet $\{0,1\}$ with any forbidden subword of length three


Rade Doroslovački




The set of all words of length $n$ over the alphabet $\{0,1\}$ with a fixed forbidden sub word of length 3 is enumerated and constructed. The number of words is counted in two different ways, which gives some new combinatorial identities.