# Counting functions between two sets

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!

-

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

-

A. If $f$ is a function from $\{1,\cdots,n\}$ and $\{1,2\}$ that basically means that for every element $a$ in $\{1,\cdots,n\}$ we can either "mark" it (map to 1) or not (map it to 2). In total we have $2^n$ cases.

Hope that helps.

-
For (B) you have $n$ choices for $f(1)$ and $n$ choices for $f(2)$. – Daniil Nov 21 '11 at 8:36

The total number of one-one functions to set $A$ from set $B$ is calculated by formula:

$$_nP_m =\frac{n!}{(n-m)!}$$

where $n$ is the cardinality of set $A$ and $m$ is the cardinality of the set $B$.

-
I improved your answer as much as I could by editing it, hope that I don't change any important thing that you would mind. – Mher Dec 5 '14 at 13:57
@Mher: You have improved the answer a great deal, and I appreciate your effort. However even with this clarification, it really needs more to fully answer even the half of the original Question to which it was addressed. – hardmath Dec 5 '14 at 14:25
I have edited the statement again, for the sake of making it valid, specifying the direction of the function's 1-1 mapping. – hardmath Dec 5 '14 at 17:43