How many bit strings of length $8$ have at least a block of at least $4$ contiguous ones?

Question

Can take the $8$ bits with the $\ge 4$ contiguous bits as a block. Need consider the different cases separately.
The positions possible for each of the size of blocks is:
(i) $4$ contiguous bits : $^8P_4$,
(ii) $5$ contiguous bits : $^8P_5$,
(iii) $6$ contiguous bits : $^8P_6$,
(iv) $7$ contiguous bits : $^8P_7$,
(v) $8$ contiguous bits : $^8P_8$,
Need to add all these cases by the addition principle, as these are mutually exclusive cases and comprise the solution space.

$=> ^8P_4 + ^8P_5 + ^8P_6 +^8P_7 + ^8P_8$

But, also need to consider the possible choices for each case. Also, in each case, except the last two cases above there is chance that two positions at the both sides of the contiguous block are $0$. I mean that it is possible that one end is the start position for the contiguous bits as $11110000$ which is different from $01111011$. For the case of $4$ contiguous bits, will the chances be :

$^8P_4\cdot(\,\,$case $00001111+$ case $11110000+$cases$ (0/1)1111(0/1)(0/1)(0/1)\,\,) + $ cases$ (0/1)(0/1)(0/1)1111(0/1) \,\,)$

$=> ^8P_4\cdot(\,\, 1 + 1 + 2^4 +2^4)$

$=> ^8P_4\cdot(\,\, 2+ 2\cdot2^4)$

If the above analysis is correct for the case of $4$ contiguous bits, then how to generalize it for more bits.

======

Update :- My post considers $8$ separate positions, & then takes the $i=\{4,5,6,7,8\}$ possible contiguous $1$s. It takes the possible permutations of these all, then multiplies by the ways the other digits are chosen (i.e. $0,1$); & then adds all of these cases.

This is defective, as the first of all, the $i$ contiguous $1$s are a unit, leaving only $5$ positions.
This is not obvious (to me), but can be checked by comparing the values of $^8P_4(=1680)$ to $^5P_4(=120)$.

Second, the $8-i$ positions can take a value based on where there are w.r.t. the contiguous block; i.e. if next to the block, then only one choice. This means that if the block is in a corner, then different number of choices are possible. So, need to consider individual cases.
This part is not a shortcoming of my answer, as have considered individual case separately.

Third, there is overlap between cases, as pointed out by the sole answer.

=======

Update 2 The python code for finding the sets' elements, & the intersection sets is given here, as provided by @SiongThyeGoh.

=========

Update 3 This is to have record of chats with @Siong Thye Goh :
(i) dt. 7th, 8th, 9th, 10th Oct., 2018; at: https://chat.stackexchange.com/transcript/84135/2018/10/7,
(ii) dt. 08 Nov. , 2018: https://chat.stackexchange.com/rooms/85486/jiten,
(iii) dt. 27 Nov. , 2018: https://chat.stackexchange.com/rooms/86261/8-bit-strings-having-4-contiguous,
(iv) dt. 17th Dec., 2018: https://chat.stackexchange.com/rooms/87190/stack-error-py3.

Answer 1

The numbers are small that a brute force way is possible (though not encouraged):

The bit strings can be of the following form:

• $11110xyz$ : $2^3$ possibilities
• $011110xy$ : $2^2$ possibilities
• $x011110y$ : $2^2$ possibilities
• $xy011110$ : $2^2$ possibilities
• $xyz01111$ : $2^3$ possibilities
• $111110xy$ : $2^2$ possibilities
• $0111110x$ : $2^1$ possibilities
• $x0111110$ : $2^1$ possibilities
• $xy011111$ : $2^2$ possibilities
• $1111110x$ : $2^1$ possibilities
• $01111110$ : $2^0$ possibilities
• $x0111111$ : $2^1$ possibilities
• $11111110$ : $2^0$ possibilities
• $01111111$ : $2^0$ possibilities
• $11111111$ : $2^0$ possibilities

Hence there are a total of $$2(2^3)+5(2^2)+4(2)+4(1)=48 \text{ bit strings}$$

Edit:

If $A_i$ is the set of strings where positions $i$ to $i+3$ must take value $1$.

For this particular example, we note that $A_i \cap A_j \neq \emptyset$. Also, also for this particular question, the consecutive block of $1$ with lenght at least $4$ must be connected. if we assume $j>i$, in fact, we have $$|A_i \cap A_j | = 2^{8-((j+3)-i+1)}=2^{4-j+i}$$

Also, we have $A_i \cap A_j \cap A_k = A_{\max(i,j,k)} \cap A_{\min(i,j,k)}$ for this particular example.

With the help of Python, we can use inclusion exclusion principle to conclude that the cardinality is

