This was an optional question given by my lecturer:
Given that $|X| = n$ and $|Y| = m$, how many functions are there from $X$ to $Y$?
I know that a function must take in every value $x \in X$, giving out only one value $y = f(x) \in Y$.
Assume that $n<m$.
Then for each element in $X$, there are $m$ choices to pick from for the value. So in total there would be $n^m$ choices to map $n$ elements from $X$ to the $m$ elements in $Y$.
Assume that $n>m$.
Then by similar reasoning, it will be $m^n$ choices.
If $m=n$ then the amount of ways is $n^n = m^m$.
Is this correct? If so is there a better way and if not, how would I have done this?
$\endgroup$ 42 Answers
$\begingroup$For each element in $X$, there are $m$ choices to pick from the total, hence in total, there are $$\overbrace{m \times \ldots \times m}^{n \text{ times}} = m^n.$$
The same argument works regardless of whether $m$ is bigger than $n$.
$\endgroup$ $\begingroup$n$^m$ as you indicated ; no need to have 3 cases , the reasoning is the same .Good job
$\endgroup$
