How many bit strings of length $12$ have a substring $01$? My question is should it be $11C2$ or should it be $11C1$?
Since $01$ are connected together, I take them as a single unit and there are $11$ different positions where they can be placed. Is the answer $11C1$? 
 A: It might be easier to ask how many bit strings of length $n$ do not have the substring '01'.
I think of the bit string as a little plot, so $0100$ would be the graph $(0,0),(1,1),(2,0),(3,0)$. The substring $01$ corresponds to an upward jump in the graph. It follows that the only graphs that do not have an upward jump are those of the form $1^* 0^*$ (of the appropriate length, of course).
Hence the number of bit strings of length $n$ do not have the substring '01' is
$n+1$ (all ones, all ones except for last place, ..., all zeros).
Hence
the answer is $2^n-(n+1)$.
A: Easier way to answer this: there are $2^{12}$ bitstrings. How many bitstrings don't have a substring $01$? To answer this: This means that a bitstring has to be either all $0$s, all $1$s, or has $n$ leading $1$s and $12-n$ following $0$s. (Like $100000000000$ through $111111111110$.)
There's only one bitstring that's all $0$s, and there's only one bitstring that's all $1$s. Then there are $11$ bitstrings for the leading-$1$-and-following-$0$ case. (Just count $100000000000$, $11000000000$, etc., or show it arithmetically.)
So there are $13$ bitstrings that don't have a $01$ substring. So there are $2^{12} - 13$ bitstrings that have a $01$ substring.
A: The critical observation is that a string that lacks the substring $01$ can only be a (possibly empty) substring of $1$'s, followed by a (possibly empty) substring of $0$'s.  If any $1$ comes after any $0$, then there must be a $01$ substring.  Therefore, there are only $13$ different bit strings that fail to have a substring $01$, and the total number of strings that satisfy the original condition is $2^{12}-13$.
A: I would attack this problem from left to right:
Let's suppose that my string starts with 0, then we have a lot of possibilities that my string have the substring 01, those are $(2^{11} - 1)$ (we have all the $2^{11}$ possibilities, except when all the $11$ bits left are all 0s).
The next step I would take is supposing that my string starts with 10, then we have another $(2^{10} - 1)$ possibilities, then we suppose that it starts with 110, and so on...
At the end (last steps), my string starts with 11111111110; ($10$ 1s), so I have $2^1 - 1=1$ possibility for my string having the substring 01, that's when my last bit is 1.  Then I would have my beginning string like 11111111110 ($11$ 1s), and there I have $2^0 - 1 = 0$ possibilities for having the 01 as a substring, and that's obvious because I have no available bits, and my string doesn't have the substring 01.  And finally 111111111111 ($12$ 1s) does not have the string '01` as a substring either.
So the answer is 
$$\begin{align}
(2^{11} - 1) + (2^{10} - 1)+ & \ldots + (2^0 - 1) \\ 
&= (2^{11} + 2^{10} + \ldots + 2^0) - \overbrace{(1+1+ \ldots +1)}^{12 \text{ times}} \\ 
&= (2^{12} - 1) - 12 \\
&= 2^{12} - 13 = 4083
\end{align}$$
A: The number of strings with the first $01$ occurring at the $1$st position:


*

*$01XXXXXXXXXX$

*Therefore, it is $1\cdot2^{10}$



The number of strings with the first $01$ occurring at the $2$nd position:


*

*$001XXXXXXXXX$

*$101XXXXXXXXX$

*Therefore, it is $2\cdot2^{9}$



The number of strings with the first $01$ occurring at the $3$rd position:


*

*$0001XXXXXXXX$

*$1001XXXXXXXX$

*$1101XXXXXXXX$

*Therefore, it is $3\cdot2^{8}$



The number of strings with the first $01$ occurring at the $4$th position:


*

*$00001XXXXXXX$

*$10001XXXXXXX$

*$11001XXXXXXX$

*$11101XXXXXXX$

*Therefore, it is $4\cdot2^{7}$



And so forth...
So the general formula is $\sum\limits_{n=1}^{11}n\cdot2^{11-n}=4083$.
Since the total number of strings is $2^{12}=4096$, there is probably an easier way to derive this.
