2
$\begingroup$

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$
3
  • $\begingroup$ You have to repeat if you only have two possible options but five places you must fill. $\endgroup$
    – fleablood
    Jun 14, 2016 at 3:14
  • $\begingroup$ 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. $\endgroup$
    – André Nicolas
    Jun 14, 2016 at 3:15
  • $\begingroup$ 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). $\endgroup$
    – fleablood
    Jun 14, 2016 at 3:20

3 Answers 3

Reset to default
1
$\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$ These strings are often called Fibbinaries, for obvious reasons. $\endgroup$
    – Rick Decker
    Jun 14, 2016 at 13:45
0
$\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$
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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