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?
On
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.)
On
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$$
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.