Question

how many 10 bit binary strings are there none of which contains the pattern '110'

Answer 1

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→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