For n≥4 consider the strings where there are exactly two occurrences of 01. How many are there?
Okay, so I first tried brute forcing this to see if a pattern might arise, but I couldn't find one and as n got larger I found it harder to list out all the possible strings with exactly two occurrences of 01. The solution I found at the back of my book was also very confusing.
Answer: A string of this type consists of x1 1's followed by x2 0's followed by x3 1'x followed by x4 0's followed by x5 1's followed by x6 0's, where,
$$x_1 + x_2 + x_3 + x_4 + x_5 +x_6 = n$$
What I am confused about is why x1 has to consist of 1's and not 0's. Doesn't this following sequence 010100 count as one possible string where x1 is a 0 and not a 1? Finally, if n = 4 for instance, how would it add up to 4 if the only sequence where exactly two 01 occurs is 0101? I can't understand how 0 + 1 + 0+ 1 = 4
Best Answer
In the string $010100$, $x_1=0$, $x_2=1$, $x_3=1$, $x_4=1$, $x_5=1$, and $x_6=2$: the leading block of $1$’s is empty. The point is that you must have exactly two instances of $01$, so overall the string has to look like
$$\ldots01\ldots01\ldots\;,\tag{1}$$
where the dots must fill in for strings that do not contain $01$. Such strings must be empty, all $0$’s, all $1$’s, or of the form $11\ldots 100\ldots 0$, i.e., a string of $1$’s followed by a string of $0$’s. We can cover all of these possibilities by saying that we’re talking about strings of the form $1^k0^\ell$, meaning $k$ $1$’s followed by $\ell$ $0$’s, where $k$ and $\ell$ are non-negative integers. In particular, they can be $0$. Thus, we can fill out $(1)$ to read
$$1^{k_1}0^{\ell_1}011^{k_2}0^{\ell_2}011^{k_3}0^{\ell_3}\;;$$
this is a string of $k_1$ $1$’s followed by a string of $\ell_1+1$ $0$’s, a string of $k_2+1$ $1$’s, a string of $\ell_2+1$ $0$’s, a string of $k_3+1$ $1$’s, and a string of $\ell_3$ $0$’s. In terms of your notation, $x_1=k_1$, $x_2=\ell_1+1$, $x_3=k_2+1$, $x_4=\ell_2+1$, $x_5=k_3+1$, and $x_6=\ell+3$. As you can see, we can have any non-negative integer values of $x_1,\ldots,x_6$ such that $x_2,x_3,x_4$, and $x_5$ are strictly positive.
Your problem then reduces to counting the solutions in non-negative integers of
$$x_1+x_2+x_3+x_4+x_5+x_6=n\;,$$
subject to the restriction that $x_2,x_3,x_4,x_5\ge 1$. This is a fairly standard stars and bars problem.