Let $m,n$ be positive integers. Let $X$ be a set with $m$ distinct elements and $Y$ with a set with $n$ distinct elements. How many distinct functions are there from $X$ to $Y$?
I was thinking the following:
If $n=m$, then there are $n!$ distinct functions. If $n>m$, then we have $nPm$ distinct functions ($P$ stands for permutation) and I am not sure about the case where $ n<m$. If $n<m$ the function $f$ should be a many-to-one function by the Pigeonhole principle, but I cannot enumerate the number of distinct functions for this case.
Any input, help and correction is much appreciated.
Best Answer
Your proposed answer of $nPm= \frac{n!}{(n-m)!}$ seems to indicate that you are thinking only about one-to-one functions from $X$ to $Y$. if $X = \{ x_1 , x_2, \ldots , x_m \}$, there are $n$ choices for $f(x_1)$, and $n-1$ choices for $f(x_2)$, etc., until we arrive at there being $n-(m-1)$ choices for $f(x_m)$. This results in a total of $$n \cdot (n-1) \cdot \cdots \cdot (n-(m-1)) = nPm$$ distinct (one-to-one) functions.
Of course, not all functions $X \to Y$ are one-to-one. Instead, there are $n$ choices for $f(x_1)$, and then $n$ choices for $f(x_2)$, etc. This results in a total of $$\overbrace{n \cdot n \cdot \cdots \cdot n}^{m\text{ times}} = n^m$$ different functions from $X$ to $Y$.