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.


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.


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.