patternMinor
Functions between sets?
Viewed 0 times
functionssetsbetween
Problem
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 ?
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 ?
Solution
$\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$.
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$.
Context
StackExchange Computer Science Q#6611, answer score: 2
Revisions (0)
No revisions yet.