Number of possible functions for a PRP

Question

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?

Answer 1

Yes, that's right. This is also why the key size can be much larger than the block size. The idea of a (well-distributed) key is that it pseudo-randomly chooses a function from X to Y.

So for instance AES can have a block size of 128 and a key size of 256 (and it has) because there are "only" $2^{256}$ keys while there are $2^{128}!$ possible functions / permutations. This is more explicitly explained here.