# find the number of subsets of S={1,2,3,…10} that contain exactly 5 elements, the sum of which is even

I noticed that the sum of any even number of odds with any other even numbers is even.

So, in making 5 elements I counted only the ones with 2 odd numbers, the rest being even

for example 1 3 2 4 6

and 4 odd number, the last number being even, and of of course the set itself, which is even.

for example 1 3 5 7 2

for dealing with 2 odds, I did 5 choose 2 or C(5,2) which gave me 10

for dealing with 4 odds, I did 5 choose 4 or C(5,4) which gave me 5

This sums up to 11. However, when i compared it with the actually solution it is wrong.

What did i do wrong?

There are 3 cases to be considered that leads to the sum to be an even number.

Case 1: 0 odd, 5 evens: 2, 4, 6, 8, 10. So there is 1 solution set.

Case 2: 2 odds, 3 evens: example: 3, 5, 2, 6, 10. There are C(5,2)*C(5,3) = 100 sets.

Case 3: 4 odds, 1 even. There are C(5,4)*C(5,1) = 25 sets.

So there are: 126 sets in total.

We need to choose $1$ even and $4$ odd, or $3$ even and $2$ odd, or $5$ even and $0$ odd. The total is $$\binom{5}{1}\binom{5}{4}+\binom{5}{3}\binom{5}{2}+\binom{5}{5}\binom{5}{0}.$$ There is a little less work if we notice that $\binom{5}{5-k}=\binom{5}{k}$.

Remark: The following argument is fancier, but more informative. Let $n$ be odd. We ask how many ways there are to choose $n$ numbers from the numbers $1,2,3,\dots, 2n$ so that the sum is even.

Note that the sum of the numbers $a_1,a_2,\dots, a_n$ is odd if and only if the sum of the $n$ numbers $2n+1-a_1,2n+1-a_2, \dots, 2n+1-a_n$ is even.

Thus there are exactly as many ways to choose $n$ numbers with odd sum as there are to choose $n$ numbers with even sum. It follows that the required number is $\frac{1}{2}\binom{2n}{n}$.

For $n=5$, we get $\frac{1}{2}\binom{10}{5}$, which is $126$. But for $n=5$, the simple enumeration of cases is a more reasonable approach.

The situation for even $n$ can also be analyzed. It turns out that the number of $n$-subsets with even sum is $2^{n-1}$.

Here is a proof using generating functions of the count of subsets of the set $\{1,2,3,\ldots,2n\}$ with $n$ elements whose sum is even.

By inspection the bivariate ordinary generating function of these sets by total sum (variable $z$) and number of elements (variable $u$) is $$f(z, u) = \prod_{k=1}^{2n} (1 + u z^k).$$

Now we are not interested in the value of the sum, only its parity. Observe that the univariate generating function of the subsets with even parity by the number of elements is given by $$\frac{1}{2} f(+1,u) + \frac{1}{2} f(-1, u).$$

Actually doing the substitution for $z$ this produces $$\frac{1}{2} \prod_{k=1}^{2n}(1 + u) + \frac{1}{2} \prod_{k=1}^{2n}(1 + u (-1)^k) = \frac{1}{2} (1+u)^{2n} + \frac{1}{2} ((1+u)^n \times (1-u)^n) \\ = \frac{1}{2} (1 + u)^{2n} + \frac{1}{2} (1 - u^2)^n.$$

Now there are two cases, the first of which is that $n$ is odd and the second that $n$ is even.

Note that the second power in $1-u^2$ does not contain odd powers so that when $n$ is odd only the first term contributes. By the binomial expansion we get the result $$[u^n] \frac{1}{2} (1 + u)^{2n} = \frac{1}{2} {2n\choose n},$$ which incidentally also follows by inspection with no additional algebra needed.

On the other hand when $n$ is even the second term contributes the value $$[u^n] \frac{1}{2} (1-u^2)^n = \frac{1}{2} (-1)^{n/2} {n\choose n/2}$$ for a total of $$\frac{1}{2} {2n\choose n} + \frac{1}{2} (-1)^{n/2} {n\choose n/2}.$$

These two formulas taken together produce the following sequence: $$1, 2, 10, 38, 126, 452, 1716, 6470, 24310, 92252, \ldots$$

This is sequence OEIS A119358.

Notice the bijection between sets which add to $15+k$ and $40-k$ for $0 \leq k \leq 12$

Thus, there are the same amount of odd sets as even sets.

Therefore, the answer is $\frac{1}{2} {10 \choose 5} = 126$.