Results 1 to 5 of 5

Math Help - Number of Onto Function between two sets?

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    3

    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.

    Please help.

    Q. Let A ={0,1,2,3} and B ={0,1,2}. How many functions are there from A to B that are onto?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    Quote Originally Posted by himanshugpt View Post
    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 } .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2010
    Posts
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1
    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 B to be included then excluded.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2010
    Posts
    3
    Thanks for the Link. I will try to understand this and will post here if I encounter any other problem.

    Thanks again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hex number sets.. what is 0?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 29th 2011, 03:16 AM
  2. Replies: 1
    Last Post: February 13th 2011, 03:43 AM
  3. Replies: 1
    Last Post: August 10th 2010, 08:40 PM
  4. Number of possible pair sets
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 5th 2010, 12:27 AM
  5. Minimum number of common elements in sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 18th 2009, 04:48 PM

Search Tags


/mathhelpforum @mathhelpforum