Counting functions between two sets

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.