Thread: Number of Onto Function between two sets?

1. Number of Onto Function between two sets?

I am a beginner here and have recently started learning Discrete math. I dont know how to solve the following question.

Q. Let A ={0,1,2,3} and B ={0,1,2}. How many functions are there from A to B that are onto?

2. Originally Posted by himanshugpt
I am a beginner here and have recently started learning Discrete math. I dont know how to solve the following question.
Q. Let A ={0,1,2,3} and B ={0,1,2}. How many functions are there from A to B that are onto?
I will answer this question for the finite case only.
Being beginner, you may not understand the reply.
You need to know how to use the generalized inclusion/exclusion rule.

Let $\displaystyle |A|$ denote the number of elements in set $\displaystyle A$.

If $\displaystyle |A|<|B|$ there are no onto functions $\displaystyle A\to B$.

If $\displaystyle |A|=m\ge~n=|B|$ then number of onto functions $\displaystyle A\to B$ is given by:

$\displaystyle \text{Surj}(m,n)=\sum\limits_{j = 0}^n {\left( { - 1} \right)^j \dbinom{ n}{j} \left( {n - j} \right)^m }$.

3. Thanks for the reply Plato.
Is there any link or topic I have to ponder on to understand this.
I am unable to get what the variable j mean in the above formula.

4. Well, I did say that you may not have any idea what is going on.
It is rather advanced material. Here is webpage on inclusion/exclusion.

In essence we are selecting elements of $\displaystyle B$ to be included then excluded.

5. Thanks for the Link. I will try to understand this and will post here if I encounter any other problem.

Thanks again.

,
,
,
,

,

,

,

,

,

,

,

,

onto functions from a to b

Click on a term to search for related topics.