# How many bit strings of length $5$ do not have consecutive $1$'s?

How many bit strings of length 5 do not have consecutive 1's?

I'm trying to think of a way to calculate how many ways we can arrange a string of length 5 starting with the first position (or index).

I feel like in this case we would use a permutation because order matters. I also believe repetition is not allowed (hence no consecutive 1's) here? Please correct me if I'm going about this wrong.

• You have to repeat if you only have two possible options but five places you must fill. Jun 14, 2016 at 3:14
• This type of problem has been dealt with a number of times on MSE. For length $5$, a careful organized listing is feasible. I think you will find there are $13$. For a couple of more general ideas, you could look at this recent question. Jun 14, 2016 at 3:15
• Repetitions are mandatory so permutations are not a good idea. Strings should nearly always be lists. In this case you can count the number of strings with 5 1s (0), 4 1s (0), 3 1s (1, do you know why) 2 1s (??) and 1 1 (5; for obvious reasons). Jun 14, 2016 at 3:20

We can solve the problem recursively.

Let $a_n$ denote the number of permissible bit strings of length $n$.

A bit string of length $1$ cannot have two consecutive ones. Since there are two ways to fill the digit, $a_1 = 2$.

The only bit string of length $2$ that has two consecutive ones is $11$. Since there are two ways to fill each of the two digits in the bit string, $a_2 = 2 \cdot 2 - 1 = 3$.

Any permissible bit string of length $n + 1$ that ends in $0$ can be formed by by appending a $0$ to the end of a permissible bit string of length $n$, of which there are $a_n$.

For a bit string of length $n + 1$ to end in a $1$, the entry in the $n$th position must be a zero. Thus, any permissible bit string of length $n + 1$ that ends in a $1$ can be formed by appending the bit string $01$ to a permissible bit string of length $n - 1$, of which there are $a_{n - 1}$.

Thus, we have the recurrence relation \begin{align*} a_1 & = 2\\ a_2 & = 3\\ a_{n + 1} & = a_n + a_{n - 1}, n \geq 2 \end{align*} You can use the recurrence relation to determine $a_5$, the number of bit strings of length $5$ that do not have two consecutive ones.

• These strings are often called Fibbinaries, for obvious reasons. Jun 14, 2016 at 13:45

Listing all binary strings of length $5$ satisfying the condition should work for a problem of this small a size. Or, you can find the number of binary strings of length $5$ that have consecutive 1's and subtract that number from $32$.

Suppose there are two $1's$ , and so three $0's$,
the two $1's$ can be inserted at the uparrows in $\binom42$ ways, as shown under:
$\uparrow 0 \uparrow 0 \uparrow 0\uparrow\;\;$ which generalizes to $\binom{n-k+1}{k}$ for $k\;\; 1's$

For $n = 5$, $k$ can be $\le3$, thus $$\text{answer}=\sum_{k=0}^3 \binom{6-k}{k}= 13$$