Number of binary arrays of length n with k consecutive 1's What is the number of binary arrays of length $n$ with at least $k$ consecutive $1$'s? 
For example, for $n=4$ and $k=2$ we have $0011, 0110, 1100, 0111, 1110, 1111$ so the the number is $6$.
 A: It's easier to count strings that avoid $k$ consecutive $1$'s. Let $a_n$ be the number of those strings of length $n$. Append a digit at the end, $0$ or $1$. The only "bad" strings thus created are those ending on exactly $k$ consecutive $1$'s (i.e. $1^k$ or $\dots01^k$). Thus,
$$
2a_n=a_{n+1}+a_{n-k}, \qquad n\ge k,
$$
and $a_n=2^n$ for $0\le n\le k-1$, $a_k=2^k-1$, so the generating function $A(x)$ for $a_n$ is
$$
A(x)=\frac{1-x^k}{1-2x+x^{k+1}}.
$$
The number of binary strings containing $k$ consecutive $1$'s is $b_n=2^n-a_n$, so the corresponding generating function is
$$
B(x)=\frac{1}{1-2x}-\frac{1-x^k}{1-2x+x^{k+1}}=\frac{(1-x)x^k}{(1-2x)(1-2x+x^{k+1})}.
$$
A: More in general, words of length $n$ with a finite alphabet $A$, that contain (or that avoid, if you like) a given pattern as a factor. The solution of the enumeration problem is given in terms of a rational generating function, which can be easily computed by means of the "autocorrelation polynomial" of the pattern. 
A: Let $a_n$ be the sought number. Consider the first occurence of $k$ consecutive $1$'s in an array of length $n \geq k$. Either they are the first $k$ bits followed by any sequence of $n - k$ bits, or they are preceded by a $0$ preceded by a sequence of $i \geq 0$ bits that do not contain $k$ consecutive bits, and followed by $n - k - 1 - i$ arbitrary bits. This implies $a_n = 2^{n - k} + \sum_{i = 0}^{n - k - 1}(2^i - a_i)2^{n - k - 1 - i}$. Denote $b_n = a_n \cdot 2^{-n}$, and $f(x) = \sum_{n = 0}^{\infty} b_n x^n$ the o.g.f. of $b_n$. After some standard manipulations we arrive at $f(x) = \frac{x^k (2 - x)}{2^{k + 1}(1 - x)^2 - x^{k + 1}(1 - x)}$, and $a_n$ is $2^n / n!$ times $n$-th term of Taylor expansion of $f$.
