# Combinatorics Question

• May 2nd 2011, 03:12 AM
xEnOn
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:
$\binom{9}{1}+\binom{7}{2}+\binom{5}{2}=40$

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

What I don't understand is why is there $\binom{11}{0}$ ? Why is there a 11 choose 0, which creates an additional 1 more possibility?
• May 2nd 2011, 03:34 AM
Plato
Quote:

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 $\binom{11}{0}+\binom{9}{1}+\binom{7}{2}+\binom{5}{ 2}=40$
What I don't understand is why is there $\binom{11}{0}$ ? Why is there a 11 choose 0, which creates an additional 1 more possibility?

NOTE THAT $\binom{11}{0}+\binom{9}{1}+\binom{7}{2}+\binom{5}{ 2}=41$ not 40.
The term $\binom{11}{0}$ is counting a string of all zeros.
• May 2nd 2011, 03:38 AM
xEnOn
oh yea...sorry... typo on that one. You are right, it should be 41 for the correct answer.

If the term $\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?
• May 2nd 2011, 03:49 AM
Plato
Quote:

Originally Posted by xEnOn
If the term $\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 $0000000000$ ones appear in pairs?
That is that darn empty set for you.
• May 2nd 2011, 03:55 AM
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?

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?
• May 2nd 2011, 04:07 AM
Plato
Quote:

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.
• May 2nd 2011, 04:14 AM
xEnOn
Quote:

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 $\binom{11}{0}$ but also add $\binom{9}{0}$, $\binom{7}{0}$ and $\binom{5}{0}$ because they all are false statements that is true. Then this would result to an even larger possible ways.
• May 2nd 2011, 04:20 AM
Plato
Quote:

Originally Posted by xEnOn
I kind of still feel weird because then I could do the same to all, like not just $\binom{11}{0}$ but also add $\binom{9}{0}$, $\binom{7}{0}$ and $\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?"
• May 2nd 2011, 04:30 AM
xEnOn
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.