What is the number of subsets of $A=\{1 ,2 ,3,…,8,9\}$ such that the maximum is in $B = \{1,3,5,7,9 \}$?
For example :
Subset {1, 2} is not in context, since the maximum is not in $B$.
Attempt : I have solved this in a tedious way.
First, I calculate the number of subsets such that it contains even numbers :
Let $\{2, (3,5,7,9) \}$ means that we can put 3, 5, 7, 0r, 9 in $\{ 2, \_ \}$
- For two-element subsets with one only even number :
$\{2, (3,5,7,9) \}$ means that there are 4 subsets
$\{4, (5,7,9) \}$ means that there are 3 subsets
$\{6, (7,9) \}$ means that there are 2 subsets
$\{8, 9 \}$ means that there is 1 subset
in total 10 subsets.
- For three-element subsets with one only even number :
$\{2, (3,5,7,9), \_ \}$ the empty gap can be filled by 9-2-3 = 4 possible elements (because we cannot have 4, 6, and 8 in there). There are 4 $\times$ 4 subsets.
$\{4, (5,7,9), \_ \}$ same reasoning as above. There are $3 \times 4$ subsets.
$\{6, (7,9), \_ \}$ There are $2 \times 4$ subsets.
$\{8, 9, \_ \}$ means that there is 4 subsets.
So it is just $10 \times 4 = 40$, the previous times 4.
And so on….
Without even numbers, the number subsets are from $B$, which is $2^{5} = 32$.
In total, i have counted the number of subsets is $1722$. I am quite sure this is correct, but this is quite tedious, are there better ways? Thanks.
Best Answer
The answer that you've gotten can't possibly be correct; after all, there are only $2^9=512$ TOTAL subsets of $\{1,2,\ldots,9\}$. So, there's some definite over-counting happening here.
A simpler way to go about things: you can break this up more easily by partitioning the subsets based on the maximum.
How many choices have maximum element $1$? Well, there's only one such subset: $\{1\}$.
How many subsets have maximum element $3$? You must include $3$, and can choose whether or not to include $1$ and $2$. So, there are $4$ possibilities.
For maximum element $5$, you must include $5$; you can choose whether or not to include the elements $1,2,3,4$. So, there are $2^4=16$ possibilities.
Continuing in this way, the total number of subsets is $$ 2^0+2^2+2^4+2^6+2^8=341. $$