Enumerating Binary Strings Without K-Runs of Ones

Despite having studied mathematics and computer science for quite some time now, I am still amazed to this day at how the two fields can intersect in profound and unexpected ways.

This post expounds upon one such case, examining how solving a seemingly simple enumeration problem algorithmically convolves interesting mathematical tools and insights.

Want to follow along with code? Check out the GitHub repo for example code in Java and Mathematica!

Without further ado, I present the base problem as follows:

Counting Binary Strings With No Adjacent Ones.

Given a positive integer $N > 0$, determine the number of binary strings of length $N$ which contain no adjacent $1$'s.

For example, if $N = 3$, the strings $000, 010, 101$ would be counted, and the strings $111, 110, 011$ would not be.

If you would like, take a moment to consider an algorithmic approach for computing the result before scrolling down.

Algorithm

As you might have intuited, we can use dynamic programming to enumerate the result.

Let us define our subproblem as follows: $c_{i,j}$ counts the number of valid binary strings of length $i$ such that the last character is $j$. That is, $c_{i,0}$ counts all valid binary strings of length $i$ of the form $S_{i,0} = \langle a_1 a_2 \dots a_{i-1} 0\rangle$.

How would we compute $c_{i+1,0}$ and $c_{i+1,1}$, then?

Let us first consider $c_{i+1,0}$, which counts valid binary strings of the form $S_{i+1,0} = \langle a_1 a_2 \dots a_{i} 0 \rangle$. Since the final character is a $0$, we can include the counts of all valid $i$-long binary strings (ending in either $0$ or $1$) to get the total count of all $S_{i+1,0}$.

For example, suppose $N=3$. The possible valid strings of the form $S_{3,0}$ are in bold below:

$$
\begin{align*}
\textbf{000} & & 001 \\
\textbf{010} & & 011 \\
\textbf{100} & & 101 \\
110 & & 111
\end{align*}
$$

These strings can only be formed by taking valid strings of the form $S_{2,0}$ ($00$, $10$) and $S_{2,1}$ ($01$) and adding a $0$.

For $c_{i+1,1}$, we take a slightly different approach. $c_{i+1,1}$ counts the number of valid strings of the form $S_{i+1, 1} = \langle a_1 a_2 \dots a_i 1 \rangle$. Since the last character is a $1$, it follows that $a_i$ must be a $0$ – which limits us to only including the count of all valid strings of the form $S_{i, 0}$, or $c_{i,0}$.

From our above example ($N = 3$), the valid strings of the form $S_{3,1}$ are shown in bold.

$$
\begin{align*}
000 & & \textbf{001} \\
010 & & 011 \\
100 & & \textbf{101} \\
110 & & 111
\end{align*}
$$

We can therefore functionally define $c_{i,j}$ as follows:
$$
\begin{align*}
c_{i,0} &= c_{i-1,0} + c_{i-1,1}\\
c_{i,1} &= c_{i-1,0}
\end{align*}
$$

And that's that! Now all that's left is our initial conditions and to compute the result for the input parameter, $N$.

For our initial conditions, $c_{1,0}$ and $c_{1,1}$, we note that for one character long strings, neither will produce adjacent ones! So we can just set both to be $1$.

For the final result, we just return the sum of the two cases, $c_{N,0} + c_{N,1}$.

In code, we can write our algorithm as follows:

public static int enumerateBinaryStringsNoAdjacentOnes(int N) {
  int c[][] = new int[N+1][2];
  c[1][0] = c[1][1] = 1;
  
  for (int i = 2; i <= N; i++) {
    c[i][0] = c[i-1][0] + c[i-1][1];
    c[i][1] = c[i-1][0];
  }

  return c[N][0] + c[N][1];
}

If we evaluate this code for increasing values of $N$, you'll observe an interesting pattern.

Number of Binary Strings of Length N With Adjacent Ones:
N=1: 2
N=2: 3
N=3: 5
N=4: 8
N=5: 13
...

That's our handy Fibonacci sequence (shifted by $2$)! Why does it show up here?

Take a look at our definition of $c_{i,j}$ from earlier.

$$
\begin{align*}
c_{i,0} &= c_{i-1,0} + c_{i-1,1}\\
c_{i,1} &= c_{i-1,0}
\end{align*}
$$

This system of equations looks pretty similar if not identical to the Fibonacci recurrence!

$$
\begin{align*}
F_{i+1} &= F_{i} + F_{i-1}\\
F_{i} &= F_{i}
\end{align*}
$$
$$
\begin{pmatrix} F_{i+1} \\ F_{i} \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} F_{i} \\ F_{i-1} \end{pmatrix}
$$

By defining our $c_i$ as a vector, we can then write our dynamic programming formulation as a matrix equation.

