Sets Whose Elements Sum to an Even Integer

Question

From the set of integers $\{1,...,9\}$, how many nonempty subsets sum to an even integer.

This is probably trivial for most, but I am notoriously bad at counting, so I just want to make sure I am getting all the concepts straight. Given a subset of $S = \{1,...,9\}$, either its elements will sum to an even number or an odd number. It is clear from this consideration that the power set $\mathcal{P}(S)$ is partitioned to into sets whose elements sum to an even integer and sets whose elements sum to an odd integer. But every partition corresponds to a an equivalence relation, and we know the equivalence classes have the same number of elements. Thus these two sets that partition $\mathcal{P}(S)$ have the same number of elements. Hence $\frac{\mathcal{P}(S)}{2} = \frac{2^9}{2} -1= 2^8 -1= 255$ is the number of subsets whose elements sum to an even number.

Does this seem correct? If this is correct, this doesn't really feel like combinatorics proper. So I am wondering whether there is another way of solving the problem that is more combinatorial in nature. By the way, is it true for all sets, whether finite or infinite, that every partition arises from an equivalence relation and that every equivalence relation gives rise to a partition; and that the sets in the partition all have the same cardinality?

Answer 1

Looking at this charitably, you're right except that you may have missed out the empty set, whose sum is $0$; the answer is 256. However, I had to do some mental gymnastics to make your words into an answer: in particular, "we know the equivalence classes have the same number of elements" is confusing and is in general false (see final paragraph).

I think a more intuitive way of saying this is "Every subset of $\{1,2,\dots,9\}$ has a complement; since the sum $1+2+\dots+9$ is odd, the sum of each subset must have the opposite parity to the sum of its complement. So half the subsets are of odd sum."

You could also do this by induction. If it's true that half the subsets of $\{1,2,\dots,n-1\}$ are of even sum, then:

• Exactly half the subsets of $\{1,2,\dots,n\}$ which don't include $n$ are of even sum [inductive hypothesis]
• Exactly half the subsets of $\{1,2,\dots,n\}$ which do include $n$ are of parity equal to that of $n$ [inductive hypothesis but where we've added $n$ to every sum]

---

Every partition defines an equivalence relation: two things are equivalent iff they lie in the same region of the partition. Conversely, every equiv rel creates a partition: namely, the equivalence classes.

The sets in the partition need not have the same cardinality in general, unless I misunderstand you. Consider the partition {1,2},{3,4,5},{6,7,8,9} of {1,2,3,4,5,6,7,8,9}.