Finding the number of strings which do not contain a certain substring... I want to know the method of solving the following problem:
"How many binary strings of length $10$ are there each of which does not contain the pattern '$110$' ?
 A: There is a mechanical procedure for calculating these things (the number of strings of a given length not containing a fixed, finite set of substrings).  Form the de Bruijn graph, where the vertices are binary strings of length $3$, and there is an arrow from $v$ to $w$ if all but the first bit of $v$ matches all but the last bit of $w$ (e.g. $110 \to 101$).
Note that a $k$-step walk on this graph represents a unique string of length $k+3$ in a natural way, with each vertex corresponding to a substring of length $3$.  One can therefore count strings just by taking powers of the (directed) adjacency matrix.
Of course we already know how many strings of length $n$ there are without any of this rigamarole.  But now notice we can delete any vertices containing $110$ (in this case just one vertex), and the smaller graph represents all strings not containing $110$.  The powers of the resulting matrix then reveal the exact number that you seek, and the largest (Perron-Frobenius) eigenvalue describes the exponential growth rate.
Edit: A slight variation that makes the calculations a bit easier is to use strings of length $2$ instead, labelling edges with the strings of length $3$ and deleting any edge containing $110$.
Now we are looking for walks on a graph with only $4$ vertices, whose adjacency matrix looks like
$$ \begin{bmatrix}1&1&0&0\\0&0&1&1\\1&1&0&0\\0&0&0&1\end{bmatrix},$$
and whose 8th power is
$$  \begin{bmatrix}21&21&13&33\\13&13&8&21\\21&21&13&33\\0&0&0&1\end{bmatrix}.$$
This lets us read off the number of strings not containing $110$ which start and end with any given combination of two bits (for instance there is only one starting with $11$, which also ends with $11$).
Update: A less generic but more "clever" way to solve this is to note that the condition "does not contain $110$ as a substring" is equivalent to being of the form $x1^*$ where $x$ does not contain $11$ as a substring.  If you walk along the string and it contains $11$ anywhere, then to avoid $110$ every digit to the right of $11$ must also be a $1$.  This makes it fairly easy to see, with some careful logic, the equivalence to $F_{n+3}-1$ via Fibonacci coding.
A: Let $R(n)$ be the number of $n$ bit strings not including $110$ and ending in $0$, $S(n)$ be the number of $n$ bit strings not including $110$ and ending in $01$ (or just being the single bit $1, T(n)$ be the number of $n$ bit strings not including $110$ and ending in $11, U(n)$ be the number of $n$ bit strings including $110$.  Then you have $R(1)=1,S(1)=1,T(1)=0,U(1)=0\\R(n)=R(n-1)+S(n-1)$ 
because you can add a $0$ to the end of any $R,S,T$ string of length $n-1$ to get an $R$ string of length $n$.  Now figure out the recurrences for $S,T,U$ and evaluate.  A spreadsheet with copy down will make it easy.
