0

How many bit string of length 12 contains 01 as a substring ?

I arrived at 2^10 . taking 01 as one set and remaining as other set

Heterotic
  • 481
Techwatch
  • 51
  • Probably easiest to find the strings that DO NOT contain $01$ and subtract that out from $2^{12}$. Which, offhand, I'm not coming up with many. All 1's. All 0's. And strings which only consist of a substring of 1's followed by a substring of 0's. I might be missing a bunch... – turkeyhundt Jan 20 '15 at 05:52
  • I think all 1s and all 0 are only two conditions other one would be 111....0 ( last one as zero) – Techwatch Jan 20 '15 at 05:57
  • well, as @Anurag A explains, 111100000000 etc also apply. – turkeyhundt Jan 20 '15 at 05:58

2 Answers2

4

Your way of reasoning is not correctly counting the number of strings. What you should aim for is count the number of strings that DO NOT CONTAIN $01$. Such strings will be of the form $111100000000$, i.e. Starts with bunch of $1's$ Then followed by $0's$. They will be $13$ such strings (including all zeroes). Thus your answer should be $2^{12}-13$.

Anurag A
  • 41,067
  • 1
    @turkeyhundt as I realized my error immediately I saw your comment also. Thanks I fixed the error. – Anurag A Jan 20 '15 at 06:00
1

Anurag A has given a fine explanation of the most straightforward way to solve the problem, but I thought that someone should also explain what’s wrong with your approach. The first problem is that you didn’t take into account the fact that the $01$ block can occupy any one of $11$ different positions in the string. Thus, a first approximation to the desired number is $11\cdot 2^{10}$, not $2^{10}$.

Unfortunately, this overcounts rather badly. The string $\color{brown}{01}0000\color{green}{01}0000$, for instance, gets counted twice, once with the brown $\color{brown}{01}$ as the glued-together block, and once with the green $\color{green}{01}$ as the glued-together block. The string $010101010101$ gets counted $6$ times. To compensate for the overcounting you need an inclusion-exclusion argument. The strings with two $01$ substrings have all been counted twice, so we have to subtract them. Making two glued-together blocks, we see that we have a string of $10$ items, $2$ of which are the $01$ blocks; they can be placed in $\binom{10}2$ ways in the string, and the other $8$ bits can be chosen arbitrarily, so we count a total of $\binom{10}2\cdot2^8$ strings and get a second approximation of

$$\binom{11}1\cdot 2^{10}-\binom{10}2\cdot 2^8\;.\tag{1}$$

But now each string that has three $01$ substrings has been counted $3$ times in the first term of $(1)$ and subtracted $3$ times in the second term (why?), so in effect it isn’t counted in $(1)$ at all. Thus, we have to add those strings back in. When this process is carried to completion, we find that there are

$$\binom{11}1\cdot 2^{10}-\binom{10}2\cdot 2^8+\binom93\cdot 2^6-\binom84\cdot2^4+\binom75\cdot 2^2-\binom66\cdot 2^0$$

$12$-bit strings containing $01$ as a substring. You can check that this actually does work out to $2^{12}-13=4083$.

Brian M. Scott
  • 616,228