# combinatorics: number of subsets containing the same number of odds and evens

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

I got $462$, but I don't know if that is the correct answer.

The way I did it is that I made two subsets: one containing all the odd numbers and one containing all the even numbers. Then, I tried to find the possible combinations that will result in $0, 2,\ldots10$ elements and added them, giving me $462$.

• The number $462$ is correct. – André Nicolas Nov 9 '13 at 8:14
• I dont see anything wrong with your answer – Arief Anbiya Nov 9 '13 at 8:16

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

• Hello dera friend. :+) – mrs Nov 9 '13 at 14:10

Here is a slick but rather non-obvious way to solve the problem with less arithmetic. Suppose that $S$ is a subset of $A=\{1,2,\ldots,11\}$ with the same number of even and odd elements. Let

$$S^*=\{k\in S:k\text{ is even}\}\cup\{k\in A\setminus S:k\text{ is odd}\}\;.$$

In other words, $S^*$ is formed from $S$ by replacing the odd numbers in $S$ with the odd numbers that aren’t in $S$, while leaving the even numbers alone. The map $S\mapsto S^*$ is a bijection from $\wp(A)$ to itself, as may be seen by observing that it is its own inverse: $S^{**}=S$ for each $S\subseteq A$.

Let $\mathscr{E}$ be the collection of $S\subseteq A$ with the same number of even and odd elements, and let $\mathscr{E}^*=\{S^*:S\in\mathscr{E}\}$; $|\mathscr{E}|=|\mathscr{E}^*|$, so we’ll be done if we can count the sets in $\mathscr{E}$.

For $S\subseteq A$ let $e(S)$ be the number of even elements of $S$ and $o(S)$ the number of odd elements of $S$; $o(A)=6$, so $e(S^*)=e(S)$, and $o(S^*)=6-o(S)$. If $S\in\mathscr{E}$, then $e(S)=o(S)$, so $e(S^*)+o(S^*)=e(S)+6-o(S)=6$. Thus, $e(S)+o(S)=6$ for every $S\in\mathscr{E}^*$. Conversely, if $S\subseteq A$, and $e(S)+o(S)=6$, then $o(S^*)=6-o(S)=e(S)=e(S^*)$, so $S^*\in\mathscr{E}$, and therefore $S\in\mathscr{E}^*$. In short,

$$\mathscr{E}^*=\{S\subseteq A:e(S)+o(S)=6\}=\{S\subseteq A:|A|=6\}\;,$$

and therefore $$|\mathscr{E}|=|\mathscr{E}^*|=\binom{11}6=462\;.$$

(Writing it up carefully makes it look harder than it really is!)