How many maps of this set into itself question? Suppose we have a set $(1, 2, ... n)$, which has $2^n$ subsets. I am taking an introduction to analysis course, and I don't seem to understand the following two questions about this set:


*

*How many maps of this set into itself?

*How many maps of this set onto itself?


I understand the definitions of "into" and "onto" in this context, but I'm struggling with understanding what exactly they're asking. Any help?
 A: Call the set $S$. By "into" they mean any map $f\colon S\rightarrow S$. By "onto" they mean a map $f\colon S\rightarrow S$ whose image is $S$ itself (i.e. $f(S)=S$). That is, each element in the codomain is mapped to by some element in the domain.
A: Consider the function $f: A \rightarrow A$.
I think the answer would be 
$$\sum^n_{i=1} \left[\binom{n}{i} nPi \right]$$
Where $nPi$ is the permutations of length $i$ from an $n$ element set. 
My reasoning is that there are $\binom{n}{i}$ subsets of length $i$ coming from the domain $A$, and there are $nPi$ ways to arrange $i$ elements coming from the codomain $A$. Only the first $i$ elements of the codomain are selected, thus giving any permutations needed.  An injective function does not necessarily need every element in its domain or codomain to be used.
An example is when $n=2$, you have the following 6 injections:
1 to 1
1 to 2
2 to 1
2 to 2
1,2 to 1,2 (respectively)
1,2 to 2,1 (respectively)
We do not permute the domain, and only the codomain to avoid double counting.
A: There are $n^n$ maps from an $n$ element set to itself. 
A surjection from a finite set to itself is also an injection, hence a bijection. (Proof: If $f\colon X=\{1, \dotsc n\}\to X$ is a surjection, then $\{f^{-1}(x) \mid x\in X\}$ is a partitions $X$ into $n$ nonempty disjoint sets, so every $f^{-1}(x)$ must have exactly one element.) Thus, the number of surjections from $X$ to itself equals $n!$, as that is the number of bijections from $X$ to itself.
Note that in the general case, computing the number of surjections from a set of $n$ elements to a set of $k$ elements is more involved, and is answered here and here.
