Question:
Find the recurrence relation for the number of bit strings that contain the string $01$.
Attempt:
Since $01$ can appear in a lot of places, I focused on instances without $01$ first.
Bit strings without $01$ in a bit string of length $n$. Let $XX\dots X$ be bit string without $01$:
- $XX\dots X0$
- $1XX\dots X$
Thus we know we acquire twice more bit string without $01$ from length of $n-1$ to $n$. Let $a_n$ be the count of bit strings without $01$ at length $n$, recurrence relation of this is the following:
$$a_n = 2a_{n-1}, a_2 = 1$$
The inverse of this is then the recurrence relation with $01$. Let $P_n$ be the recurrence relationship of the number of bit string with length $n$ with $01$, thus,
$$P_n = 2^n – a_n = 2^n – 2a_{n-1}, a_2 = 1$$
Since $P_n = 2^n – a_n$, then, $a_n = 2^n – P_n$, thus
$$P_n = 2^n – 2*(2^{n-1} – P_{n-1})$$
$$\iff P_n = 2^n – 2^n + 2P_{n-1}$$
$$P_n = 2P_{n-1}, P_2 = 1$$
Problem:
I've also played around with the n-combination to solve this. The format of a bit string without $01$ is the following,
$$1\dots10\dots0$$
Adding $0$ or $1$ to either side adds a $01$, thus we can only add either $1$ on the left and $0$ on the right. Another way to view this is,
$1^p0^q, p, q \geq 1$
The number of bit strings without $01$ is for a bit string of length $n$,
$${2 + n – 2 – 1\choose n-2} = \\
{n-1 \choose 1} = \\
n-1$$
The inverse of this is,
$$2^n – n+1$$
Which is the number of bit string with $01$ at length $n$.
If we solve the recurrence relation above for $P_n$,
$$P_3 = 2P_2 = 2$$
$$P_4 = 2*2\\
\vdots\\
P_n = 2^{n-2}$$
Which is inconsistent with the $n$-combination solution to solve this. Where did I get it wrong??
Best Answer
The number of bit-strings of length $n$ without
01
is: $n+1$. (Not $n-1$.)You have the pattern $\underbrace{1\cdots 1}_{k}\underbrace{0\cdots 0}_{n-k}$, where the number of
1
bits, $k$, can range from $0$ to $n$.Thus the number of $n$ length bit-strings with at least 1 substring of
01
is: $2^n-n-1$.You are over counting. Adding
0
to the end of110
gives the same result as adding1
to the start of100
: namely1100
. Just count the ways to add0
or1
to the end of the strings and remain valid. You can viably add0
to every valid $n-1$ length string; but there is only one viable target to which you can add1
(the one with all1
s).Also there are three string of length 2 which do not contain
01
: namely00
,10
,11
.$$a_n = a_{n-1}+1, a_2=3$$
Thus the valid 3-length strings are:
000
,100
,110
, and111
. $a_n=4$ as expected.(Always test your logic on the simplest examples. )
Applying the correct formula: $$\begin{align} P_n & = 2^n - a_{n} \\ & = 2\cdot 2^{n-1} - (a_{n-1} + 1) \\ & = P_{n-1} + 2^{n-1} - 1 \\[2ex] P_2 & = 1 & 2^2-3 \\P_3 & = 1+4-1 = 4 & 2^3-4 \\P_4 & = 4+8-1 = 11 & 2^4 - 5 \\ \text{et cetera} \end{align}$$