$$
\begin{pmatrix} c_{i,0} \\ c_{i,1} \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
\begin{pmatrix} c_{i-1,0} \\ c_{i-1,1} \end{pmatrix}
$$

By then leveraging matrix exponentiation, we can directly compute the result for $N$.

$$
\begin{pmatrix} c_{N,0} \\ c_{N,1} \end{pmatrix} =
\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^N
\begin{pmatrix} 1 \\ 1 \end{pmatrix}
$$

Or, more concisely, $\mathbf{c_N} = \mathbf{Q}^N \mathbf{1}$, where $\mathbf{Q}$ is the Fibonacci matrix and $\mathbf{1}$ is our initial vector of ones.

Asymptotic Complexity

Now that we have shown that computing the total number of length $N$ binary strings with no adjacent ones is effectively the same as computing the $N+2$th Fibonacci number, our runtime can be characterized in terms of Fibonacci algorithm complexities.

The dynamic programming implementation above is slow and operates in linear time $O(N)$. However, we can do better.

I've already gone into detail in my Fibonacci matrix post, but Nayuki over from Project Nayuki elaborates considerably on runtime complexities of Fibonacci implementations.

In short, the asymptotic upper bound for computing the result for $N$-long binary strings is $O(\log N)$ when using matrix exponentiation or fast doubling. (Note: The runtime here is given in terms of BigInteger operations. We are assuming all basic mathematical operations take constant time, regardless of the number values exceeding the size of a standard int). That's pretty fast!

There is another very interesting way to look at solving this problem that I cover below, but first – let's examine generalizations of this problem!

Generalizing to $K$-Runs of Ones

What if we wanted to enumerate binary strings that do not have $K$ consecutive ones, for $K \geq 2$? We've already done this for $K = 2$, but we should be able to extend this to arbitrarily large values of $K$.

As it turns out, the answer still has close ties with our best friend Fibonacci. Let's first attempt an example to identify any patterns.

Example ($K = 3$)

Similar to before, we'll want to apply a dynamic programming approach, where in the subproblem we consider a binary string of length $1 \leq i \leq N$.

However, now that we are looking to avoid counting strings with runs of $3$ consecutive $1$'s, simply keeping track of the last character won't be enough!

In order to determine whether adding a $1$ or a $0$ will create a $3$ run, we'll need to keep track of the last two characters.

So, we'll have four cases:

$$
\begin{align*}
S_{i,00} &= \langle a_1 a_2 \dots a_{i-2} 0 0\rangle\\
S_{i,01} &= \langle a_1 a_2 \dots a_{i-2} 0 1\rangle\\
S_{i,10} &= \langle a_1 a_2 \dots a_{i-2} 1 0\rangle\\
S_{i,11} &= \langle a_1 a_2 \dots a_{i-2} 1 1\rangle\\
\end{align*}
$$

As before, we'll denote the total counts for a string $S_{i,00}$ as $c_{i,00}$, etc.

However, the $S_{i,00}$ and $S_{i,10}$ cases are the same! If the last character is a $0$, it does not matter what the previous two are.

To see why, below is a list of all the valid four character binary strings organized by ending suffix:

$$
\begin{align*}
\mathbf{000}0 && \mathbf{001}0 \\
\mathbf{010}0 && \mathbf{011}0 \\
\mathbf{100}0 && \mathbf{101}0 \\
\mathbf{110}0 && \mathbf{111}0 \\ \\
0001 && 0101 \\
1001 && 1101 \\ \\
0011 && 1011
\end{align*}
$$

Observe that for the set of strings ending in $00$ or $10$, every possible valid prefix (3-character binary string, in bold) appears.

Therefore, we can relabel our suffix "cases" as such:

$$
\begin{align*}
00, 10 &\rightarrow 0 \\
01 &\rightarrow 1 \\
11 &\rightarrow 2
\end{align*}
$$

This re-labeling was chosen intentionally such that the new labels count the number of consecutive $1$'s in the suffix starting at the end of the string.

Therefore, since $c$ only keeps track of the counts of valid strings, we can simply define $$c_{i,0} = c_{i-1,0} + c_{i-1,1} + c_{i-1,2}$$

That takes care of case $0$. For case $1$, where we have a suffix of $01$, we note that we can only include the count for valid strings of length $i-1$ where the final character is a $0$. Thus, $$c_{i,1} = c_{i-1,0}$$

Finally, for case $2$, where we have a suffix of $11$, we can only include the count for valid strings of length $i-1$ where the final character is a $1$. Thus, $$c_{i, 2} = c_{i-1, 1}$$

You can refer to the above listing of valid four-character binary strings to confirm this for yourself.

Writing this all out in matrix notation, we can see a pattern start to emerge.

$$
\begin{pmatrix} c_{i,0} \\ c_{i,1} \\ c_{i,2} \end{pmatrix} =
\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}
\begin{pmatrix} c_{i-1,0} \\ c_{i-1,1} \\ c_{i-1, 2} \end{pmatrix}
$$

