Number of Bit Strings with Five Zeros How many bit strings of length 10 contain either five consecutive 0's or five consecutive 1's?
I think the answer to this question is:
10!/(5!*5!), according to book-keepers rule. Since, there are 10! total permutations, with 5 zeros being indistinguishable and five ones being indistinguishable. But I'm confused about the keyword, "either". Please help, thanks. :)
 A: NOTE: This answer assumes that the OP asks for the number of bit strings with EXACTLY 5 consecutive 0's or 1's. It does not work if you're looking for the number of bit strings with AT LEAST 5 consecutive 0's or 1's.

There are 10 bits, so there's a total of $2^{10}=1024$ possible cases.
Let see the case of 5 consecutive 0's.
Then, we need at least a 1 in every end (if there wasn't, it would be 6 consecutive 0's). Let's see all possible arranges ($x$ is a bit whose value doesn't matter, so it could be either a 1' or a 0':
$$\begin{array}{rcl}
000001xxxx&&6\text{ numbers fixed, so }2^4\text{ cases}\\
1000001xxx&&7\text{ numbers fixed, so }2^3\text{ cases}\\
x1000001xx&&7\text{ numbers fixed, so }2^3\text{ cases}\\
xx1000001x&&7\text{ numbers fixed, so }2^3\text{ cases}\\
xxx1000001&&7\text{ numbers fixed, so }2^3\text{ cases}\\
xxxx100000&&6\text{ numbers fixed, so }2^4\text{ cases}
\end{array}$$
So there's $2\cdot 2^4 + 4\cdot2^3=2^5+2^5=2^6=64$ bit strings with 5 consecutive 0's.
The case of 5 consecutive 1's is exactly the same, so there's 64 bit strings with 5 consecutive 1's.
But, note we are counting twice the cases with 5 consecutive 1's and 5 consecutive 0's:
$$0000011111\qquad 1111100000$$
So we need to substract 2 (2 possible bit strings) for a total of:
$$64+64-2=126\text{ bit strings with either 5 consecutive 0's or 1's}$$
A: The question, as is all too often the case, is ambiguous. Do we mean exactly $5$ consecutive $0$'s, or at least $5$? We take the at least interpretation.
How does one interpret "either $\dots$ or?" Does the string with $5$ $0$'s followed by $5$ $1$'s qualify?  We will do violence to ordinary English (but not to mathematical English) by deciding that it does qualify. 
We first count the strings with (at least) $5$ consecutive $0$'s.
The consecutive string could start at the leftmost bit. There are $2^5$ ways to complete.
It could start at the second bit. Then the first bit is $1$, and there are $2^4$ ways to complete. 
It could start at the third bit. Then the second bit is $1$, the first bit is arbitrary, as are the last $3$, for a total of $2^4$. 
Starting at the fourth, fifth, sixth each contribute another $2^4$.
The total is $112$.
We have the same number with consecutive $1$'s.
However, we have double-counted the $2$ strings that have $5$ consecutive $0$'s and $5$ consecutive $1$'s.
The total is therefore $222$. If we use the exclusive or interpretation of "either $\dots$ or" this shrinks to $220$.
A: Lets count the strings that don't have $5$ consecutive equal bits. Call such a string a "funny string".
To do this we shall create the function $f(n)$. This function counts how many "funny strings" of length $n$ there are.
It is clear $f(1)=2,f(2)=4,f(3)=8,f(4)=16,f(5)=30$
We shall now find a recurrence:
suppose we want to count the number of funny strings of length $n$. We called this number $f(n)$ . We can classify these strings into two types:
First type: Those strings in which the last bit is different to the second to last bit. There are $f(n-1)$ of this type since removing the last bit gives us a funny string of length $n-1$. And for any funny string of length $n-1$ we can create a funny string of length $n$ by adding a digit at the end that is different to the previous last digit.
Second type: These are the strings in which the last two digits are equal. The number of funny strings of this type is equal to the number of funny strings of length $n-1$ that do not end in four consecutive bits of the same type. How many of these are there?
It is easier once again to count how many funny strings of length $n-1$ do end in $4$ equal bits. There are $f(n-5)$ of these. Why? Suppose you are given a funny string of length $n-1$ that ends in $4$ equal bits. Then you can take away those $4$ last bits and you shall get a "funny string" of length $n-5$ where the last bit is different from the 4 bits you just removed. Conversely given a "funny string" of length $n-5$ if you add 4 digits different from the last one at the end you shall get a funny string of length $n-1$ that ends in $4$ equal bits.
So there are $f(n-5)$ funny strings that end in $4$ digits of the same length, and therefore there are $f(n-1)-f(n-5)$ funny strings of  length $n$ of the second type.
Therefore we get $f(n)=2f(n-1)-f(n-5)$
following up our previous table and using the recursion we get:
$f(1)=2,f(2)=4,f(3)=8,f(4)=16,f(5)=30,f(6)=58,f(7)=112,f(8)=216,f(9)=416,f(10)=802$
So there are $802$ strings of length $10$ that don't have five consecutive equal bits. Thus there are $1024-802=222$ that do.
A: Suppose you have a bit string of zeros and ones, like $1110010011111101001$. This can be described (up to complementation, or flipping every bit in the string) by the lengths of the runs of $1$s and $0$s. In other words, $1110010011111101001$ or its complement, $0001101100000010110$, can be described be the sequence of run lengths $3:2:1:2:6:1:1:2:1$. If the string has $n$ bits, these run lengths add up to $n$. Such a decomposition of $n$ into an ordered sum of positive integers is called a composition of $n$. The compositions of $n$ are in one-to-two correspondence with the length $n$ bit strings. (There are two choices for the first bit, and then the composition describes the string.)
A bit string with a run of at least $5$ of the same bit will have an associated composition that contains a number that is greater than or equal to $5$. 
Therefore, the number of length $n$ bit strings with no run of $5$ zeros or ones is two times the number of compositions of $n$ using parts from $1$ to $4$.
The number of compositions of $n$ using parts from $1$ to $4$ is the $n+3$-rd "tetranacci" number. See https://oeis.org/A000078.
For $n=10$, the $n+3$-rd tetranacci number is $401$, so there are $802$ length-$10$ bit strings that do not contain a run of length at least $5$. There are $1024$ strings of length 10 in all, leaving $222$ that do contain a run of length $5$.
