# how many subsets of $\{1,2,3,4,5,6,7\}$ has $6$ as largest?

Let $A =\{1,2,3,4,5,6,7\}$, The how many subsets have 6 as largest element?

My approach -

Total subsets are $2^7 = 128$. Then First I have to exclude the $1$ empty subset i.e. $\{\}$, $6$ sets with $1$ element except $\{6\}$, then two elements not containing $6$ as its element(I am not getting a way to count these element) and the $2$ subsets $\{6,7\},\{7,6\}$. Then I am stuck here as I am not getting the way to count these numbers. Any help?

• Well, none of the sets have 7 so this is the same as asking what are the subsets of B = {1.... 6} they all have 6 so all sets are equal to $C \cup \{6\}$ for some set C. C is a subset of $\{1,...., 5\}$ so we just need to find the subsets of {1,2...5} and add {6} to all of them. There are $2^5$ subset of {1,2....5} so there are the same number of subsets of {12,...5,6} that must have 6 which is the same number of subsets of {1,2,....7} that must have 6 and must not have 7. – fleablood Aug 25 '16 at 19:58
• 128 subsets. Half have 6 as an element. 1/4, contain both 6 and 7. So 1/4 have 6 and do not have 7. – Doug M Aug 25 '16 at 20:23

Remember how we determined that the number of subsets was 2 to the power of the number of elements.

We did that because for each element, $a$, either $a$ could be in a subset. So the total number of sets was the product of all the choices each of which was 2.

This is the same. Either 1 is in a subset or not. That 2 choices. Either 2 is in the subset or not. That's $2*2$ choice. Keep it up EXCEPT notice $6$ must be in the subset so that is only $1$ choice and $7$ must not be in the set so that's only one set.

So the number of sets is $2*2....*2*1*1$ which is what.

....

Or

....

Don't eliminate the sets one at a time. Remove ALL the subsets that do not have $6$ in them. How many do not have $6$. Remove ALL the subsets that do have $7$. How many is that? Then to avoid double counting add back the ones that had $6$ and didn't have $7$. How many is that?

....

Or

....

Figure 1/2 of the 128 have 6 and half do not. That only leaves half of them acceptable. Then half of those have 7 and half to not. That leaves only half of those acceptable.

....

Or

....

No set has $7$. So all the elements are taken from {$1,2,3,4,5,6$}.

All sets have $6$. So all elements that aren't $6$ are taken from {$1,2,3,4,5$} and $6$ is always added to it.

There are $2^5$ subsets of {$1,2,3,4,5$} and we are only taking those and sticking a $6$ into them. There are $2^5$ such sets.

• I like your way of dividing it up. That makes good sense! – John Aug 25 '16 at 20:16
• You have to be careful in assuming that your condition is exactly 1/2 though. In this case you can but if you were asked say How many sets have the numbers add up to an even number and contain the number 5 you can't assume half the sets add up to an even number and of those half of them contain 5. – fleablood Aug 25 '16 at 20:23

Hint:

Include $6$. How many ways are there to include zero through five members of $\{1,2,3,4,5\}$?

(Order doesn't matter with sets.)

• okay now i got. There are total subsets = 2^6 = 64. – Brij Raj Kishore Aug 25 '16 at 19:58
• The element $6$ has to be there. The element $7$ can't be in there. But any, all, or none of $1$ through $5$ can be. In other words, if $S_5 = \{1,2,3,4,5\}$, then the union of $\{6\}$ and any subset of $S_5$ will have $6$ as the largest element. You figured out the number of subsets for a set of $7$ elements. How about for $5$ elements? – John Aug 25 '16 at 20:02
• Regarding your answer, not quite. It's not optional whether $6$ is in there or not. – John Aug 25 '16 at 20:03
• So the answer is 2^6 -1 - 5. Am i correct? But in option there are 4 options as - 32,31,64,128. – Brij Raj Kishore Aug 25 '16 at 20:05
• No set has 7. All sets have 6. So all sets are a subset of {1,2,3,4,5} unioned up with {6}. How many sets are there. There is {6} = {} + {6}; there is {1,4,5,6} = {1,4,5} + {6}. They are all C + {6} where $C \subset$ {1,2,3,4,5}. How many such sets are there. – fleablood Aug 25 '16 at 20:14

Think about it we need $6$ as an element but we can't have $7$ because $7$ is larger than $6$, we can have anything else.

What we're looking for: How many subsets have $6$ as an element but not $7$?

We must choose to include $6$, that gives $1$ choice. We may choose to to include $1$ or not, that gives $2$ choices. We may choose to include $2$ or not, that gives $2$ choices. We may choose to include $3$ or not, that gives $2$ choices. We may choose to include $4$ or not, that gives $2$ choices. We may choose to include $5$ or not, that gives $2$ choices. We must choose not to include $7$, that gives $1$ choice. By the multiplication principle the number subsets with $6$ but not $7$ is:

$$1•2•2•2•2•2•1=2^5$$