# Subsets that contain equal amounts of even and odd integers

Someone asked this question:

Compute the number of subsets of a set $A := \{1,2,...,11\}$ that contain the same number of even and odd values, e.g. the subsets $\{\}$,$\{1,2,5,8\}$ and $\{3,5,8,10\}$ should be counted, but the subsets $\{1,2,3\}$, $\{1,2,3,5,6\}$ and $\{1,2,...,11\}$ shouldn't.

and a person replied with this answer:

$\{1,3,5,7,9,11\}$, $\{2,4,6,8,10\}$ $${6 \choose 0}{5 \choose 0}+{6 \choose 1}{5 \choose 1}+{6 \choose 2}{5 \choose 2}+{6 \choose 3}{5 \choose 3}+{6 \choose 4}{5 \choose 4}+{6 \choose 5}{5 \choose 5} =$$ $$=1 + 30 +150 + 200 + 75 + 6 = 462$$

could someone please explain how this was worked out, because i don't understand.

## 1 Answer

Let the number of even elements (which equals the number of odd elements) be $k$. To form such a subset we need to choose $k$ of the $6$ odd elements (which can be done in $6 \choose k$ ways) and $k$ of the $5$ even elements (which can be done in $5 \choose k$ ways). So the number of subsets is then $6 \choose k$ $5 \choose k$. The number $k$ can equal $0,1,2,3,4,5$ and so to find the total number of subsets we sum over these possibilities.