Number of Onto Function between two sets?

• Oct 2nd 2010, 02:02 PM
himanshugpt
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?
• Oct 2nd 2010, 02:33 PM
Plato
Quote:

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 $|A|$ denote the number of elements in set $A$.

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

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

$\text{Surj}(m,n)=\sum\limits_{j = 0}^n {\left( { - 1} \right)^j \dbinom{ n}{j} \left( {n - j} \right)^m }$.
• Oct 2nd 2010, 02:37 PM
himanshugpt
In essence we are selecting elements of $B$ to be included then excluded.