Subsets of $\{1,2,3,4,5,6,7,8\}$ with at least 1 odd and 1 even number

Question

How can I formally write the number of subsets of $S=\{1,2,3,4,5,6,7,8\}$ with at least 1 odd and 1 even number?

I know if I take the subset with even numbers, $E =\{2,4,6,8\}$, there are $2^4-1$ subsets with even numbers (excluding $Ø$), and the same number for an the odd subset, $O$, and multiplying these together will give me an exact answer. But I'm not really satisfied because this isn't very formal, and I don't know how to show this with the proper mathematical symbols.

Thanks in advance !

Answer 1

What you said using words is quite formal enough.

Symbolically, you want:

$$\begin{align} &\quad\Bigl|\mathcal P(\{1,2,3,4,5,6,7,8\})\setminus \bigl(\{\varnothing\}\cup\mathcal P(\{1,3,5,7\})\cup\mathcal P(\{2,4,6,8\})\bigr)\Bigr| \\ &= \Bigl|\mathcal P(\{1,2,3,4,5,6,7,8\})\Bigr| - \Bigl(\bigl|\mathcal P(\{1,3,5,7\})\bigr|+\bigl|\mathcal P(\{2,4,6,8\})\setminus\{\varnothing\}\bigr|\Bigr) \\ &= 2^8-(2^4+2^4-1) \\ &= 2^8-2^5+1 \end{align}$$

Which is a little more compact, but conveys the same reasoning.

Answer 2

All non-empty subsets is $2^8 - 1$. There are $2^4 - 1$ non-empty subsets that consist only of even numbers, and $2^4 - 1$ non-empty ones that only have odd numbers. These are mutually exclusive sets.

We substract these last 2 from the first to get the right answer. This was my first approach.

Your answer is also correct, any good set can be seen as a unique disjoint union of a non-empty even set and a non-empty odd set. We can pick them independently, so we multiply.

Both come to 225.

Answer 3

Your answer is absolutely fine. If you want to be rigorous, notice the following properties:

1. The union of any non-empty subset of $\{1,3,5,7\}$ and $\{2,4,6,8\}$ is a subset of $\{1,2,3,4,5,6,7,8\}$ with at least one even and one odd member. (That is: "Your method only counts elements in the desired set")
2. Any subset of $\{1,2,3,4,5,6,7,8\}$ with at least one even and one odd member can be written uniquely as a union of non-empty subsets of $\{1,3,5,7\}$ and $\{2,4,6,8\}$ - explicitly, we find this by taking a subset $S$ with the desired property and intersecting it with $\{1,3,5,7\}$ for instance. (This is: "Every element is counted by your method" and uniqueness gives "No element is counted twice")

This establishes that your argument counts every set with the desired property exactly once and hence gets the right answer.