How to determine the number of combinations If there is n length sequence of 0's and 1's . Out of all possible sequences, how do do you determine the the number of sequences that does not contain the pattern 1011 in them ?
 A: Let $a_n$ be the number of binary sequence of length $n$ that do not contain the string $1011$; call such sequences good. Let $b_n$ be the number of good sequences that end in $101$, $c_n$ the number that end in $10$, and $d_n$ the number that end in $1$. 
To make a good sequence of length $n+1$, you can append either $0$ or $1$ to any good sequence of length $n$ except one that ends in $101$, so $a_{n+1}=2a_n-b_n$. To make a good sequence of length $n+1$ that ends in $101$, you must append a $1$ to a good sequence of length $n$ that ends in $10$, so $b_{n+1}=c_n$. To make a good sequence of length $n+1$ that ends in $10$, you must append a $0$ to a good sequence of length $n$ that ends in $1$, so $c_{n+1}=d_n$. And to make a good sequence of length $n+1$ that ends in $1$, you must append a $1$ to a good sequence of length $n$ that does not end in $101$, so $d_{n+1}=a_n-b_n$. Thus,
$$a_{n+1}=2a_n-b_n\;,$$
and
$$b_{n+1}=c_n=d_{n-1}=a_{n-2}-b_{n-2}\;,$$
or, after shifting the indices,
$$\begin{align*}
a_n&=2a_{n-1}-b_{n-1}\tag{1}\\
b_n&=a_{n-3}-b_{n-3}\;.\tag{2}
\end{align*}$$
From $(1)$ we get $a_{n-3}=2a_{n-4}-b_{n-4}$ and hence $a_{n-4}-b_{n-4}=a_{n-3}-a_{n-4}$, and from $(2)$ we have $b_{n-1}=a_{n-4}-b_{n-4}$; substituting into $(1)$ yields the recurrence
$$a_n=2a_{n-1}-(a_{n-4}-b_{n-4})=2a_{n-1}-a_{n-3}+a_{n-4}\;,$$
with initial values $a_k=2^k$ for $k=0,1,2,3$. This confirms that the sequence is OEIS A049864, as suggested by Gerry Myerson in the comments, but shifted two places to the left, with without the first two terms of that sequence. No nice closed form is given. 
A: Inclusion exclusion. Mouseover the grey area for the [horrible] series. 

There are $\displaystyle\sum_{k=0} (-1)^kc_k$ length $n$ strings without $1011$. $c_0=2^n$ sequences have length $n$. In any sequence with $1011$ there are $2^{n-4}$ possibilities for the remaining bits, and $n-3$ places where the $1011$ can start, so $c_1=2^{n-4}(n-3)$ or $0$ if $n<4$. Sequences with two $1011$s have been over-counted, and the two $1011$s may overlap; there are $\displaystyle \sum_{k=1}^{n-7}n-5-k= (n-7)(n-5)-\frac{1}2(n-7)(n-6)$ ways to place them and $2^{n-8}$ ways to place the remaining bits. Subsequent $c_k$ are found similarly.  

