Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many bit strings of length $n$, where $n \geq 4$, contain exactly two occurrences of $01$?

share|improve this question

2 Answers 2

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}$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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