I'm faced with the following questions:
1) How many functions are there from a set of size 3 to a set of size 5? How many of them are 1-to-1?
2) How many functions are there from a set of size 10 to a set of size 2? How many of them are onto?
Attempt:
1) To determine the the number of functions, we can set $A = \{a,b,c\} = a$ and $B = \{d, e, f, g, h\} = b$. So the number of functions is $b^a$ or $5^3$. However, this is a large figure for me to do each one by paper and pencil to determine how many are 1:1. Is there any simple way?
2) Same as part 1 but I don't want to write out $2^{10}$ functions to see how many are onto.
Best Answer
I am making a function $f$ from a set of $3$ elements, say the set $A=\{a,b,c\}$, to a set $B$ of $5$ elements.
I can choose the value of $f(a)$ in $5$ ways. For every way of deciding what $f(a)$ is, there are $5$ ways to decide what $f(b)$ is, for a total of $5^2$ ways of deciding the values of $f(a)$ and $f(b)$. And for every way of doing that, there are $5$ choices for the value of $f(c)$, for a total of $5^3$.
If we want $f$ to be one to one, then for every choice about the value of $f(a)$, we only have $4$ choices for $f(b)$, since we cannot have $f(a)=f(b)$. And once we have chosen $f(a)$ and $f(b)$, there are only $3$ allowed values for $f(c)$. Thus there are $(5)(4)(3)$ one to one functions from $A$ to $B$.
For the second problem, let our $2$-element set $B$ be, say, $\{0,1\}$. There are, by the same argument as before, $2^{10}$ functions from a set $A$ of $10$ elements to the set $B$.
How many of these $2^{10}$ functions are bad (not onto)? Exactly $2$ of them, the function that send everybody to $0$ and the one that sends everybody to $1$.