In how many subsets of {1,2,3 ... 9,10} there are odd number of objects from {1,2,3,4,5} and even number of objects from {6,7,8,9,10}?

Question

In how many subsets of {1,2,3 ... 9,10} there are odd number/s of objects from {1,2,3,4,5} and even numbers of objects from {6,7,8,9,10} ? The answer I remember is 2^4 . 2^4 ( But It may not be correct )

Answer 1

The power set ${\cal P}(A)$ of $A:=\{1,2,3,4,5\}$ has an involution $\iota: \>S\mapsto A\setminus S$ which interchanges "odd" and "even" sets. It follows that exactly half of all $S\subset A$ are odd, and similarly, exactly half of all subsets of $B:=\{6,7,8,9,10\}$ are even. As $|{\cal P}(A)|=|{\cal P}(B)|=2^5$, the total number of subsets $T\subset (A\cup B)$ of the described kind is $2^4\cdot 2^4=256$.

Answer 2

For simplicity, lets denote $A=\{1,2,3,4,5\}$, $B=\{6,7,8,9,10\}$.

A subset of size 1: 5 elements from A and 0 from B, so there are 5 options.

A subset of size 2: Must be all of from $B$. So there are $5\cdot 4$ options.

A subset of size 3: There are two options: 3 elements from A, and then there are $5 \cdot 4 \cdot 3$ options, and 1 element from A, and then there are $5 \cdot 4 \cdot 5$ options. So overall there are $5 \cdot 4 \cdot 3+5 \cdot 4 \cdot 5$ options.

This goes on... But there probably is a smarter way of doing this.

Answer 3

To pick $k$ elements out of each of the halves can be done in $\binom{5}{k}$ ways, so to take $i$ elements out of the first half and $j$ out of the second can be done in $$ \binom{5}{i} \binom{5}{j} $$ ways. Bear with me for a moment: $$ (1 + z)^5 = \sum_{k \ge 0} \binom{5}{k} z^k $$ Now, if: \begin{align} f(z) &= \sum_{n \ge 0} a_n z^n \\ g(z) &= \sum_{n \ge 0} b_n z^n \end{align} then clearly: \begin{align} \frac{f(z) - f(-z)}{2} &= \sum_{n \ge 0} a{2 n} z^{2 n} \\ \frac{f(z) + f(-z)}{2} &= \sum_{n \ge 0} a{2 n + 1} z^{2 n + 1} \end{align} By the way in which polynomials ae multiplied: $$ f(z) g(z) = \sum_{n \ge 0} \sum_{0 \le k \le n} a_k b_{n - k} z^n $$ In our case \begin{align} f(z) &= \frac{(1 + \sqrt{z})^5 + (1 - \sqrt{z})^5}{2} \\ g(z) &= \frac{(1 + \sqrt{z})^5 - (1 - \sqrt{z})^5}{2 \sqrt{z}} \end{align} gives: $$ f(z) g(z) = \sum_{n \ge 0} \left( \sum_k \binom{5}{2 k} \binom{5}{n - 2 k} \right) z^n $$ But we are only interested in the full sum, which we get for $z = 1$: $$ \frac{(1 + 1)^5 + (1 - 1)^5}{2} \cdot \frac{(1 + 1)^5 - (1 - 1)^5}{2 \cdot 1} = 2^6 $$

Answer 4

You can simply sum up the following intermediate results:

• Choose $1$ object from $\{1,2,3,4,5\}$ and $0$ objects from $\{6,7,8,9,10\}$: $\binom{5}{1}\binom{5}{0}=5$
• Choose $1$ object from $\{1,2,3,4,5\}$ and $2$ objects from $\{6,7,8,9,10\}$: $\binom{5}{1}\binom{5}{2}=50$
• Choose $1$ object from $\{1,2,3,4,5\}$ and $4$ objects from $\{6,7,8,9,10\}$: $\binom{5}{1}\binom{5}{4}=25$
• Choose $3$ objects from $\{1,2,3,4,5\}$ and $0$ objects from $\{6,7,8,9,10\}$: $\binom{5}{3}\binom{5}{0}=10$
• Choose $3$ objects from $\{1,2,3,4,5\}$ and $2$ objects from $\{6,7,8,9,10\}$: $\binom{5}{3}\binom{5}{2}=100$
• Choose $3$ objects from $\{1,2,3,4,5\}$ and $4$ objects from $\{6,7,8,9,10\}$: $\binom{5}{3}\binom{5}{4}=50$
• Choose $5$ objects from $\{1,2,3,4,5\}$ and $0$ objects from $\{6,7,8,9,10\}$: $\binom{5}{5}\binom{5}{0}=1$
• Choose $5$ objects from $\{1,2,3,4,5\}$ and $2$ objects from $\{6,7,8,9,10\}$: $\binom{5}{5}\binom{5}{2}=10$
• Choose $5$ objects from $\{1,2,3,4,5\}$ and $4$ objects from $\{6,7,8,9,10\}$: $\binom{5}{5}\binom{5}{4}=5$

And you'll get $256$ (which is equal to what you remember).