3
$\begingroup$

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

  • 0
    You may find $t$his $r$elevant: http://en.wikipedia.org/wiki/Twelvefold_way2012-10-08

4 Answers 4

5

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

4

The answer is

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

  • 0
    That's correct! A typo: $n$ elements from $Y$ to choose.2012-10-08
3

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

3

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

  • 0
    Interesting! Thanks for the info!2012-10-08