# Size of the set of functions from $X$ to $Y$

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
add comment

## 4 Answers

Hint: You answer seems to indicate that all functions are one-to-one. Note that this need not be the case.

-
Yes you are right on this, I take function as one-to-one to see if I can get any result, but it seems that the counting is more complicated than that. –  Daniel Oct 8 '12 at 17:52
@jsk: Actually, it is much easier. For permutations (one-to-one functions) you remove an option at each stage. For arbitrary function, you do not remove options. You will have $n$ choices for $f ( \text{first element of }X)$, and then $n$ choices for $f ( \text{second element of }X)$, etc. –  Arthur Fischer Oct 8 '12 at 18:00
Is it $n \cdot m$ distinct functions? –  Daniel Oct 8 '12 at 18:14
Scratch my answer, that was totally wrong. –  Daniel Oct 8 '12 at 18:20
@jsk: yes, you were... a bit off. No worries, though, it's all a part of learning. –  Arthur Fischer Oct 8 '12 at 18:24
add comment

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?

-
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
add comment

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

-
add comment

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 $$|Y^X| = |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
add comment