The set of all words over alphabet $\{0,1\}$ of length $n$ with the forbidden subword 11...1 (of length $k$)


Rade Doroslovački




We enumerate the number of those words of length n over the alphabet $\{0,1\}$ in which the subword consisting of $k$ consecutive 1's is forbidden. This number of words is counted in two different ways, which gives some new combinatorical identities.