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.
$\endgroup$ 33 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$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$.
$\endgroup$ $\begingroup$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$$
$\endgroup$