\begin{align}\left| \bigcup_{i=1}^5 A_i\right|&=\sum_{i=1}^52^4- \sum_{i=1}^4 \sum_{j=i+1}^52^{4-j+i} + \sum_{i=1}^3 \sum_{j=i+1}^4\sum_{k=j+1}^52^{4-k+i}-\sum_{i=1}^2 \sum_{j=i+1}^3\sum_{k=j+1}^4\sum_{l=k+1}^52^{4-l+i}+1\\&=\sum_{i=1}^52^4 - \sum_{d=1}^4 (5-d)2^{4-d} + \sum_{d=2}^4(5-d) \binom{d-1}{1}2^{4-d}-\sum_{d=3}^4(5-d)\binom{d-1}2 2^{4-d}+1 \\&= 80 + \sum_{i=1}^4 (-1)^i\sum_{d=i}^4(5-d) \binom{d-1}{i-1}2^{4-d} \\&=80-49+23-7+1=48 \end{align}

Answer 2

Since there are two ways to fill each position in a bit string, there are $2^8 = 256$ bit strings of length $8$. From these, we must subtract those bit strings with fewer than four consecutive ones.

Let $a_n$ denote the number of bit strings of length $n$ with fewer than four consecutive bit ones. Observe that any bit string of length one, two, or three has fewer than four consecutive ones and that the only bit string of length $4$ that contains four consecutive ones is $1111$. Hence, we have the initial conditions \begin{align*} a_1 & = 2\\ a_2 & = 4\\ a_3 & = 8\\ a_4 & = 15 \end{align*} A bit string with fewer than four consecutive ones can begin in one of four ways. They are $0$, $10$, $110$, and $1110$.

• If an admissible bit string of length $n$ begins with $0$, the initial $0$ must be followed by an admissible bit string of length $n - 1$, of which there are $a_{n - 1}$.
• If an admissible bit string of length $n$ begins with $10$, the initial string $10$ must be followed by an admissible bit string of length $n - 2$, of which there are $a_{n - 2}$.
• If an admissible bit string of length $n$ begins with $110$, the initial string $110$ must be followed by an admissible bit string of length $n - 3$, of which there are $a_{n - 3}$.
• If an admissible bit string of length $n$ begins with $1110$, the initial string $1110$ must be followed by an admissible bit string of length $n - 4$, of which there are $a_{n - 4}$.

Since these four cases are mutually exclusive and exhaustive, we have the recurrence relation $$a_n = a_{n - 1} + a_{n - 2} + a_{n - 3} + a_{n - 4}, n \geq 5$$ Applying the recurrence relation to the initial conditions yields \begin{align*} a_5 & = 29\\ a_6 & = 56\\ a_7 & = 108\\ a_8 & = 208 \end{align*} As a check, observe that of the $2^5 = 32$ bit strings of length $5$, the only ones that do not have fewer than four consecutive ones are $01111$, $11110$, and $11111$, so there are $32 - 3 = 29$ bit strings of length $5$ that have fewer than four consecutive ones, which agrees with our count.

Since there are $256$ bit strings of length $8$ and $208$ of these bit strings of length $8$ have fewer than four consecutive ones, the number of bit strings of length $8$ that have at least four consecutive ones is $256 - 208 = 48$.

Answer 3

The general solution is thoroughly explained in this related post, and is given by

Number of binary strings, with $s$ "$1$"'s and $m$ "$0$"'s in total, that have up to $r$ consecutive $1$s : $$ N_b (s,r,m + 1)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m + 1} \right)} { \left( { - 1} \right)^k \binom{m+1}{k} \binom {s + m - k\left( {r + 1} \right) }{s - k\left( {r + 1} \right) } } $$ and which are the coefficients of $x^s$ in $$ \left( {{{1 - x^{\,r + 1} } \over {1 - x}}} \right)^{\,m + 1} $$

Fixing the length to be $n$, summing over $m$ the above repartition into $n-m$ ones and $m$ zeros, we get

Number of binary strings of lenght $n$, that have up to $r$ consecutive $1$s : $$ M_b (n,r)\quad = \sum\limits_{\left( {0\, \le } \right)\,\,m\,\,\left( { \le \,n} \right)} { \sum\limits_{\left( {0\, \le } \right)\,\,k\,\,\left( { \le \,{{n-m} \over {r+1}}\, \le \,m + 1} \right)} { \left( { - 1} \right)^k \binom{m+1}{k} \binom{n - k\left( {r + 1} \right)}{ n - m - k\left( {r + 1} \right) } } } $$ which doesn't look to be further simplifiable.

In your case we have $$ M_b (8,r)\quad \left| {\;0 \le r \le 8} \right.\quad = 1,\;55,\;149,\;208,\;236,\;248,\;253,\;255,\;256 $$ thus $M_b (8,3)=208$, and the number of strings having $4$ or more consecutive ones is $2^8-208=48$

Note that those having exactly a maximum of $4$ consecutive ones are $M_b (8,4) -M_b (8,3)=28$

Finally, $M_b (n,r)$ is the OEIS sequence A126198 : "number of compositions of n into parts of size <= k".