# Functions between sets?

I recently took a practice exam for the Computer Science GRE and this was one of the questions:

Assume that set $A$ has 5 elements and set $B$ has 4 elements, how many functions exist from set $A$ to set $B$?

I had no idea what this means, I don't recall ever studying functions between sets, could someone shed some light on this question for me ?

-
Hint: Think of how many ways you can select something (allowing repetition) from $B$ where order matters $|A|$ times. – Nicholas Mancuso Nov 11 '12 at 1:39
@NicholasMancuso Are you just talking about a permutation that allows repetitions? That would kind of be irritating if that were the answer because it is just $|B| = 4$; $|A| = 5$; or $4^5$ – Hunter McMillen Nov 11 '12 at 1:48
– A.Schulz Nov 11 '12 at 7:47
It also probably helps to have a definition of a function as a mapping between sets – jk. Nov 12 '12 at 12:47

$\newcommand{\stirling}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}$Your comment is correct in that there are $4^5=1024$ functions from $A$ to $B$.

Letting $|A| =n, |B| = m$ this can be seen by the identity:

$$\sum_{k=0}^n \stirling{n}{k} m(m - 1) \dotsb (m - k + 1) = m^n$$

This describes all the ordered partitions of $A$ over $B$ where each partition is an assignment to the same item in $B$.

A less heady explanation (and perhaps easier to visualize) is the following:

We have a vector of length $n$. Each position in this vector can choose $m$ possible values. That is, the $i$th value in the vector represents what $f(a_i)$ maps to. How many $n$-length vectors over $m$ values can we have? Exactly $m^n$.

-
Thank you for your answer, if permutation was actually in the question I would have gotten it :| – Hunter McMillen Nov 11 '12 at 2:22