How many sequence of length twelve are there consisting of eight ones and four zeros, such that there are no two consecutive zeros. I'm working through this problem and I haven't been able to make any progress. The textbook provides the answer of $ {9 \choose 4}$ but I'm not sure as to how they got this result. 
 A: *

*If you write the $8$ $1's$ horizontally beside each other, the number of possible places to put zeros between them or at the left-most or right-most position is $\color{blue}{9}$

*The number of ways to choose $4$ of these $9$ places to put exactly one $0$ is $\color{blue}{\binom{9}{4}}$
A: Consider the two atoms: $x\to01$ and $y\to1$. If we arrange $4$ $x$s and $5$ $y$s, we get all the allowable strings suffixed with a $1$. For example:
$$xxxyyxyyy\leftrightarrow010101110111\color{#AAA}{1}$$
$$yyxyyyxxx\leftrightarrow110111101010\color{#AAA}{1}$$
$$yxyxyxyxy\leftrightarrow101101101101\color{#AAA}{1}$$
So the number of possible strings is the number of ways to arrange the $4$ $x$s and $5$ $y$s: $\binom{9}{4}$.
A: Here is a more sophisticated way to solve this, using DFAs. We can construct a state machine accepting the language of all strings without two consecutive zeroes as follows:


*

*There are two states, $q_0$ and $q_1$.

*The initial state is $q_1$.

*At state $q_0$, there is a $1$-transition leading to $q_1$.

*At state $q_1$, there is a $0$-transition leading to $q_0$, and a $1$-transition leading to $q_1$.


The transition matrix ("transfer matrix") corresponding to this DFA is as follows, where $0$-transitions are indicated by the variable $x$ and $1$-transitions are indicated by the variable $y$:
$$
\begin{pmatrix}
0 & x \\
y & y
\end{pmatrix}
$$
The number of words of length $n$, counted according to the number of $0$s and $1$s, is
$$
\begin{pmatrix} 1 & 1 \end{pmatrix}
\begin{pmatrix}
0 & x \\
y & y
\end{pmatrix}^n
\begin{pmatrix} 0 \\ 1 \end{pmatrix}
$$
For example, when $n = 12$ we get
$$
7x^6y^6 + 56x^5y^7 + 126x^4y^8 + 120x^3y^9 + 55x^2y^{10} + 12xy^{11} + y^{12}.
$$
The coefficient of $x^4y^8$ is what you wanted.

Why do we need this very elaborate method? Since it works whenever your constraint can be described by a succinct DFA. For example, you can answer questions of the form "how many strings of length 100 have exactly 50 zeroes and 50 ones, and no copies of 000 or 1101?"
The calculation will amount to a dynamic programming algorithm. Using DFAs is just a principled way of designing the dynamic programming recurrence.