Just as before, the first element in the result vector is given by the sum of the $K$ preceding elements. The remaining elements correspond to the the $K-1$ preceding values!

Of course, we can finally enumerate the total count for the $N$-long binary string directly with the following:

$$
\begin{pmatrix} c_{N,0} \\ c_{N,1} \\ c_{N,2} \end{pmatrix} =
\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^N
\begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix}
$$

The Crux

We are now able to extrapolate to cases with arbitrary $K$. Unlike before, I will present the matrix-formulation first – as the generalization is more intuitive in this representation.

$$
\begin{pmatrix} c_{N,0} \\ c_{N,1} \\ c_{N,2} \\ \vdots \\ c_{N,K-1} \end{pmatrix} =
\begin{pmatrix}
1 & 1 & 1 & \cdots & 1 \\
1 & 0 & 0 & \cdots & 0 \\
0 & 1 & 0 & \cdots & 0 \\
0 & 0 & 1 & \cdots & 0 \\
0 & 0 & \vdots & \ddots & 0
\end{pmatrix}_{[K \times K]}^N
\begin{pmatrix} 1 \\ 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}_{[K \times 1]}
$$

To relate this back to the Fibonacci sequence, I now present a variation of traditional Fibonacci, the $r$-Fibonacci sequence.

We define the $k$-Fibonacci sequence ${U_{n}}$ as: $$U_{n} = \sum_{i=1}^k U_{n-i} = U_{n-1} + U_{n-2} + \dots + U_{n-k}$$

for $n \geq k$, with $U_0 = U_1 = \dots = U_{k-2} = 0$ and $U_{k-1} = 1$.

It thus follows that we can define the total number of $N$-long strings without $K$ consecutive $1$'s as the $N+K$th element of the $K$-Fibonacci sequence. Of course, for $K=2$ we simply have the original Fibonacci sequence. For further reading, this relationship between the enumeration of binary strings and the $K$-Fibonacci sequence is further explored by Nyblom [2].

Below is a code implementation of the dynamic programming algorithm for the general case.

public static int countNumberBinaryStringsNoKRun(int N, int K) {
  int c[][] = new int[N+1][K];
  c[1][0] = c[1][1] = 1;
  
  for (int i = 2; i <= N; i++) {
    c[i][0] = sum(c, i-1, 0);
    for (int j = 1; j < K; j++) {
      c[i][j] = c[i-1][j-1];
    }
  }

  return sum(c, N, 0);
}

private static int sum(int c[][], int x, int yStart) {
  int total = 0;
  for (int i = yStart; i < c[0].length; i++) {
    total += c[x][i];
  }
  return total;
}

Asymptotic Complexity

The runtime complexity of the dynamic programming implementation is $O(NK)$. Of course, this is pretty poor performance - so we turn again to our good friend linear algebra for a faster solution.

Using the matrix exponentiation by squaring algorithm, we can trim the runtime complexity down – we obtain $\lfloor \log N \rfloor$ matrix squarings and $\lfloor \log N \rfloor$ matrix multiplications, each of which involves $K^2$ (big) integer products. Therefore, our runtime complexity with exponentiation by squaring is $O(K^2 \log N)$. For small $K$ and substantially large $N$, this is good performance. In particular, if $N = \Theta(2^K)$, then the algorithm's complexity is polynomial in $K$ as opposed to exponential.

I have omitted a formal proof of correctness for the above algorithm from this post, but I encourage you to read Nyblom's paper which treats exploration of the problem with more rigor.

Another Perspective: DFAs and Markov Chains

As I mentioned above, the enumeration problem admits another interesting solution under a slightly different interpretation. This time, we'll borrow from computational complexity theory and use a DFA to enumerate the number of $N$-long binary strings with no adjacent ones.

For an initial example, let us consider a DFA $D$ that accepts the regular language $L_2$ containing all binary strings of length $2$ such that there are no adjacent ones.

$$D = (Q, \Sigma, \delta, q_0, F)$$

We clearly have $\Sigma = \{0, 1\}$. What does our state space look like? We'll want our transition function to represent the appending of a '0' or '1' to the string built while traversing the DFA. Then, we will have $2*2$ intermediate (including final) states, one initial state, and one trap state. We will label the initial state $q_0 = 0$, the remaining states in order from $1\dots 4$, and the trap state $5$.

Then, $Q = \{0, 1, 2, 3, 4, 5\}$, $q_0 = 0$, and $F = \{3, 4\}$.

In designing the transition function, following any pair of consecutive $1$-transitions should lead us to the trap state. This should feel remarkably similar to the design of the dynamic programming approach.

Below is a state diagram and state transition table for $D$.

