[Math] Consecutive bit strings

discrete mathematics

I can't figure out a solution for these kinds of questions could someone solve an example for me

How many bit strings of length 15 contain 9 consecutive 1’s or 9 consecutive 0’s?

Best Answer

Let’s first count the $15$-bit strings that have exactly $9$ consecutive ones.

If the bit string is $b=b_1b_2\dots b_{15}$, the block of ones can start at $b_1,b_2,b_3,b_4,b_5,b_6$, or $b_7$. If it starts at $b_1$, $b_{10}$ must be $0$, and bits $b_{11}$ through $b_{15}$ can be anything. That’s five bits that can be set arbitrarily to $0$ or $1$; there are $2^5=32$ ways to do that, so there are $2^5$ $15$-bet strings that begin with a string of exactly $9$ consecutive ones. Similarly, there are $2^5$ that end with such a string. If the string of $9$ ones starts at $b_2,b_3,b_4,b_5$, or $b_6$, on the other hand, it must have a $0$ on each end. That accounts for $9+2=11$ bits, leaving only $15-11=4$ bits to be set arbitrarily. In each case this can be done in $2^4=16$ ways. Thus, we get a grand total of $2\cdot2^5+5\cdot2^4=64+80=144$ such bit strings.

There are of course exactly as many that have exactly $9$ consecutive zeroes, and no $15$-bit string can have both, so there are $2\cdot144=288$ $15$-bit strings that contain exactly $9$ consecutive ones or consecutive zeroes.

A string of at least $9$ ones can still begin at any of the first seven positions. If it begins with $b_1$, we must have $b_1=b_2=\ldots= b_9=1$, but the remaining $6$ bits can be set arbitrarily, since we no longer have to require that $b_{10}=0$; this case therefore yields $2^6$ strings. If it begins with one of $b_2$ through $b_7$, it must be preceded by a zero, so a total of ten bits are determined: a zero followed by $9$ ones. The remaining $5$ bits, however, can be set arbitrarily, so these six cases yield another $6\cdot2^5$ strings. And as before we’ll get just as many with a string of at least $9$ zeroes, so the grand total is $2\left(2^6+6\cdot2^5\right)=512$.

Related Question