How many bit strings of length $n$, where $n \geq 4$, contain exactly two occurrences of $01$?
The number of bit strings with only two occurrences of 01
2 Answers
Any such sequence can be written as:
$1^k0^l1^m0^p1^q0^r$
where $k+l+m+p+q+r=n$ and $l,m,p,q\geq 1$ and $k,r\geq 0$.
But we can see that as the number of ways of writing $n-4$ as the sum of $6$ non-negative integers, which is ${n+1}\choose{5}$.
Use recurrence relations:
Let $a_n$ be the number of sequences containing exactly two occurrences of $01$ ending with $1$.
Denote by $b_n$ the number of sequences containing exactly two occurrences of $01$ ending with $0$.
Denote by $c_n$ the number of sequences containing exactly one occurrence of $01$ ending with $1$. Denote by $d_n$ the number of sequences containing exactly one occurrence of $01$ ending with $0$.
Denote by $e_n$ the number of sequences containing no occurrences of $01$ ending with $1$.
Denote by $f_n$ the number of sequences containing no occurrences of $01$ ending with $0$.
Now you have the following system:
$\left\{ \begin{array} aa_n=a_{n-1}+d_{n-1} \\ b_n=a_{n-1}+b_{n-1}\\ c_n=c_{n-1}+f_{n-1}\\ d_n=c_{n-1}+d_{n-1}\\ e_n=e_{n-1}\\ f_n=e_{n-1}+f_{n-1} \end{array}\right.$ By solving this system (substituting from one equation to the other) you can get to an equation for $a_n$ and $b_n$. You need $a_n+b_n$. From this equation you can easily get that: $e_n=1$ and $f_n=n$. From the third equation you get $c_{n-1}=c_{n-2}+f_{n-2}$. Using the fourth equation you get $c_{n-1}=d_n-d_{n-1}$. Which implies that $d_n-d_{n-1}=d_{n-1}-d_{n-2}+f_{n-2}$. Hence $d_n2-d_{n-1}+d_{n-2}=n-2$, which simplifies the equation.