Number of $k-$subsets of $ \lbrace 1,2, \ldots ,n \rbrace$ with even sum.

Question

Using generating functions it is easy to show that the number $e(n,k)$ of all $k-$subsets of $ \lbrace 1,2, \ldots ,n \rbrace$ such that the sum of their elements is even is given by $$\sum_j{\binom{ \lceil {n/2} \rceil}{2j}\binom{ \lfloor {n/2} \rfloor }{k-2j}}.$$ Is there a direct combinatorial proof of this fact?

Answer 1

Let $L$ be set of odd numbers up to $n$ and $S$ set of even numbers up to $n$.

So $|L| = \lceil {n/2} \rceil$ and $|S| = \lfloor {n/2} \rfloor$.

Then you must take always $2j$ odd numbers from the set $L$, (thus you can do this on $\displaystyle {\lceil {n/2} \rceil \choose 2j}$ ways)

and the rest of them , that is $k-2j$ form the set $S$ (and you can do this on $\displaystyle {\lfloor {n/2} \rfloor \choose k-2j}$ ways).

So for fixed $j$ you can do this on $\displaystyle {\binom{ \lceil {n/2} \rceil}{2j}\binom{ \lfloor {n/2} \rfloor }{k-2j}}$ ways.

You can do this for all $j\leq \displaystyle \lceil {n/4} \rceil$ thus the sum.