# Intro combinatorics question

1. Jan 16, 2009

### future_phd

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. Jan 16, 2009

### Staff: Mentor

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

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.

3. Jan 17, 2009

### future_phd

Ahh! That makes sense, that's probably what it's asking. Thanks! :D