1. ## Combinatorics Question

How many bit strings of length 10 can the bits of "1" be in pairs? Ie: 0110000110 has the property but 0011100110 does not)

My solution to this was to group the two 1bits into a block and the maximum pairs can only be 3 pairs in separated positions in a string of length 10. Then I choose the middle spaces between a string of zeros like this:
$\displaystyle \binom{9}{1}+\binom{7}{2}+\binom{5}{2}=40$

But The correct answer given was $\displaystyle \binom{11}{0}+\binom{9}{1}+\binom{7}{2}+\binom{5}{ 2}=40$

What I don't understand is why is there $\displaystyle \binom{11}{0}$ ? Why is there a 11 choose 0, which creates an additional 1 more possibility?

2. Originally Posted by xEnOn
How many bit strings of length 10 can the bits of "1" be in pairs? Ie: 0110000110 has the property but 0011100110 does not)
But The correct answer given was $\displaystyle \binom{11}{0}+\binom{9}{1}+\binom{7}{2}+\binom{5}{ 2}=40$
What I don't understand is why is there $\displaystyle \binom{11}{0}$ ? Why is there a 11 choose 0, which creates an additional 1 more possibility?
NOTE THAT $\displaystyle \binom{11}{0}+\binom{9}{1}+\binom{7}{2}+\binom{5}{ 2}=41$ not 40.
The term $\displaystyle \binom{11}{0}$ is counting a string of all zeros.

3. oh yea...sorry... typo on that one. You are right, it should be 41 for the correct answer.

If the term $\displaystyle \binom{11}{0}$ counts the string of all zeros, wouldn't it be wrong because the question only wanted the bits to be in pairs of "1"s? A string of all zeros have no pairs of "1"s but why is it being counted into the total ways?

4. Originally Posted by xEnOn
If the term $\displaystyle \binom{11}{0}$ counts the string of all zeros, wouldn't it be wrong because the question only wanted the bits to be in pairs of "1"s? A string of all zeros have no pairs of "1"s but why is it being counted into the total ways?
Is it not true that in the string $\displaystyle 0000000000$ ones appear in pairs?
That is that darn empty set for you.

5. Sorry but I am still a little confused.
The string 0000000000 is all in zeros and has no pairs of 1s. So how can I count that in?

Did you mean I have to count that in even though it has no pairs of 1s because an empty set has a cardinality of 1?

6. Originally Posted by xEnOn
Sorry but I am still a little confused.
The string 0000000000 is all in zeros and has no pairs of 1s. So how can I count that in?
Do you understand that a false statement implies any statement?
This is a true sentence, "If 1=2 then 1<0".
So is this statement, "If there is a one in 0000000000 then the ones appear in pairs" is a true.

7. Originally Posted by Plato
Do you understand that a false statement implies any statement?
This is a true sentence, "If 1=2 then 1<0".
So is this statement, "If there is a one in 0000000000 then the ones appear in pairs" is a true.
Thanks! I am not aware of this.
Maybe I am not used to this yet. I kind of still feel weird because then I could do the same to all, like not just $\displaystyle \binom{11}{0}$ but also add $\displaystyle \binom{9}{0}$, $\displaystyle \binom{7}{0}$ and $\displaystyle \binom{5}{0}$ because they all are false statements that is true. Then this would result to an even larger possible ways.

8. Originally Posted by xEnOn
I kind of still feel weird because then I could do the same to all, like not just $\displaystyle \binom{11}{0}$ but also add $\displaystyle \binom{9}{0}$, $\displaystyle \binom{7}{0}$ and $\displaystyle \binom{5}{0}$ because they all are false statements that is true. Then this would result to an even larger possible ways.
I agree with you that the question could be stated better.
It reads in mathematics speak as "How many 10-bit strings are there in which ones appear only in isolated pairs?"

9. hmm.. The only funny thing is in a 10-bit string, 0000000000, if all the places are already occupied by zeros, then there is no way I can have an isolated pair of 1s. The only way I can have a pair of 1s is to drop 2 zeroes to free up 2 "seats" for the pair of 1s. Otherwise, I could only imagine that despite all the "seats" are occupied by zero, there is still a pair of 1s in the "basket" that I haven't picked because I couldn't pick it, which this essentially makes that extra 1 more possbility.