Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 on?
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 tired summing the Binomial coefficient, but it repeats sets. Any ideas to get me going? Thanks!

share|improve this question
add comment

3 Answers

up vote 5 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|improve this answer
add comment

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|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
add comment

The total number of one-one functions in a set is calculated by a formulla used nPm =n!/(n-m)! Where n is the potensity of set A and m is the potensity of set B

share|improve this answer
add comment

Your Answer

 
discard

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.