0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Siong Thye Goh Jun 8 '17 at 16:53
  • $\begingroup$ 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 $\endgroup$ – olearythe3rd Jun 8 '17 at 16:59
  • $\begingroup$ 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? $\endgroup$ – Bram28 Jun 8 '17 at 17:08
  • $\begingroup$ 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 $\endgroup$ – olearythe3rd Jun 8 '17 at 17:12
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$$ $\endgroup$ – olearythe3rd Jun 8 '17 at 18:15
  • $\begingroup$ yep, that's correct $\endgroup$ – Sonny Da Silva-Peters Jun 8 '17 at 18:19
  • $\begingroup$ correction you should do that but with $\sum_{n=0}^{15}2^n$ sorry $\endgroup$ – Sonny Da Silva-Peters Jun 8 '17 at 18:23
  • $\begingroup$ 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 $\endgroup$ – olearythe3rd Jun 8 '17 at 18:25
  • $\begingroup$ this is becuase you want to include the final combination where the $0000$ is at the left most $\endgroup$ – Sonny Da Silva-Peters Jun 8 '17 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.