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












1












$begingroup$


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_4cdot(,,$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_4cdot(,, 1 + 1 + 2^4 +2^4)$



$=> ^8P_4cdot(,, 2+ 2cdot2^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.










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    The question is unclear. Are you asking for the probability that there is a block of at least consecutive ones in a bit string of length eight? If so, the cases of four consecutive ones and five consecutive ones are not mutually exclusive cases since a string of five consecutive ones contains two strings of four consecutive ones (starting with the first or second of the five consecutive bits). If I understand the problem correctly, you will need to use the Inclusion-Exclusion Principle or generating functions to solve the problem.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 22:49












  • $begingroup$
    @N.F.Taussig Yes, it is to get a block of at least $4$ contiguous (or, continuous) $1$s in a block of $8$ bits. Regarding, solving using the Inclusion-Exclusion Principle, or generating functions; am not clear.
    $endgroup$
    – jiten
    Oct 6 '18 at 22:52








  • 1




    $begingroup$
    Another option could be using a recurrence relation to count those bit strings with fewer than four consecutive ones, then subtracting that number from the total number of bit strings.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 23:00










  • $begingroup$
    @N.F.Taussig This should be a 3rd option. But, not clear about a generalized relation.
    $endgroup$
    – jiten
    Oct 6 '18 at 23:01






  • 1




    $begingroup$
    As a sanity check, you should compare your answer with the total number of bit strings of length eight. Since your answer exceeds that number, it cannot be correct.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 23:36
















1












$begingroup$


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_4cdot(,,$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_4cdot(,, 1 + 1 + 2^4 +2^4)$



$=> ^8P_4cdot(,, 2+ 2cdot2^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.










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    The question is unclear. Are you asking for the probability that there is a block of at least consecutive ones in a bit string of length eight? If so, the cases of four consecutive ones and five consecutive ones are not mutually exclusive cases since a string of five consecutive ones contains two strings of four consecutive ones (starting with the first or second of the five consecutive bits). If I understand the problem correctly, you will need to use the Inclusion-Exclusion Principle or generating functions to solve the problem.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 22:49












  • $begingroup$
    @N.F.Taussig Yes, it is to get a block of at least $4$ contiguous (or, continuous) $1$s in a block of $8$ bits. Regarding, solving using the Inclusion-Exclusion Principle, or generating functions; am not clear.
    $endgroup$
    – jiten
    Oct 6 '18 at 22:52








  • 1




    $begingroup$
    Another option could be using a recurrence relation to count those bit strings with fewer than four consecutive ones, then subtracting that number from the total number of bit strings.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 23:00










  • $begingroup$
    @N.F.Taussig This should be a 3rd option. But, not clear about a generalized relation.
    $endgroup$
    – jiten
    Oct 6 '18 at 23:01






  • 1




    $begingroup$
    As a sanity check, you should compare your answer with the total number of bit strings of length eight. Since your answer exceeds that number, it cannot be correct.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 23:36














1












1








1


1



$begingroup$


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_4cdot(,,$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_4cdot(,, 1 + 1 + 2^4 +2^4)$



$=> ^8P_4cdot(,, 2+ 2cdot2^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.










share|cite|improve this question











$endgroup$




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_4cdot(,,$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_4cdot(,, 1 + 1 + 2^4 +2^4)$



$=> ^8P_4cdot(,, 2+ 2cdot2^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.







combinatorics






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 25 '18 at 14:58







jiten

















asked Oct 6 '18 at 22:22









jitenjiten

1,2411413




1,2411413








  • 1




    $begingroup$
    The question is unclear. Are you asking for the probability that there is a block of at least consecutive ones in a bit string of length eight? If so, the cases of four consecutive ones and five consecutive ones are not mutually exclusive cases since a string of five consecutive ones contains two strings of four consecutive ones (starting with the first or second of the five consecutive bits). If I understand the problem correctly, you will need to use the Inclusion-Exclusion Principle or generating functions to solve the problem.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 22:49












  • $begingroup$
    @N.F.Taussig Yes, it is to get a block of at least $4$ contiguous (or, continuous) $1$s in a block of $8$ bits. Regarding, solving using the Inclusion-Exclusion Principle, or generating functions; am not clear.
    $endgroup$
    – jiten
    Oct 6 '18 at 22:52








  • 1




    $begingroup$
    Another option could be using a recurrence relation to count those bit strings with fewer than four consecutive ones, then subtracting that number from the total number of bit strings.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 23:00










  • $begingroup$
    @N.F.Taussig This should be a 3rd option. But, not clear about a generalized relation.
    $endgroup$
    – jiten
    Oct 6 '18 at 23:01






  • 1




    $begingroup$
    As a sanity check, you should compare your answer with the total number of bit strings of length eight. Since your answer exceeds that number, it cannot be correct.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 23:36














  • 1




    $begingroup$
    The question is unclear. Are you asking for the probability that there is a block of at least consecutive ones in a bit string of length eight? If so, the cases of four consecutive ones and five consecutive ones are not mutually exclusive cases since a string of five consecutive ones contains two strings of four consecutive ones (starting with the first or second of the five consecutive bits). If I understand the problem correctly, you will need to use the Inclusion-Exclusion Principle or generating functions to solve the problem.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 22:49












  • $begingroup$
    @N.F.Taussig Yes, it is to get a block of at least $4$ contiguous (or, continuous) $1$s in a block of $8$ bits. Regarding, solving using the Inclusion-Exclusion Principle, or generating functions; am not clear.
    $endgroup$
    – jiten
    Oct 6 '18 at 22:52








  • 1




    $begingroup$
    Another option could be using a recurrence relation to count those bit strings with fewer than four consecutive ones, then subtracting that number from the total number of bit strings.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 23:00










  • $begingroup$
    @N.F.Taussig This should be a 3rd option. But, not clear about a generalized relation.
    $endgroup$
    – jiten
    Oct 6 '18 at 23:01






  • 1




    $begingroup$
    As a sanity check, you should compare your answer with the total number of bit strings of length eight. Since your answer exceeds that number, it cannot be correct.
    $endgroup$
    – N. F. Taussig
    Oct 6 '18 at 23:36








1




1




$begingroup$
The question is unclear. Are you asking for the probability that there is a block of at least consecutive ones in a bit string of length eight? If so, the cases of four consecutive ones and five consecutive ones are not mutually exclusive cases since a string of five consecutive ones contains two strings of four consecutive ones (starting with the first or second of the five consecutive bits). If I understand the problem correctly, you will need to use the Inclusion-Exclusion Principle or generating functions to solve the problem.
$endgroup$
– N. F. Taussig
Oct 6 '18 at 22:49






$begingroup$
The question is unclear. Are you asking for the probability that there is a block of at least consecutive ones in a bit string of length eight? If so, the cases of four consecutive ones and five consecutive ones are not mutually exclusive cases since a string of five consecutive ones contains two strings of four consecutive ones (starting with the first or second of the five consecutive bits). If I understand the problem correctly, you will need to use the Inclusion-Exclusion Principle or generating functions to solve the problem.
$endgroup$
– N. F. Taussig
Oct 6 '18 at 22:49














$begingroup$
@N.F.Taussig Yes, it is to get a block of at least $4$ contiguous (or, continuous) $1$s in a block of $8$ bits. Regarding, solving using the Inclusion-Exclusion Principle, or generating functions; am not clear.
$endgroup$
– jiten
Oct 6 '18 at 22:52






$begingroup$
@N.F.Taussig Yes, it is to get a block of at least $4$ contiguous (or, continuous) $1$s in a block of $8$ bits. Regarding, solving using the Inclusion-Exclusion Principle, or generating functions; am not clear.
$endgroup$
– jiten
Oct 6 '18 at 22:52






1




1




$begingroup$
Another option could be using a recurrence relation to count those bit strings with fewer than four consecutive ones, then subtracting that number from the total number of bit strings.
$endgroup$
– N. F. Taussig
Oct 6 '18 at 23:00




$begingroup$
Another option could be using a recurrence relation to count those bit strings with fewer than four consecutive ones, then subtracting that number from the total number of bit strings.
$endgroup$
– N. F. Taussig
Oct 6 '18 at 23:00












$begingroup$
@N.F.Taussig This should be a 3rd option. But, not clear about a generalized relation.
$endgroup$
– jiten
Oct 6 '18 at 23:01




$begingroup$
@N.F.Taussig This should be a 3rd option. But, not clear about a generalized relation.
$endgroup$
– jiten
Oct 6 '18 at 23:01




1




1




$begingroup$
As a sanity check, you should compare your answer with the total number of bit strings of length eight. Since your answer exceeds that number, it cannot be correct.
$endgroup$
– N. F. Taussig
Oct 6 '18 at 23:36




$begingroup$
As a sanity check, you should compare your answer with the total number of bit strings of length eight. Since your answer exceeds that number, it cannot be correct.
$endgroup$
– N. F. Taussig
Oct 6 '18 at 23:36










3 Answers
3






active

oldest

votes


















2












$begingroup$

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_iright|&=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}^4sum_{k=j+1}^52^{4-k+i}-sum_{i=1}^2 sum_{j=i+1}^3sum_{k=j+1}^4sum_{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)^isum_{d=i}^4(5-d) binom{d-1}{i-1}2^{4-d}
\&=80-49+23-7+1=48 end{align}






share|cite|improve this answer











$endgroup$













  • $begingroup$
    So, no generalized formula is possible (i.e., is not easy to use). Also, the 6th case should be $011110xy$ instead of $111110xy$.
    $endgroup$
    – jiten
    Oct 7 '18 at 5:52








  • 1




    $begingroup$
    The other answer has given you a generalized formula isn't it. $011110xy$ has been considered in the second case.
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 5:55






  • 1




    $begingroup$
    chat.stackexchange.com/rooms/85486/jiten not sure this is how chatroom works. avoid long comments.
    $endgroup$
    – Siong Thye Goh
    Nov 8 '18 at 7:47






  • 1




    $begingroup$
    i can't response much today ... i am sick... again.... maybe after i recover.
    $endgroup$
    – Siong Thye Goh
    Nov 12 '18 at 12:32






  • 1




    $begingroup$
    print out i and its length and examine what happens.
    $endgroup$
    – Siong Thye Goh
    Nov 27 '18 at 8:25



















1












$begingroup$

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






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Thanks for the answer. Is an alternate approach possible, that is based on finding without having a count of first few cases. I mean that the above approach seems like induction, as generates a formula based on few initial cases. I hence request a formula that is based on something like my approach.
    $endgroup$
    – jiten
    Oct 7 '18 at 0:58






  • 1




    $begingroup$
    This approach struck me as simpler than using the Inclusion-Exclusion Principle. To use the Inclusion-Exclusion Principle, I would define $A_i$, $1 leq i leq 5$, as the set of bit strings of length $8$ that include four consecutive ones beginning in the $i$th position. The problem is that these sets intersect when more than four consecutive ones occur, so we over count. Therefore, we must subtract those cases that occur more than once. Doing so requires care and considerable effort.
    $endgroup$
    – N. F. Taussig
    Oct 7 '18 at 1:12






  • 2




    $begingroup$
    Example if I understand definition of $A_i$ correctly. $11111000 in A_1 cap A_2$
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 5:14






  • 1




    $begingroup$
    $A_i$ has $1$ starting from position $i$, it is also possible to have $1$ at position $i-1$. $11111000$ has $5$ consecutive $1$. It is in $A_1$ since starting from position $1$, there are $5$ consecutive $1$'s. It is in $A_2$ since starting from position $2$, there are $4$ consecutive $1$'s.
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 6:05






  • 1




    $begingroup$
    @SiongThyeGoh: there is a more clean and effective approach : re. to this related post which leads to the solution I presented above.
    $endgroup$
    – G Cab
    Oct 7 '18 at 19:34



















1












$begingroup$

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
= sumlimits_{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 - kleft( {r + 1} right) }{s - kleft( {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 = sumlimits_{left( {0, le } right),,m,,left( { le ,n} right)} {
sumlimits_{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 - kleft( {r + 1} right)}{ n - m - kleft( {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".






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Thanks, but feel that the last link is wrong, as it s about triangular numbers. Sorry, if wrong.
    $endgroup$
    – jiten
    Oct 8 '18 at 10:17











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2945020%2fhow-many-bit-strings-of-length-8-have-at-least-a-block-of-at-least-4-contigu%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes









2












$begingroup$

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_iright|&=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}^4sum_{k=j+1}^52^{4-k+i}-sum_{i=1}^2 sum_{j=i+1}^3sum_{k=j+1}^4sum_{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)^isum_{d=i}^4(5-d) binom{d-1}{i-1}2^{4-d}
\&=80-49+23-7+1=48 end{align}






share|cite|improve this answer











$endgroup$













  • $begingroup$
    So, no generalized formula is possible (i.e., is not easy to use). Also, the 6th case should be $011110xy$ instead of $111110xy$.
    $endgroup$
    – jiten
    Oct 7 '18 at 5:52








  • 1




    $begingroup$
    The other answer has given you a generalized formula isn't it. $011110xy$ has been considered in the second case.
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 5:55






  • 1




    $begingroup$
    chat.stackexchange.com/rooms/85486/jiten not sure this is how chatroom works. avoid long comments.
    $endgroup$
    – Siong Thye Goh
    Nov 8 '18 at 7:47






  • 1




    $begingroup$
    i can't response much today ... i am sick... again.... maybe after i recover.
    $endgroup$
    – Siong Thye Goh
    Nov 12 '18 at 12:32






  • 1




    $begingroup$
    print out i and its length and examine what happens.
    $endgroup$
    – Siong Thye Goh
    Nov 27 '18 at 8:25
















2












$begingroup$

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_iright|&=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}^4sum_{k=j+1}^52^{4-k+i}-sum_{i=1}^2 sum_{j=i+1}^3sum_{k=j+1}^4sum_{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)^isum_{d=i}^4(5-d) binom{d-1}{i-1}2^{4-d}
\&=80-49+23-7+1=48 end{align}






share|cite|improve this answer











$endgroup$













  • $begingroup$
    So, no generalized formula is possible (i.e., is not easy to use). Also, the 6th case should be $011110xy$ instead of $111110xy$.
    $endgroup$
    – jiten
    Oct 7 '18 at 5:52








  • 1




    $begingroup$
    The other answer has given you a generalized formula isn't it. $011110xy$ has been considered in the second case.
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 5:55






  • 1




    $begingroup$
    chat.stackexchange.com/rooms/85486/jiten not sure this is how chatroom works. avoid long comments.
    $endgroup$
    – Siong Thye Goh
    Nov 8 '18 at 7:47






  • 1




    $begingroup$
    i can't response much today ... i am sick... again.... maybe after i recover.
    $endgroup$
    – Siong Thye Goh
    Nov 12 '18 at 12:32






  • 1




    $begingroup$
    print out i and its length and examine what happens.
    $endgroup$
    – Siong Thye Goh
    Nov 27 '18 at 8:25














2












2








2





$begingroup$

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_iright|&=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}^4sum_{k=j+1}^52^{4-k+i}-sum_{i=1}^2 sum_{j=i+1}^3sum_{k=j+1}^4sum_{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)^isum_{d=i}^4(5-d) binom{d-1}{i-1}2^{4-d}
\&=80-49+23-7+1=48 end{align}






share|cite|improve this answer











$endgroup$



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_iright|&=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}^4sum_{k=j+1}^52^{4-k+i}-sum_{i=1}^2 sum_{j=i+1}^3sum_{k=j+1}^4sum_{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)^isum_{d=i}^4(5-d) binom{d-1}{i-1}2^{4-d}
\&=80-49+23-7+1=48 end{align}







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Oct 8 '18 at 3:05









Saad

19.7k92352




19.7k92352










answered Oct 7 '18 at 5:37









Siong Thye GohSiong Thye Goh

100k1465117




100k1465117












  • $begingroup$
    So, no generalized formula is possible (i.e., is not easy to use). Also, the 6th case should be $011110xy$ instead of $111110xy$.
    $endgroup$
    – jiten
    Oct 7 '18 at 5:52








  • 1




    $begingroup$
    The other answer has given you a generalized formula isn't it. $011110xy$ has been considered in the second case.
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 5:55






  • 1




    $begingroup$
    chat.stackexchange.com/rooms/85486/jiten not sure this is how chatroom works. avoid long comments.
    $endgroup$
    – Siong Thye Goh
    Nov 8 '18 at 7:47






  • 1




    $begingroup$
    i can't response much today ... i am sick... again.... maybe after i recover.
    $endgroup$
    – Siong Thye Goh
    Nov 12 '18 at 12:32






  • 1




    $begingroup$
    print out i and its length and examine what happens.
    $endgroup$
    – Siong Thye Goh
    Nov 27 '18 at 8:25


















  • $begingroup$
    So, no generalized formula is possible (i.e., is not easy to use). Also, the 6th case should be $011110xy$ instead of $111110xy$.
    $endgroup$
    – jiten
    Oct 7 '18 at 5:52








  • 1




    $begingroup$
    The other answer has given you a generalized formula isn't it. $011110xy$ has been considered in the second case.
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 5:55






  • 1




    $begingroup$
    chat.stackexchange.com/rooms/85486/jiten not sure this is how chatroom works. avoid long comments.
    $endgroup$
    – Siong Thye Goh
    Nov 8 '18 at 7:47






  • 1




    $begingroup$
    i can't response much today ... i am sick... again.... maybe after i recover.
    $endgroup$
    – Siong Thye Goh
    Nov 12 '18 at 12:32






  • 1




    $begingroup$
    print out i and its length and examine what happens.
    $endgroup$
    – Siong Thye Goh
    Nov 27 '18 at 8:25
















$begingroup$
So, no generalized formula is possible (i.e., is not easy to use). Also, the 6th case should be $011110xy$ instead of $111110xy$.
$endgroup$
– jiten
Oct 7 '18 at 5:52






$begingroup$
So, no generalized formula is possible (i.e., is not easy to use). Also, the 6th case should be $011110xy$ instead of $111110xy$.
$endgroup$
– jiten
Oct 7 '18 at 5:52






1




1




$begingroup$
The other answer has given you a generalized formula isn't it. $011110xy$ has been considered in the second case.
$endgroup$
– Siong Thye Goh
Oct 7 '18 at 5:55




$begingroup$
The other answer has given you a generalized formula isn't it. $011110xy$ has been considered in the second case.
$endgroup$
– Siong Thye Goh
Oct 7 '18 at 5:55




1




1




$begingroup$
chat.stackexchange.com/rooms/85486/jiten not sure this is how chatroom works. avoid long comments.
$endgroup$
– Siong Thye Goh
Nov 8 '18 at 7:47




$begingroup$
chat.stackexchange.com/rooms/85486/jiten not sure this is how chatroom works. avoid long comments.
$endgroup$
– Siong Thye Goh
Nov 8 '18 at 7:47




1




1




$begingroup$
i can't response much today ... i am sick... again.... maybe after i recover.
$endgroup$
– Siong Thye Goh
Nov 12 '18 at 12:32




$begingroup$
i can't response much today ... i am sick... again.... maybe after i recover.
$endgroup$
– Siong Thye Goh
Nov 12 '18 at 12:32




1




1




$begingroup$
print out i and its length and examine what happens.
$endgroup$
– Siong Thye Goh
Nov 27 '18 at 8:25




$begingroup$
print out i and its length and examine what happens.
$endgroup$
– Siong Thye Goh
Nov 27 '18 at 8:25











1












$begingroup$

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






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Thanks for the answer. Is an alternate approach possible, that is based on finding without having a count of first few cases. I mean that the above approach seems like induction, as generates a formula based on few initial cases. I hence request a formula that is based on something like my approach.
    $endgroup$
    – jiten
    Oct 7 '18 at 0:58






  • 1




    $begingroup$
    This approach struck me as simpler than using the Inclusion-Exclusion Principle. To use the Inclusion-Exclusion Principle, I would define $A_i$, $1 leq i leq 5$, as the set of bit strings of length $8$ that include four consecutive ones beginning in the $i$th position. The problem is that these sets intersect when more than four consecutive ones occur, so we over count. Therefore, we must subtract those cases that occur more than once. Doing so requires care and considerable effort.
    $endgroup$
    – N. F. Taussig
    Oct 7 '18 at 1:12






  • 2




    $begingroup$
    Example if I understand definition of $A_i$ correctly. $11111000 in A_1 cap A_2$
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 5:14






  • 1




    $begingroup$
    $A_i$ has $1$ starting from position $i$, it is also possible to have $1$ at position $i-1$. $11111000$ has $5$ consecutive $1$. It is in $A_1$ since starting from position $1$, there are $5$ consecutive $1$'s. It is in $A_2$ since starting from position $2$, there are $4$ consecutive $1$'s.
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 6:05






  • 1




    $begingroup$
    @SiongThyeGoh: there is a more clean and effective approach : re. to this related post which leads to the solution I presented above.
    $endgroup$
    – G Cab
    Oct 7 '18 at 19:34
















1












$begingroup$

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






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Thanks for the answer. Is an alternate approach possible, that is based on finding without having a count of first few cases. I mean that the above approach seems like induction, as generates a formula based on few initial cases. I hence request a formula that is based on something like my approach.
    $endgroup$
    – jiten
    Oct 7 '18 at 0:58






  • 1




    $begingroup$
    This approach struck me as simpler than using the Inclusion-Exclusion Principle. To use the Inclusion-Exclusion Principle, I would define $A_i$, $1 leq i leq 5$, as the set of bit strings of length $8$ that include four consecutive ones beginning in the $i$th position. The problem is that these sets intersect when more than four consecutive ones occur, so we over count. Therefore, we must subtract those cases that occur more than once. Doing so requires care and considerable effort.
    $endgroup$
    – N. F. Taussig
    Oct 7 '18 at 1:12






  • 2




    $begingroup$
    Example if I understand definition of $A_i$ correctly. $11111000 in A_1 cap A_2$
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 5:14






  • 1




    $begingroup$
    $A_i$ has $1$ starting from position $i$, it is also possible to have $1$ at position $i-1$. $11111000$ has $5$ consecutive $1$. It is in $A_1$ since starting from position $1$, there are $5$ consecutive $1$'s. It is in $A_2$ since starting from position $2$, there are $4$ consecutive $1$'s.
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 6:05






  • 1




    $begingroup$
    @SiongThyeGoh: there is a more clean and effective approach : re. to this related post which leads to the solution I presented above.
    $endgroup$
    – G Cab
    Oct 7 '18 at 19:34














1












1








1





$begingroup$

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






share|cite|improve this answer









$endgroup$



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







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Oct 6 '18 at 23:27









N. F. TaussigN. F. Taussig

43.9k93355




43.9k93355












  • $begingroup$
    Thanks for the answer. Is an alternate approach possible, that is based on finding without having a count of first few cases. I mean that the above approach seems like induction, as generates a formula based on few initial cases. I hence request a formula that is based on something like my approach.
    $endgroup$
    – jiten
    Oct 7 '18 at 0:58






  • 1




    $begingroup$
    This approach struck me as simpler than using the Inclusion-Exclusion Principle. To use the Inclusion-Exclusion Principle, I would define $A_i$, $1 leq i leq 5$, as the set of bit strings of length $8$ that include four consecutive ones beginning in the $i$th position. The problem is that these sets intersect when more than four consecutive ones occur, so we over count. Therefore, we must subtract those cases that occur more than once. Doing so requires care and considerable effort.
    $endgroup$
    – N. F. Taussig
    Oct 7 '18 at 1:12






  • 2




    $begingroup$
    Example if I understand definition of $A_i$ correctly. $11111000 in A_1 cap A_2$
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 5:14






  • 1




    $begingroup$
    $A_i$ has $1$ starting from position $i$, it is also possible to have $1$ at position $i-1$. $11111000$ has $5$ consecutive $1$. It is in $A_1$ since starting from position $1$, there are $5$ consecutive $1$'s. It is in $A_2$ since starting from position $2$, there are $4$ consecutive $1$'s.
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 6:05






  • 1




    $begingroup$
    @SiongThyeGoh: there is a more clean and effective approach : re. to this related post which leads to the solution I presented above.
    $endgroup$
    – G Cab
    Oct 7 '18 at 19:34


















  • $begingroup$
    Thanks for the answer. Is an alternate approach possible, that is based on finding without having a count of first few cases. I mean that the above approach seems like induction, as generates a formula based on few initial cases. I hence request a formula that is based on something like my approach.
    $endgroup$
    – jiten
    Oct 7 '18 at 0:58






  • 1




    $begingroup$
    This approach struck me as simpler than using the Inclusion-Exclusion Principle. To use the Inclusion-Exclusion Principle, I would define $A_i$, $1 leq i leq 5$, as the set of bit strings of length $8$ that include four consecutive ones beginning in the $i$th position. The problem is that these sets intersect when more than four consecutive ones occur, so we over count. Therefore, we must subtract those cases that occur more than once. Doing so requires care and considerable effort.
    $endgroup$
    – N. F. Taussig
    Oct 7 '18 at 1:12






  • 2




    $begingroup$
    Example if I understand definition of $A_i$ correctly. $11111000 in A_1 cap A_2$
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 5:14






  • 1




    $begingroup$
    $A_i$ has $1$ starting from position $i$, it is also possible to have $1$ at position $i-1$. $11111000$ has $5$ consecutive $1$. It is in $A_1$ since starting from position $1$, there are $5$ consecutive $1$'s. It is in $A_2$ since starting from position $2$, there are $4$ consecutive $1$'s.
    $endgroup$
    – Siong Thye Goh
    Oct 7 '18 at 6:05






  • 1




    $begingroup$
    @SiongThyeGoh: there is a more clean and effective approach : re. to this related post which leads to the solution I presented above.
    $endgroup$
    – G Cab
    Oct 7 '18 at 19:34
















$begingroup$
Thanks for the answer. Is an alternate approach possible, that is based on finding without having a count of first few cases. I mean that the above approach seems like induction, as generates a formula based on few initial cases. I hence request a formula that is based on something like my approach.
$endgroup$
– jiten
Oct 7 '18 at 0:58




$begingroup$
Thanks for the answer. Is an alternate approach possible, that is based on finding without having a count of first few cases. I mean that the above approach seems like induction, as generates a formula based on few initial cases. I hence request a formula that is based on something like my approach.
$endgroup$
– jiten
Oct 7 '18 at 0:58




1




1




$begingroup$
This approach struck me as simpler than using the Inclusion-Exclusion Principle. To use the Inclusion-Exclusion Principle, I would define $A_i$, $1 leq i leq 5$, as the set of bit strings of length $8$ that include four consecutive ones beginning in the $i$th position. The problem is that these sets intersect when more than four consecutive ones occur, so we over count. Therefore, we must subtract those cases that occur more than once. Doing so requires care and considerable effort.
$endgroup$
– N. F. Taussig
Oct 7 '18 at 1:12




$begingroup$
This approach struck me as simpler than using the Inclusion-Exclusion Principle. To use the Inclusion-Exclusion Principle, I would define $A_i$, $1 leq i leq 5$, as the set of bit strings of length $8$ that include four consecutive ones beginning in the $i$th position. The problem is that these sets intersect when more than four consecutive ones occur, so we over count. Therefore, we must subtract those cases that occur more than once. Doing so requires care and considerable effort.
$endgroup$
– N. F. Taussig
Oct 7 '18 at 1:12




2




2




$begingroup$
Example if I understand definition of $A_i$ correctly. $11111000 in A_1 cap A_2$
$endgroup$
– Siong Thye Goh
Oct 7 '18 at 5:14




$begingroup$
Example if I understand definition of $A_i$ correctly. $11111000 in A_1 cap A_2$
$endgroup$
– Siong Thye Goh
Oct 7 '18 at 5:14




1




1




$begingroup$
$A_i$ has $1$ starting from position $i$, it is also possible to have $1$ at position $i-1$. $11111000$ has $5$ consecutive $1$. It is in $A_1$ since starting from position $1$, there are $5$ consecutive $1$'s. It is in $A_2$ since starting from position $2$, there are $4$ consecutive $1$'s.
$endgroup$
– Siong Thye Goh
Oct 7 '18 at 6:05




$begingroup$
$A_i$ has $1$ starting from position $i$, it is also possible to have $1$ at position $i-1$. $11111000$ has $5$ consecutive $1$. It is in $A_1$ since starting from position $1$, there are $5$ consecutive $1$'s. It is in $A_2$ since starting from position $2$, there are $4$ consecutive $1$'s.
$endgroup$
– Siong Thye Goh
Oct 7 '18 at 6:05




1




1




$begingroup$
@SiongThyeGoh: there is a more clean and effective approach : re. to this related post which leads to the solution I presented above.
$endgroup$
– G Cab
Oct 7 '18 at 19:34




$begingroup$
@SiongThyeGoh: there is a more clean and effective approach : re. to this related post which leads to the solution I presented above.
$endgroup$
– G Cab
Oct 7 '18 at 19:34











1












$begingroup$

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
= sumlimits_{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 - kleft( {r + 1} right) }{s - kleft( {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 = sumlimits_{left( {0, le } right),,m,,left( { le ,n} right)} {
sumlimits_{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 - kleft( {r + 1} right)}{ n - m - kleft( {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".






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Thanks, but feel that the last link is wrong, as it s about triangular numbers. Sorry, if wrong.
    $endgroup$
    – jiten
    Oct 8 '18 at 10:17
















1












$begingroup$

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
= sumlimits_{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 - kleft( {r + 1} right) }{s - kleft( {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 = sumlimits_{left( {0, le } right),,m,,left( { le ,n} right)} {
sumlimits_{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 - kleft( {r + 1} right)}{ n - m - kleft( {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".






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Thanks, but feel that the last link is wrong, as it s about triangular numbers. Sorry, if wrong.
    $endgroup$
    – jiten
    Oct 8 '18 at 10:17














1












1








1





$begingroup$

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
= sumlimits_{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 - kleft( {r + 1} right) }{s - kleft( {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 = sumlimits_{left( {0, le } right),,m,,left( { le ,n} right)} {
sumlimits_{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 - kleft( {r + 1} right)}{ n - m - kleft( {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".






share|cite|improve this answer











$endgroup$



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
= sumlimits_{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 - kleft( {r + 1} right) }{s - kleft( {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 = sumlimits_{left( {0, le } right),,m,,left( { le ,n} right)} {
sumlimits_{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 - kleft( {r + 1} right)}{ n - m - kleft( {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".







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








edited Oct 7 '18 at 19:24

























answered Oct 7 '18 at 17:42









G CabG Cab

18.3k31237




18.3k31237












  • $begingroup$
    Thanks, but feel that the last link is wrong, as it s about triangular numbers. Sorry, if wrong.
    $endgroup$
    – jiten
    Oct 8 '18 at 10:17


















  • $begingroup$
    Thanks, but feel that the last link is wrong, as it s about triangular numbers. Sorry, if wrong.
    $endgroup$
    – jiten
    Oct 8 '18 at 10:17
















$begingroup$
Thanks, but feel that the last link is wrong, as it s about triangular numbers. Sorry, if wrong.
$endgroup$
– jiten
Oct 8 '18 at 10:17




$begingroup$
Thanks, but feel that the last link is wrong, as it s about triangular numbers. Sorry, if wrong.
$endgroup$
– jiten
Oct 8 '18 at 10:17


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2945020%2fhow-many-bit-strings-of-length-8-have-at-least-a-block-of-at-least-4-contigu%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Bressuire

Cabo Verde

Gyllenstierna