2
$\begingroup$

How many subsets with an odd number of elements does a set with $10$ elements have?

I came up with this solution:

${10 \choose 1} + {10 \choose 3} + {10 \choose 5}+ {10 \choose 7} + {10 \choose 9} =512$.

But the solutions says it's $2^9=512$, which I don't kinda get. Aren't you counting the number of subsets with, for example, $2$ elements? (I know it's the same solution, it just doesn't make sense to me).

Can someone explain me why this is correct and what's the reasoning behind this?

$\endgroup$
3
$\begingroup$

One way to see this combinatorially is to consider the $10$ elements in some order. With the first $9$ elements, you have a free choice of either including it or not including it, for $2$ choices each. However, there's no choice for the $10$ element, as it must be included if the total # so far is even, and not included if the total # is odd. Thus, as there are $2$ choices for each of the first $9$ elements, there are $2^9$ choices overall.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Start with a ten element set and take one element out, calling it $x$. We now have a nine element set. For each subset, $S$, of the nine element set, either

  • $S$ contains an odd number of elements, so should be counted as a subset of the ten element set containing an odd number of elements.
  • $\{x\} \cup S$ has an odd number of elements, so should be counted as a subset of the ten element set containing an odd number of elements.

There are $2^9$ subset of a nine element set. We have shown that every one of these can be made into a subset of a ten element set having an odd number of elements.

What we have not shown is that every subset of a ten element set having an odd number of elements has been produced in this way. So, if a subset of a ten element set having an odd number of elements does not contain $x$, it is a subset of the nine element set, so is included in the count above. If a subset of a ten element set having an odd number of elements does contain $x$, deleting $x$ from that subset yields a subset of the nine element set having an even number of elements, so is included in the count above.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Suppose you pick a set a subset $X$ from $\{1,2,\cdots ,10\},$ construct the following function. If $10\in X,$ produce $Y=X\setminus \{10\}.$ If $10\not \in X,$ then make $Y=X\cup \{10\}.$ This is a bijection in between the subsets of odd size and the ones of even size. And so doing odds or even gives the same result and you know that doing evens and odds are $\sum _{i=0}^{10}\binom{10}{i}=2^{10}.$ So it has to be half of it. Meaning $2^9.$

If this combinatorial thing does not satisfies you, apply binomial theorem to $(1-1)^{10}.$ and separate positive and negative elements. What do you get?

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

The number of sets with odd power is the same as the number of sets with even power. So, since the number of all (sub)sets is $2^n$ the answer is $2^{n-1}$.

| cite | improve this answer | |
$\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.