1
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Just to clarify: this is because a sum will be even if and only if the number of odd sumands will be even. $\endgroup$ – 5xum Aug 17 '17 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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