Alteration in Binary Strings Question

Question

Question:

An alteration in a binary string is said to occur when the string encounters one of the following two patterns - “01” or “10”.

For example, the string 1101001 has exactly 4 alterations in it - which occur at positions 3,4,5 and 7. Count the total number of n bit strings that have at least 2 alterations.

I'm completely stumped on this question. After spending some time looking at it, I can determine that a combination will need to be used to try and count the total number of possibilities. However, I'm not sure how you would be able to set this up using some sort of counting method.

Any sort of solution/guidance is appreciated.

Answer 1

Let's calculate the answer by finding number of n-bit strings (no restriction) - ... strings with 0 alteration - ... with 1 alteration.

When n=2 there are no strings with 2 alterations or more, so the answer is 0. Assume $n\geq 2$

Number of n-bit strings is $\fbox{$2^n$}$, as each bit can either be 0 or 1.

Strings with 0 alteration means there are no "switch" in the string, which implies the string is either 0....0 or 1....1. There are $\fbox{$2$}$ cases here.

Finally, the number of strings with 1 alteration must be in the form 0...01....1 or 1...10....0 with at least one 0 and one 1. Consider the form 0...01...1. There can be 1 0 as the prefix, 2 0, ..., (n-1) 0, giving us (n-1) cases. The same applies for 1...10...0, giving us $\fbox{$2(n-1)$}$ cases in total.

Therefore, the number of strings with 2 or more alterations is $\fbox{$2^n-2n$}$.

Bonus: Number of strings with exactly k alterations is 2*(n-1 choose k).

Proof: Let's consider the number strings with exactly k alterations
that start with a `0` and double the answer.

The n-bit string looks like this:            0 _ _ _ _ _ _ _ _ _ _ 
Now let's insert a "pipe" between each bit:  0|_|_|_|_|_|_|_|_|_|_
For example one string might look like this: 0000000|1111|0000000 (where k=2)
Each pipe represents an alteration, and we must choose k of them out of the (n-1)
Thus there are 2*(n-1 choose k) where choose is the binomial coefficient