How many bit strings of length 10 contain either five consecutive 0s or five consecutive 1s?
Answers
The problem with your approach is that you are counting some arrangements more than once. Eg when you count by grouping and summing, you must take care that the groups are exclusive. For example, you count:
00000***** →25→25
*00000**** →25→25
but a configuration like 0000001111 belongs to both groups, hence you are couting it twice. And some, more than twice (eg, 0000000111 belongs to three groups).
To count the strings of 10 bits with at least 5 consecutive zeros, lets group them according to k=k= the first zero position in the (possibly larger than 5) run. Then k∈{1,2,3,4,5,6}k∈{1,2,3,4,5,6} (counting from one).
For k=1k=1, we have 2525 strings: ( 00000*****)
For k>1k>1 , we have 2424 strings (eg *100000***for k=3k=3)
This groping is exhaustive and exclusive. Hence the number of strings with at least 5 consecutive zeros is 25+5×24=11225+5×24=112
By symmetry, the number of strings with at least 5 consecutive ones is the same; however, this would count both 0000011111 and 1111100000twice (as you noticed), hence the total number is
112+112−2=222112+112−2=222
Notice that this method only works only because ℓ≥n/2ℓ≥n/2 (ℓℓ is the runlength, nn the total length) , otherwise more complicated methods would be needed (example).