Solution: 2018 Fall Midterm - 11

Author: Michiel Smid

Question

A bitstring is called 00-free, if it does not contain two 0's next to each other. In class, we have seen that for any $m \geq 1$, the number of 00-free bitstrings of length $m$ is equal to the $(m+2)$-th Fibonacci number $f_{m+2}$.
What is the number of 00-free bitstrings of length 55 that have 0 at position 9, and 1 at position 40? (The positions are numbered $1,2,\dots,55$.)

(a)

$f_7 \cdot f_{29} \cdot f_{15}$

(b)

$f_{10} \cdot f_{32} \cdot f_{18}$

(c)

$f_9 \cdot f_{31} \cdot f_{17}$

(d)

$f_8 \cdot f_{30} \cdot f_{16}$

Solution

Because there is a 0 at position 9, there must be a 1 at position 8 and 10 to avoid a 00.

It looks something like this: …, 1, 0, 1, …, 1, …

The number of 00-free bitstrings made from the first 8 bits $ \text{bit positions 1 to 7} $ is $ f_{7+2} $.

The number of 00-free bitstrings made from the 29 bits $ \text{bit positions 11 to 39} $ between the second and third fixed 1’s is $ f_{29+2} $.

The number of 00-free bitstrings made from the last 15 bits $ \text{bit positions 41 to 55} $ is $ f_{15+2} $.

Thus, the number of 00-free bitstrings with the above conditions is $ f_{9} \cdot f_{31} \cdot f_{17} $.