Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am currently self-studying introductory combinatorics by reading Introduction to combinatorial mathematics. I am currently in the first chapter, and I have a question regarding one of the examples. The question was asking to count the number of n-bit strings with an even number of zeros. The answer is of course $2^{n-1}$. The author gave 2 solutions. I however didn't completely understand what I think is the straightforward one. The solution I got was that he took out 1 bit, leaving $(n-1)$ bits, if the number of zeros is even in the $(n-1)$-bit number, then he will just append a 1, if not then he will append a zero. So in the end we just needed to count the number of $(n-1)$-bit strings. The other solution (the straightforward one) that I didn't understand examined the symmetry that half of the $2^n$ must have an even number of zeros, and the other half will have an odd number of zeros. I just don't get why this property must hold. I can understand that half of the $2^n$ numbers will have even parity, but I can't see how it holds for the parity of the number of zero or one bits. If anyone can show me how that property holds, I'd be very grateful. I'd also be interested to see different explanations and proofs if possible.

Thank you.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

Divide the $2^n$ strings into two groups, one with an odd number of zeros and one with an even number of zeros. If you take anything from the "odd" group, and flip the first bit, you will get something in the "even" group. Similarly, flipping the first bit of anything in the "even" group will produce something in the "odd" group.

Once you realize that there is no chance of overlap (that is, flipping two different strings cannot give the same result), it means that the two groups have be exactly the same size.

share|improve this answer
1  
Thanks a lot, this is a simple and elegant way to think about it. Thank you. –  turingcomplete Jul 28 '12 at 23:57

One standard approach is that the number of strings with an even number of $0$'s is $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots.$$ The number with an odd number of $0$'s is $$\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots.$$

Recall that by the Binomial Theorem, $$(1+x)^n=\binom{n}{0}+\binom{n}{1}x+\binom{n}{2}x^2+\binom{n}{3}x^3+\binom{n}{4}x^4+\cdots.$$ Put $x=-1$. We get $$0=\binom{n}{0}-\binom{n}{1}+\binom{n}{2}-\binom{n}{3}+\binom{n}{4}-\cdots.$$ So the number with an even number of $0$'s is the same as the number with an odd number of $0$'s.

Overkill, but this generating functions approach can be used for other results. Not first chapter stuff, maybe second.

share|improve this answer
    
Thank you, this was also simple to follow and understand. –  turingcomplete Jul 28 '12 at 23:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.