finding the number of subsets and functions of $S_n$ Let $S_n = \{1,2,\ldots,n\}$
(a) for any positive integer $n$, find the number of subsets of $S_n$ which contain 1.  
I think this would be $2^{n-1}$ it seems to work when I test a few examples, however I am not quite sure behind the reasoning.  
(b) for any integer $n\ge 2$ find the number of subsets of $S_n$ which contain both 1 and 2.
pretty sure this would be $2^{n-1} \times  2^{n-1} = 2^{2n-2}$ is this correct?  
(c) for any positive integer $n$ find the number of functions $f: S_n  \rightarrow \mathscr P(S_n)$ so that $S_k \subseteq f(k) $ for all $k \in S_n.$ ($\mathscr P(S_n)$ is the power set of the set $S_n$ ). Answer should be in the form $2^M$ where $M$ is an expression involving $n$.    
I am stuck on (c), any help is appreacited.
 A: your second part is incorrect.
Since you have $1,2$ in your subset
every subset of $A\subseteq\{3,...,n\}$ corresponds to a subset of
$\{1,\ldots, n\}$ that contains $1,2$ by $A\cup\{1,2\}$ 
And every subset
$B\subseteq\{1,\ldots,n\}$ that contains both $1,2$ corresponds
to a subset of $\{3,...n\}$ by  $B\setminus\{1,2\}$.
Hence the number of such subsets is $2^{|\{3,\ldots,n\}|}=2^{n-2}$
A: For each of the elements $k$ of $S_n$ and any subset $A$ of $S_n$, either $k\in A$ or $k\notin A$. That gives us two options for each $k\in S_n$, so there are a total of $2^n$ subsets of $S_n$. Of these, half contain $1$ and the other half don't, so there are $2^{n-1}$ subsets of $S_n$ containing $1$. We'll need to cut that in half again to find the number of subsets containing both $1$ and $2$ (we certainly shouldn't have more subsets containing both $1$ and $2$ than we have subsets total). We can continue this trend for $k=3,...,n$.
Let's look at this in another light, to see how it might help us with part (c). Note that there are $2^{n-1}$ subsets of $S_n$ containing $S_1$ as a subset--according to part (a)--$2^{n-2}$ subsets of $S_n$ containing $S_2$ as a subset--according to part (b)--and continuing the trend, we generally have $2^{n-k}$ subsets of $S_n$ containing $S_k$ as a subset ($k=1,2,...,n$).
To make a function $f:S_n\to\mathscr{P}(S_n)$ as described in (c), then, for $k=1,...,n$ there are $2^{n-k}$ choices available for $f(k)$. Hence, there are $$2^{n-1}\cdot2^{n-2}\cdots2^{n-(n-1)}\cdot 2^{n-n}=2^0\cdot 2^1\cdots 2^{n-2}\cdot 2^{n-1}$$ such functions. Since $$0+1+\cdots +(n-2)+(n-1)=\frac{n(n-1)}2,$$ then there are a total of $$2^{\frac{n(n-1)}2}$$ such functions.
A: The way to an answer to (c) has been prepared by (a) and $(b)$.
How many choices do we have for $f(1)$? The condition on $f$ says that $S_1\subseteq f(1)$, that is, $1\in f(1)$.  So by the result of (a), there are $2^{n-1}$ choices for $f(1)$.
For every one of these choices, there are many choices for $f(2)$. The only condition on $f(2)$ is that $S_2\subseteq f(2)$, that is, that $1$ and $2$ are each in $f(2)$.  The correct answer to (b) is $2^{n-2}$, so that's how many choices there are for $f(2)$.
Once we have chosen $f(1)$ and $f(2)$, how many choices are there for $f(3)$? It is any set that contains $1$, $2$, and $3$, and there are $2^{n-3}$ of these. 
Continue. The total number of choices in making a function $f$ with the desired properties is
$$2^{n-1}\cdot 2^{n-2}\cdot 2^{n-3} \cdots 2^{n-n}.$$
By the usual laws for exponents, this is $2^M$, where 
$$M=(n-1)+(n-2)+(n-3)+\cdots +0.$$
that's a backwards way of writing $M=1+2+3+\cdots +(n-1)$. This sum simplifies to give $M=\dfrac{n(n-1)}{2}$.  
