1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Intro combinatorics question

  1. Jan 16, 2009 #1
    1. The problem statement, all variables and given/known data
    Find a one-to-one correspondence between the binary strings (i.e. sequences of 0's and 1's) of length k that have an odd number of 1's, and those that have an even number of 1's.

    2. Relevant equations

    3. The attempt at a solution
    I'm not exactly sure of what it's asking me to do.
    If it's of length k, then you have 2^k different combinations. Half of these will have an even number of 1's, half will have an odd number. So you get (2^k)/2 or 2^(k-1) with an odd number of 1's, and 2^(k-1) with an even number of 1's. Not exactly sure where to go from here.
    Last edited: Jan 16, 2009
  2. jcsd
  3. Jan 16, 2009 #2


    Staff: Mentor

    If I understand this problem correctly, it's very easy. There's no guarantee that I understand it correctly, though.:biggrin:

    Consider a binary string of length k, with n 1's and (k - n) 0's. Form a new string of the same length, switching 1's to 0's and 0's to 1's. The new string will have n 0's and (k - n) 1's.

    This is clearly a 1:1 mapping, and I think you can satisfy yourself that if the first string had an odd number of 1's, the new string will have an even number of 1's.
  4. Jan 17, 2009 #3
    Ahh! That makes sense, that's probably what it's asking. Thanks! :D
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook