How many bit strings of length $12$ have a substring $01$?

Question

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$?

Answer 1

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)$.

Answer 2

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$.

Answer 3

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.

Answer 4

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}$$

Answer 5

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.