# Combinations and Bit String help

I have a 15 bit string, and I want to find how many combinations there are where there are no consecutive two 0's in a row. If I'm interpreting this right, combinations of 001001001001001 and 101010101010101 are valid, but combinations such as 000010101010101 are not. Am I going about this right? I'm looking for guidance rather than answers.

• I m confused."how many combinations there are where there are no consecutive two $0$'s in a row" is the word no there in your first sentence? – Siong Thye Goh Jun 8 '17 at 16:53
• Essentially, how many 15 bit strings have no consecutive two 0's in a row, which i interpreted as: a combination with 0000 cannot be a choice, but a combination with 00100 is valid – olearythe3rd Jun 8 '17 at 16:59
• Just because something does not contain two consecutive 00's does not mean it has to contain at least one 00 .... So at least the way you phrased this question,m I would think 101010101010101010101 is a valid combination. ... am I missing something? – Bram28 Jun 8 '17 at 17:08
• I believe you are correct, in retrospect, 101010101010101010101 is a valid combination as it doesn't violate the bit string not having consecutive two 0's in a row, regardless of whether it contained 00 or not within it. I will update my question to reflect this – olearythe3rd Jun 8 '17 at 17:12

## 1 Answer

If you try to take out all combinations that would make it fail it is much easier. For this example imagine an 8 bit string. $$00001111$$ What surrounds $0000$ does not matter therefore you can have any combination for the remaining 4 bits that aren't the $0000$, to figure out the amount of combinations that would be possible around the $0000$ we do $2^4$. Now however imagine we shift the $0000$ to the right $$11100001$$ Now any changes to the right which include a $0$ will be accounted for therefore only the possibility of a $1$ laying to the $0000$ right is not accounted for, thereby we calculate the amount of possibility's to the left of $0000$ we have $2^3$. now imagine we shift the $0000$ to the right again. $$11000011$$ As you can see we have accounted for possibility's apart from if there is $11$ to the right of the $0000$ therefore the amount of combinations that include $000011$ at the leftmost bits is $2^2$

If we were to continue this you get:$$2^0+2^1+2^2+2^3+2^4=\sum_{n=0}^4{2^n}$$ So to figure out the amount of invalid possibility's you can use: $$\sum_{n=1}^m{2^n}$$ Where m is the length of your bit string minus $4$.

Now that you know all combinations that would be rejected, you can calculate all possible combinations, valid or invalid, using $2^k$ where $k$ is the length of your string. Subtract invalid possibility's from all possibility's to obtain the amount of valid combinations, in this case: $$2^8 - (\sum_{n=0}^42^n) = 256 - 31 = 225$$

• I think i understand this. so if i apply this to a 15 bit string, I should solve: $$2^{15} - (\sum_{n=1}^{11}2^n)$$ – olearythe3rd Jun 8 '17 at 18:15
• yep, that's correct – Sonny Da Silva-Peters Jun 8 '17 at 18:19
• correction you should do that but with $\sum_{n=0}^{15}2^n$ sorry – Sonny Da Silva-Peters Jun 8 '17 at 18:23
• cool, so what if it was three 0's? $2^{15} - (\sum_{n=0}^{9}2^n)$? that would come out to 32768-1022=31746? I find that odd as i feel that there would be less combinations for three 0's over two 0's – olearythe3rd Jun 8 '17 at 18:25
• this is becuase you want to include the final combination where the $0000$ is at the left most – Sonny Da Silva-Peters Jun 8 '17 at 18:26