# Number of distinct functions between two finite sets

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.

-
You may find this relevant: en.wikipedia.org/wiki/Twelvefold_way – Austin Mohr Oct 8 '12 at 18:14

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$.

-

It is worth noting that for two sets $X$ and $Y$ (not necessarily finite), the set of all functions $X \to Y$ is denoted by $Y^X$. One benefit of this notation is that, by generalising some of the arguments you've seen in the other answers, there is a nice expression for its cardinality, namely $$\left|Y^X\right| = |Y|^{|X|}.$$ In your situation $|X| = m$ and $|Y| = n$ so you get the result you've deduced above. What is really interesting is that the relationship between the cardinalities is true even for infinite sets (provided you use cardinal arithmetic).

-
Interesting! Thanks for the info! – Daniel Oct 8 '12 at 22:27

$n^m$.

Its the same as this question:

How many $m$-digit numbers can I form using the digits $1,2,\ldots,n$ and allowing repetition?

-
For every $x \in X$ I have $m$ elements from $Y$ to choose from and thus $n\cdot n \cdot n ...$ for $n^m$? – Daniel Oct 8 '12 at 18:22
That's correct! A typo: $n$ elements from $Y$ to choose. – P.. Oct 8 '12 at 18:37

Hint 1: How many ways do you have to define $f(a)$ for $a\in X$ ?

Hint 2: two functions $f,g$ are different if there is $a\in X$ s.t the $f(a)\neq g(a)$

-