Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 3 down vote favorite

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 ?

share|improve this question
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
1  
@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
2  
See also math.stackexchange.com/questions/84162/… – 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

1 Answer

up vote 2 down vote accepted

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

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

Your Answer

 
discard

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.