Results 1 to 9 of 9

Math Help - Combinatorics Question

  1. #1
    Member
    Joined
    Oct 2010
    Posts
    95

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1607
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    Posts
    95
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1607
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2010
    Posts
    95
    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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1607
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Oct 2010
    Posts
    95
    Quote Originally Posted by Plato View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,657
    Thanks
    1607
    Awards
    1
    Quote Originally Posted by xEnOn View Post
    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?"
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Oct 2010
    Posts
    95
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. combinatorics question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 10th 2011, 10:37 AM
  2. Combinatorics question
    Posted in the Statistics Forum
    Replies: 2
    Last Post: December 16th 2008, 10:12 AM
  3. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 10th 2008, 10:21 AM
  4. Combinatorics question
    Posted in the Advanced Math Topics Forum
    Replies: 5
    Last Post: December 8th 2007, 02:12 PM
  5. Combinatorics question
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: October 10th 2007, 01:55 PM

Search Tags


/mathhelpforum @mathhelpforum