How many binary sequences of length n are there that contain exactly m occurrences of the pattern 01? I thought there were n-1 places between the first and last digit.
In these places I hypothesized there are switches that change (from 0->1 or 1->0)
For {First,Last}={00,01,10,11} -> 4 ways 
I ask an answer for the first case mostly (I think the rest will be similar)
Since there are m patterns of 01 how many switches are there?
And how many ways are there to pick out of n-1? 
 A: Method I
$\require{enclose}
\newcommand{\bitP}[1]{\enclose{box}{#1}}
$Consider following encoding of $n$-bit binary strings
$$\bitP{a_0 a_1 a_2 \ldots a_{n-1}} \mapsto \bitP{b_0 b_1 b_2\ldots b_{n-1}}$$
defined by
$$b_k = \begin{cases} a_k, &k = 0\\ a_k \oplus a_{k-1}, & 1 \le k \le n-1\end{cases}$$
where $\oplus$ stands for logical exclusive or between two bits. 
In order for $\bitP{a_0 a_1 a_2 \ldots a_{n-1}}$ to have exactly $m$ copies of $\bitP{01}$, 
there are four possibilities.
Let $N_m$ be the numbers of $\bitP{1}$ among the $n-1$-bit binary string $\bitP{b_1b_2\ldots b_{n-1}}$, the four possibilities can be summarized by following table.
$$\begin{array}{cl:l}
b_0 & N_m & \text{e.g.} (n=6, m=2) \\
\hline
0 & 2m - 1 & \bitP{010111} \mapsto \bitP{011100}\\
0 & 2m     & \bitP{010100} \mapsto \bitP{011110}\\
1 & 2m     & \bitP{101011} \mapsto \bitP{111110}\\
1 & 2m + 1 & \bitP{101010} \mapsto \bitP{111111}\\
\end{array}$$
Base on this, we find the number of $n$-bit binary strings with exactly $m$ copies of $\bitP{01}$ is give by 
$$
\binom{n-1}{2m-1} + \binom{n-1}{2m} + \binom{n-1}{2m} + \binom{n-1}{2m+1}\\
= \binom{n}{2m} + \binom{n}{2m+1} = \binom{n+1}{2m+1}
$$
Method II - generating function.
Instead of looking at the collection of $n$-bit binary strings and ask how many of them
has exactly $m$ copies of $\bitP{01}$. We look at the collection of binary strings
with exactly $m$ copies of $\bitP{01}$ and ask how many of them has length $n$.
The collection of binary strings with exactly $m$ copies of $\bitP{01}$ can be described
by following regular expression
$$1\verb/*/\;(\;0\verb/+/\;1\verb/+/\;)\{m\}\;0\verb/*/\tag{*1}$$
where 


*

*$X\verb/*/\;$ means the pattern $X$ is repeated zero to any number of times.

*$X\verb/+/\;$ means the pattern $X$ is repeated one to any number of times.

*$X\{m\}\;$ means the pattern $X$ is repeated exactly $m$ times. 


To count the number of bit strings with length $n$, we assign to each piece
in the regular expression $(*1)$ by a power series in some indeterminate $t$.
$$\begin{array}{ccl}
1\verb/*/\; & \leftrightarrow & \frac{1}{1-t} = 1 + t + t^2 + \ldots\\
0\verb/+/\; & \leftrightarrow & \frac{t}{1-t} = t + t^2 + \ldots\\
1\verb/+/\; & \leftrightarrow & \frac{t}{1-t} = t + t^2 + \ldots\\
0\verb/*/\; & \leftrightarrow & \frac{1}{1-t} = 1 + t + t^2 + \ldots
\end{array}$$
In general, if a pattern allows a bit to repeat $r$ times, we attach a term $t^r$ to it.
Combine these, we obtain following generating function corresponds to $(*1)$.
$$\frac{1}{1-t}\left(\frac{t}{1-t} \frac{t}{1-t}\right)^m\frac{1}{1-t} = \frac{t^{2m}}{(1-t)^{2m+2}} 
= \sum_{k=0}^\infty \binom{2m+1+k}{k} t^{k+2m}
\tag{*2}$$
If one expand the RHS as a power series of $t$, one will find the terms with power $t^n$ 
are in an one to one correspondence with those $n$-bit binary strings matching the regular expression $(*1)$. This means the number we want is the coefficient of $t^n$ in $(*2)$. i.e.
$$\binom{2m+1+(n-2m)}{n-2m} = \binom{n+1}{n-2m} = \binom{n+1}{2m+1}$$
which matches what we get by another method.
A: Your idea is good.  One case is that the string starts with $0$ and ends with $0$; in this case it'll have to go up $m$ times and down $m$ times, starting with an up, then alternating between down and up, ending with a down.  So you just get to (have to) choose the $2m$ switching points, and there are $\binom{n-1}{2m}$ ways to do that.  I leave the other cases for you, as you requested.
