Finding the number of subsets of S How can we find the number of subsets of $S=\{1,2,3,...,10\}$ that contain neither 5 nor 6?
Thanks!
 A: Say S is a subset. Ask yourself, "Is 1 in S?" You have two choices, yes or no. Then ask yourself, "Is 2 in S?", again two choices. For 5 and 6 you only have one choice, no. Every string of answers will define a unique subset S, clearly. The multiplication rule tells you that the total number of strings will be $2\cdot2\cdot2\dots\cdot1\cdot 1 \cdot 2\dots\cdot 2=2^8$. 
A: then you must find all subsets of {1,2,3,4,7,8,9,10}
so it is $2^8$
A: Think of the subsets of S as bit-strings; strings of bits where 0 means the element in that position is not in the subset, and 1 means it is.  Use the symbol x to mean a bit which could be either 0 or 1.  
We can express all of the subsets of S as xxxxxxxxxx and the subsets of S not containing 5 or 6 as xxxx00xxxx.
There are 2 possible values of x for each x in the string, so there are 2^10 subsets of S and 2^8 subsets of S that don't contain 5 or 6.  
A: HINT: The subsets of $S$ that contain neither $5$ nor $6$ are the subsets of $A=\{1,2,3,4,7,8,9,10\}$. How big is $A$? How many subsets does it have?
A: The general formula of finding the number of subsets of a set containing $n$ elements is $2^{n}$.
Assume that $A$ consists of 10 elements total from $1$ to $10$.  If we want to count the total number of subsets of $A$ that don't contain $5$ and $6$, then we remove them from the set $A$, which now contains 8 elements.  Thus, there are $2^{8}$ subsets of $A$.
Also, note that $\varnothing \subseteq A$.  This counts as a subset of $A$.  If we exclude $\varnothing$, and we have $8$ elements in $A$, then there are $2^{8} - 1$ subsets of $A$.
A: Suppose that a set $S$ has $k$ elements and it is $S=\{a_1,a_2,\dots, a_k\}$. Let the number of subsets of the $k-\text{element}$ set be $f(k)$. If a new element $a_{k+1}$ is introduced in the set $S$, the new set is $S'=\{a_1,a_2,\dots,a_{k+1}\}$. From each subset $T$ of $S$ we can form  new subsets of $S$ such that $T$ contains $a_{k+1}$ OR $T$ does not contain $a_{k+1}$.Thus, from each subset of $S$, 2 subsets of $S'$ are formed . Thus $f(k+1)=2f(k)=2^2f(k-1)=\dots=2^{k+1}$.
In your question, $k=8$ and number of subsets of the set in question is $2^8$.
Another way to count the number of elements of a $k-\text{element}$ subsets is the following: 
Every element is either in the subset or it is not. So, every subset may have $\displaystyle \binom{k}{0}$,$\displaystyle \binom{k}{1}$, $\displaystyle \dots,  \binom{k}{k}$ elements and hence the number of subsets of the $k-\text{element}$ subset is $\displaystyle \sum_{j=0}^k\binom{k}{j}=2^k$(by expanding $(1+1)^n$ using the binomial theorem.)