$$
\newcommand\T{\Rule{0pt}{1em}{.3em}}
\begin{array}{c|c|c}
& \mathbf{0} & \mathbf{1} \\ \hline
0 & 1 & 2 \\
1 & 3 & 4 \\
2 & 3 & 5 \\
3 & 5 & 5 \\
4 & 5 & 5 \\
\end{array}
$$

Now, we want to compute the total number of unique state transition paths that from state $0$ to any of the accepting states. A naive algorithm could involve a depth-first search over all the possible paths, but this would quickly become $O(2^N)$ when we extend this approach to larger $N$.

Instead, we will borrow from Markov to accomplish this much more quickly. Let us assign a uniform probability $0.5$ to each transition in the above state diagram to create a weighted graph $G_D$.

For a random walk over $G_D$, we have the following sparse stochastic matrix:

$$ \mathbf{p} = \begin{pmatrix}
0 & 0.5 & 0.5 & 0 & 0 & 0 \\
0 & 0 & 0 & 0.5 & 0.5 & 0 \\
0 & 0 & 0 & 0.5 & 0 & 0.5 \\
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1
\end{pmatrix}$$

We define $p(i,j)$, the element at the $i$th row and $j$th column of the matrix, to be the probability of transitioning from state $i$ to $j$.

Observe that for the two final states, these transition deterministically to the trap state (as this indicates that the input string is of length greater than $2$).

We now want to know the probabilities of reaching the final states from state $0$ in $2$ steps. Computing $p^2$, we get:

$$\mathbf{p}^2 = \begin{pmatrix}
0 & 0 & 0 & 0.5 & 0.25 & 0.25 \\
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 1 \\
\end{pmatrix}$$

We now take $\sum_{u \in F} p^2(q_0, u) = p^2(0,3) + p^2(0,4) = 0.75$. This means that we have 75% chance of hitting a final state over all possible transition paths from $q_0$. Multiplying $0.75$ by the total number of possible paths, $2^2$, we get $3$.

Turns out, this is the correct value! There are $3$ $2$-long binary strings without consecutive ones.

Looking quickly at the $N=3$ case, we have the following state diagram.

As with before, we generate the stochastic matrix:

$$
\mathbf{p} = \begin{pmatrix}
0 & 0.5 & 0.5 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0.5 & 0.5 & 0 & 0 & 0 \\
0 & 0 & 0 & 0.5 & 0 & 0 & 0 & 0.5 \\
0 & 0 & 0 & 0 & 0 & 0.5 & 0.5 & 0 \\
0 & 0 & 0 & 0 & 0 & 0.5 & 0 & 0.5 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{pmatrix}
$$

Computing $\mathbf{p}^3$, we have:

$$
\mathbf{p}^3 = \begin{pmatrix}
0 & 0 & 0 & 0 & 0 & \frac{3}{8} & \frac{1}{4} & \frac{3}{8} \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1
\end{pmatrix}
$$

Finally, $\sum_{u \in F} p^3(q_0, u) = p^3(0,5) + p^2(0,6) = \frac{5}{8}$. Multiplied by $2^3$ possible $3$-long binary strings, we have $5$ total valid strings! This is what we would expect given our previous results.

Extending this approach to binary strings of length $N$ should not be difficult. The approach is as follows:

General Stochastic Matrix Construction Algorithm

Generate a matrix $p$ that is $(2N + 2) \times (2N + 2)$ in dimension. Set $p(0,1) = p(0,2) = 0.5$. For every odd $i$th row, set $p(i, i+2) = p(i, i+3) = 0.5$. For every even $i$th row, set $p(i, i+1) = 0.5$ and $p(i, 2N+1) = 0.5$. Then set $p(2N-1, 2N+1) = p(2N, 2N+1) = p(2N+1, 2N+1) = 1$.

Analyzing the runtime of this approach will show that it is asymptotically slower than our fast Fibonacci approach from before. If we use exponentiation by squaring, we have $\lfloor \log N \rfloor$ multiplications, each of which takes $N^2$ integer operations... giving us $O(N^2 \log N)$ total runtime (including time to create the stochastic matrix). While not optimal, this brief exercise yields (potentially surprising) insights into how our string enumeration is fundamentally connected to finite state automata! It definitely blew my mind when I was working all of the calculations out. :)

Sample Code

I have uploaded my working sample code for this problem to a GitHub repository.

It also includes a Mathematica notebook for visualizing the Fibonacci matrix products.

Conclusion

Overall, I hope you enjoyed reading through this post! I had a lot of fun writing it. Please let me know if you have any questions! I would love to hear if this helped you in any way. :) Cheers!

Sources/References

  1. Project Nayuki, Fast Fibonacci algorithms, 2015.
  2. Nyblom, M. A., Enumerating Binary Strings without $r$-Runs of Ones, 2012.