We got this question in homework (excuse my poor translation):
This question deals with counting functions between two sets:
A. How many functions exist between the set $[1,2,…,n]$ and the set $\{1,2\}$? How many of them are onto?
B. How many functions exist between the set $\{1,2\}$ and $[1,2,…,n]$? How many of them are injective?
I don't really know where to start. I tried summing the Binomial coefficient, but it repeats sets.
Any ideas to get me going? Thanks!
Best Answer
The number of functions from a set $X$ to another set $Y$ is given by $|Y|^{|X|}$ since each element in the set $X$ has $|Y|$ choices.
Hence, in the first case, you have a total of $2^n$ functions. To count the number of onto(surjective) functions, the easier way in this case is to subtract out the number of functions which are not onto. In this case, there are only two functions which are not unto, namely the function which maps every element to $1$ and the other function which maps every element to $2$. Hence, the total number of onto functions is $2^n-2$.
In the second case, the total number of functions is $n^2$. To count the number of one-to-one(injective) functions, all we need is $1$ and $2$ must map to distinct elements. If the function is one-to-one, then the number of choices for $1$ is $n$. Once we know where $1$ has been mapped to the number of choices for $2$, so that the function is one-to-one, is $n-1$. Hence, the total number of injective functions is $n(n-1)$.