# Number of subsets of $A=\{1 ,2 ,3,…,8,9\}$ such that the maximum is in $B = \{1,3,5,7,9 \}$

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.

• The number of subsets in which $1$ is the maximum: $\{1\}$. The number in which $a$ is the maximum should be subsets of $\{1,2,...,a\}$ containing $a$. That is equinumerous to the subsets of $\{1,2,...,a-1\}$. That is $2^{a-1}$. – saltandpepper Mar 30 '18 at 17:24
• In your case $a=3,5,7,9$. Therefore, the total is $1+2^{3-1}+2^{5-1}+2^{7-1}+2^{9-1}=341$. – saltandpepper Mar 30 '18 at 17:31

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

• Thanks Nick. Much more concise and compact.. i even forgot to calculate the total number of subsets from $A$. – Arief Anbiya Mar 30 '18 at 17:44