Results 1 to 9 of 9

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

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    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 $\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.
    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 $\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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

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

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,782
    Thanks
    2824
    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 $\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?"
    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: Apr 10th 2011, 10:37 AM
  2. Combinatorics question
    Posted in the Statistics Forum
    Replies: 2
    Last Post: Dec 16th 2008, 10:12 AM
  3. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 10th 2008, 10:21 AM
  4. Combinatorics question
    Posted in the Advanced Math Topics Forum
    Replies: 5
    Last Post: Dec 8th 2007, 02:12 PM
  5. Combinatorics question
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Oct 10th 2007, 01:55 PM

Search Tags


/mathhelpforum @mathhelpforum