I'm trying to solve how many twelve bit strings have more zeros than ones. Can someone sanity check my method please?
C(12,5) = 792 +
C(12,4) = 495 +
C(12,3) = 220 +
C(12,2) = 66 +
C(12,1) = 12 +
C(12,0) = 1 =
1586 ?
[Math] 12 bit strings with more zeros than ones
combinatorics
Related Solutions
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}$$
Your expression is correct. Here is another way that exploits the symmetry.
Let $a$ be the number of strings with more $1$'s than $0$'s, let $b$ be the number with more $0$'s than $1$'s, and let $c$ be the number with equal numbers of $0$'s and $1$'s.
Then $a=b$, $a+b+c=2^{12}$, and $c=\binom{12}{6}$. So $2a=2^{12}-\binom{12}{6}$ and therefore $$a=2^{11}-\frac{1}{2}\binom{12}{6}.$$
Best Answer
Your method is correct (apart from the way you write it down; as written, it reads as $C(12,5)=792+C(12,4)=\ldots=1=1586$, but clearly $C(12,5)\ne 792+C(12,4)$, … and $1\ne1586$), but unnecessarily complicated. A simpler way is as follows:
There are three types of 12 bit strings:
Obviously there are $2^{12}=4096$ 12 bit strings in total. Also, the number of strings of the first two types is equal, as you get one by bit-flipping the other. Finally, the last class has $\binom{12}{6}=924$ strings.
Therefore the first class (more zeroes than ones) has $(4096-924)/2 = 1586$ elements.