4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ I suggest migrating this to m.se. $\endgroup$ Dec 12, 2017 at 23:35

3 Answers 3

7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.