How to figure out the number of possible subsets? Let S = $\{1, 2, 3, ..., n\}$. Let set A be a selection of integers from S. Let set B also be a selection of integers from set S.


*

*How many ways are there of choosing the elements for both A and B
such that every element in A is also in B?

*How many ways are there of choosing the elements for both A and B
such that every element in A is also in B, and B contains at least
one element not in A?
I'm not certain about it, but I have the feeling that problem one can be solved by just finding all possible subsets of B, so its solution is $2^n$. But given this line of reasoning, I can't seem to figure out what I should subtract from $2^n$ to account for any cases where all elements are the same in both sets. I'm stumped.
Thanks for any help.
 A: We solve the first problem. You can then solve the second by using the count of the first problem, and counting how many of these are "bad" (do not satisfy the added condition of the second problem).  
We want to choose two subsets $A$ and $B$ of $S$ such that $A\subseteq B$.  
Suppose that we have chosen such sets $A$, $B$. We will say that an element $k$ of $S$ is of Type 1 if  $k\in A$. We will say $k$ is of Type 2 if $k$ is in $B$ but not in $A$. And we will say $k$ is of Type $3$ if it is not in $B$.
Define $f:S\to\{1,2,3\}$ by letting $f(k)$ be the type of $k$.
Every function $f:S\to\{1,2,3\}$ determines a choice of $A$ and $B$ such that $A\subseteq B$. And conversely every choice of $A\subseteq B$ determines a function. Thus the number of choices is the number of functions, it is $3^n$. 
Remark: We can also solve the problem a longer way. Let $0\le i\le n$.
We can choose $i$ elements of $S$ to be in $A$ in $\binom{n}{i}$ ways. That leaves 
$n-i$ elements of $S$. We can pick a subset of this set to add to $A$ to make $B$ in $2^{n-i}$ ways. It follows that the total number of possibilities is
$$\sum_{i=0}^n \binom{n}{i}2^{n-i}.\tag{1}$$
We recognize (1) as the Binomial Theorem expansion of $(1+2)^n$. 
