number of 10 bit binary numbers that repeat a 1

Question

So I have the following problem: given a set of 10 0s or 1s, find the total number of combinations that have at least one instance of 11 so for instance:

1100000000, 1111111111, and 1101001101

all count, and:

1010010001, 0000000000, and 1010101010

all don't count.

I have tried to look up some information on this, but every source I have found assumed that there was a fixed set of 1s and 0s.

I brute forced the answer with a program, and found it to be 880, but I cant find a way to get this number through a formula that would work for say a set of any length.

I had found a solution at one point using a recursive function, but forgot what it was, and it took me over an hour to find, and seeing as I was expected to solve this problem in just 5 minutes, I don't think it was the intended solution.

Answer 1

You can count the words where a 1 is always followed by a 0 (counting separately the cases where the last digit is 0 or 1), and subtract that from the number of words. To count the words with $k$ ones followed by 0s, ending in 0, think of a set of $10-k$ zeros, of which you choose $k$ zeros which are preceded by ones - there are $\binom{10-k}{k}$ of these. For the words with a 1 at the end, think of a set of $9-k$ zeros, $k$ of which are preceded by a 1 (so there are $k+1$ 1s in total). So in total, there are \begin{align*} \sum_{k=0}^5 \binom{10-k}{k} + \sum_{k=0}^4 \binom{9-k}{k}=144 \end{align*} words with no consecutive 1s, and $1024-144=880$ words which do have consecutive 1s.

(I think your program might be wrong, I used this MATLAB code: num=0;for i = 1 : 2 ^ 10,if ~contains(dec2bin(i),'11'), num=num+1;end,end;1024-num).

Answer 2

Let $T(n,\ell)$ be the number of $n$-bit strings with at least one $11$ for which the rightmost bit is $\ell$, and let $F(n,\ell)$ be the number of $n$-bit strings without at least one $11$, for which the rightmost bit is $\ell$. You want to find $F(10,0)+F(10,1)$.

Observe the following:

$F(n,0)=F(n-1,1)+F(n-1,0)\mbox { (Append 0 to any string with no 11.)}\\ F(n,1)=F(n-1,0)\mbox { (Append 1 to any ends-in-0 string without 11.)}\\ T(n,0)=T(n-1,1)+T(n-1,0)\mbox { (Append 0 to any string with 11.)}\\ T(n,1)=T(n-1,1)+T(n-1,0)+F(n-1,1)\\\mbox { (Append 0 to any string with 11, or append 1 to any string without 11 that ends in 1.)}$

Program an Excel spreadsheet to compute the values of $F$ and $T$ recursively. Below, the green-shaded cells are initialized by enumeration. The blue shaded cells, when summed, give the desired answer.

Answer 3

As Rob Pratt indicated in the comments, the number of binary sequences of length $n$ in which at least two consecutive ones appear can be found by subtracting the number of binary sequences in which no two consecutive ones appear from the $2^n$ binary sequences of length $n$.

We can find a recursion relation for the number of binary sequences of length $n$ in which no two consecutive ones appear. Let $a_n$ be the number of binary sequences of length $n$ in which no two consecutive ones appear.

Since the empty sequence has no two consecutive ones, $a_0 = 1$. Since any sequence of length $1$ cannot have two consecutive ones, $a_1 = 2$.

A sequence of length $n$ in which no two consecutive ones appear must either begin with $0$ or $10$. A sequence of length $n$ in which no two consecutive ones appear that begins with $0$ can be followed by any of the $a_{n - 1}$ sequences of length $n - 1$ in which no two consecutive ones appear. An sequence of length $n$ in which no two consecutive ones appear that begins with $10$ can be followed by any of the $a_{n - 2}$ sequences of length $n - 2$ in which no two consecutive ones appear. Hence, we have the recursion relation $$a_n = a_{n - 1} + a_{n - 2}$$ Using the initial conditions \begin{align*} a_0 & = 1\\ a_1 & = 2 \end{align*} we obtain $a_{10} = 144$, so the number of binary sequences of length $10$ in which no two consecutive ones appear is $2^{10} - 144 = 1024 - 144 = 880$.

In general, $a_n = F_{n + 2}$, where $F_k$ is the $k$th Fibonacci number.

Hence, the number of binary sequences with at least two consecutive ones is $2^n - F_{n + 2}$.