This question already has an answer here:
- Counting functions between two sets 3 answers
In set theory and combinatorics, the cardinal number $n^m$ is the size of the set of functions from a set of size m into a set of size $n$.
I read this from this Wikipedia page.
I don't understand, however, why this is true. I reason with this example in which $M$ is a set of size $5$, and $N$ is a set of size $3$. For each element in set $M$, there are three functions to map the element from the set of size $5$ to an element in the set of size $3$.
By my reasoning, that means the total number of functions is just $3*5$, i.e. $3$ functions for each of the $5$ elements in the set. Why is it actually $3^5$? I saw on this thread that the number of functions from a set of size $n$ to a set of size $m$ is equivalent to "How many $m$-digit numbers can I form using the digits $1,2,...,n$ and allowing repetition?" I know how to answer that question, but I don't know why it's the same thing as finding the number of functions from the size $n$ set to the size $m$ set.