World's most popular travel blog for travel bloggers.

[Solved]: Functions between sets?

, , No Comments
Problem Detail: 

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 ?

Asked By : Hunter McMillen

Answered By : Nicholas Mancuso

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6611

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback