0
$\begingroup$

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 )

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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 $$

$\endgroup$

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.