Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
You may find this relevant: – Austin Mohr Oct 8 '12 at 18:14
up vote 4 down vote accepted

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

share|cite|improve this answer

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?

share|cite|improve this answer
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)$

share|cite|improve this answer

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

share|cite|improve this answer
Interesting! Thanks for the info! – Daniel Oct 8 '12 at 22:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.