Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 10 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer
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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.