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 saw this two questions that I don't fully understand:

Let $E$ be the number of strings in $\{0,1\}^{17}$ with an even number of 1's, and Let $O$ be the number of strings with an odd number of 1's. What is $E-O$

The answer in the book is 0, but there's no explanation. Also

What is the number of strings in $\{0,1,2,3\}^{17}$ with an even sum of coordinates

The answer is $\frac{4^{17}}{2}$, but also no explanation. Thanks

share|improve this question

2 Answers 2

up vote 4 down vote accepted

If you write down a string with 17 digits, each of which is either $0$ or $1$, then you will either have an even number of $1$s and an odd number of zeros; or an odd number of $1$s and an even number of $0$s. So $E+O$ is the total number of strings.

However, if you take all strings, and in every string you exchange the roles of $0$ and $1$ (turn all $1$s to $0$s and all $0$s to $1$s) then you get back all strings again; but every string that was in $E$ will now be in $O$, and every string that was in $O$ will now be in $E$. That is, this operations swaps the contents of $E$ and $O$. So the number of elements in $E$ must be exactly the same as the number of elements in $O$. That is, $E=O$, so $E-O=0$.

Now consider the strings of length $17$ whose entries are $0$, $1$, $2$, or $3$. Exactly half of them have an even sum, and half have an odd sum. Why? Because of all strings of length $17$ with a given $16$ digit start, half will add up to an odd number and half will add up to an even number (those that end in $0$ and $2$ will have the same parity, those that end in $1$ or $3$ will have the same parity as each other, and opposite the parity of those that end in $0$ and $2$). Since there are $4^{17}$ strings total, half of them will add up to an even sum for a total of $\frac{4^{17}}{2}$.

share|improve this answer
    
Can I conclude from the first question (with a one-to-one relation) that every set $A=\{1,...,n\}$ has exactly $\frac{2^n}{2}=2^{n-1}$ sub-sets of even/odd size? –  yotamoo Mar 14 '12 at 17:52
    
@yotamoo: You can use complements to conclude that if $n$ is odd (since going from $B\subseteq A$ to $A-B$ will swap odd-sized subsets with eve-sized subsets). For $n$ even, though, that argument does not work; if you have some other way of establishing a correspondence between odd-sized subsets and even-sized subsets in that case, then yes. –  Arturo Magidin Mar 14 '12 at 18:05

For the first question, we can alternatively directly count both E and O like so:

Generally, the number of strings in $\{0,1\}^{17}$ with $k$ $1$'s is $\displaystyle\binom {17}k $, as we're ranging over all possible spots to put the $k$ ones in. So E equals the sum of this over all even numbers, and similarly O is the sum over all odd numbers. We can calculate

E - O $ = \displaystyle \sum_{i=0}^{8} \displaystyle \binom {17}{2i} - \sum_{i=0}^{8} \displaystyle \binom {17}{2i + 1} = \sum_{i=0}^{17} \displaystyle (-1)^i \binom {17}{i} = \sum_{i=0}^{17}\displaystyle 1^{n-i}(-1)^i \binom {17}{i} = (1-1)^{17} = 0^{17} = 0.$

However, this approach doesn't seem to lend itself to the next question directly, unless you notice that a sum is even iff the the number of $1$'s plus the number of $3$'s is even. In this case, you can consider $1$ and $3$ as one element, and $0$ and $2$ as one element (sorting them by parity). We're essentially looking for E here and so we can apply our result that E = O from above. Combined with the knowledge that E $+$ O = our total number of strings, $4^{17}$, we see that E = $\dfrac{4^{17}}{2}$.

A computational approach is helpful and possible, but the often superior option is to come up with what is called a combinatorial proof based on direct reasoning, as in Arturo or lhf's answers. As Stanley writes in enumerative combinatics,

Not only is the above combinatorial proof much shorter than our previous proof, but also it makes the reason for the simple answer completely transparent. It is often the case, as occurred here, that the first proof to come to mind turns out to be laborious and inelegant, but that the final answer suggests a simple combinatorial proof. (page 12)

share|improve this answer

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.