# Number of binary arrays of length n with k consecutive 1's [closed]

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$.

• I suggest migrating this to m.se. – Alexander Burstein Dec 12 '17 at 23:35

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})}.$$
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.
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$.