Bit strings of length 8 with either 2 1's in first 4 bits or 3 1's in last 4 bits So i'm trying to find out how many bit strings there are of length $n=8$ where there are either two 1's in the first four bits or 3 1's in the last 4 bits. 
Using the formula $C(n,r)=\frac{n!}{r!(n-r)!}$, there are $\frac{4!}{2!2!}=6$ bit strings of length 4 with 2 1's and $\frac{4!}{3!1!}=4$ bit strings of length 4 with 3 1's. 
However if the result was the sum of 6 and 4, this would include bitstrings where there are both 2 1's in the first half and 3 1's in the last half, so how do I exclude these bitstrings?
 A: First, it's not $6+4$. To count bit strings with two $1$s in the first half, we count as you did and then choose the last four bits arbitrarily, in any of the $2^4=16$ possible ways. After all, we're counting eight-bit strings, not four-bit strings. The same is true for the bit strings with three $1$s in the second half; there we choose the first four bits arbitrarily. That gives us $6\cdot 16+16\cdot 4$.
Now, how do we account for the bit strings with both two $1$s in the first half and three $1$s in the second half? We've double-counted them so far, so we need to subtract them to count them properly a total of once. Counting that "and" choice is a product: $6$ ways to choose the first four bits times $4$ ways to choose the last four bits, for a total of $6\cdot 4$. Combine all the pieces, and the count we seek is
$$6\cdot 16+16\cdot 4 - 6\cdot 4$$
If that's the exclusive "or", in which we don't count the bit strings with both two $1$s in the first half and three $1$s in the second half at all, we have to subtract those twice for a count of
$$6\cdot 16+16\cdot 4 - 2\cdot 6\cdot 4$$
A: Hint This is a standard application of the Inclusion-Exclusion Principle. If we denote by $A$ the set of $8$-bit strings with (exactly) $2$ $1$'s in the first four digits and by $B$ the set of strings with $3$ $1$'s in the last four digits, the number of strings satisfying one condition or the other but not both is
$$|A \triangle B| = |A \cup B| - |A \cap B| = (|A| + |B| - |A \cap B|) - |A \cap B| = |A| + |B| - 2 |A \cap B| .$$
Now, for example, if a string is in $A$, there are ${4 \choose 2} = 6$ choices for the first four bits and (independently) $2^4$ choices for the last four bits, so $|A| = 2^4 {4 \choose 2} = 96$, and we can compute $|B|$ similarly. Howe can we compute $|A \cap B|$?
