In the Coursera crypto course, Dan Boneh states that if $F: K \times X \to Y$ is a PRF, if the size of the input space $X$ is $2^{128}$, and the size of the output space $Y$ is also $2^{128}$, then there are $(2^{128})^{(2^{128})}$ different functions that map the set $X$ to the set $Y$.
I guess that's because we can see this as a sampling with replacement : for each element in $X$ we pick a random element in $Y$, and replace the element in $Y$ before picking again. Once we're done, that make a random mapping from $X$ to $Y$, and so there are $(2^{128})^{(2^{128})}$ possible mappings.
What about PRPs? Because in a PRP the mapping functions must be invertible, can we see them as a sampling without replacement? And so, the number of possible functions from $X$ to $Y$ for a PRP should be $(2^{128})!$, is that right?
$(2^{128})^{(2^{128})}$
. More here. $\endgroup$ – fgrieu Oct 22 '16 at 9:34