Total number of functions $f\colon S\to S$ where $S=\{1,2,3,4\}$ I missed a lecture on this topic and I'm having a hard time figuring out how this discrete function works. I'm given $S=\{1,2,3,4\}$ and $F =$ all functions from $S$ to $S$.
What does this mean?
I get that the domain and codomain must be $\{1,2,3,4\}$ but how do I define/figure out every function that goes from $S \to S\,$?
 A: The general idea is that we're absolutely free to choose where to send each element element of $S = \{1,2,3,4\}$. So, we can "build up" any function $f: S \to S$ starting by choosing where to send $1$.
$$1\ \overset{f}{\longmapsto}\ ??\quad (\text{four choices})$$
Now, once we've chosen where to send $1$, we get to choose where to send $2$:
$$2\ \overset{f}{\longmapsto}\ ??\quad (\text{four choices}),$$
and we would continue on, choosing where to send $3$ and $4$ as well.
In fact, if you think for a bit, you should decide that any list $(a_1, a_2, a_3, a_4)$ of four things in $S$ determines a function:
$$\begin{pmatrix}1 &2&3&4\\a_1&a_2&a_3&a_4\end{pmatrix},$$
where writing $a_1$ below $1$ means that $f(1) = a_1$.
A: This is probably the shortest/easiest way to think about it: For the function $f\colon S\to S$ to actually be defined, every element in the domain must map to a unique element in the codomain. Since $S=\{1,2,3,4\}$, we may "envision" the mapping combinations in the following manner:


*

*$1\mapsto \;?$ [Four choices]

*$2\mapsto \;?$ [Four choices]

*$3\mapsto \;?$ [Four choices]

*$4\mapsto \;?$ [Four choices]


Since $F$ is the set of all functions from $S$ to $S$, we know that $|F|=4\cdot 4\cdot 4\cdot 4= 4^4 = 256$. Thus, there is a total of $256$ functions from $S$ to $S$ when $S=\{1,2,3,4\}$. 
General case: Suppose, instead, that you were considering functions that mapped elements from an $m$-element set to an $n$-element set. How many functions would there be in total?
We may reason similarly as we did in your problem. There are $n$ choices for the first element, $n$ choices for the second element, and so on. Thus, we would have the following total number of functions from an $m$-element set to an $n$-element set:
$$
\underbrace{n\cdot n\cdot\ldots\cdot n}_{\text{$m$ times}} = n^m
$$
A: You can send the set $\{1,2,3,4\}$ to any subset of $\{1,2,3,4\}$ except $\phi$.
