Results 1 to 2 of 2

Math Help - calculate total of surjective functions

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    12

    calculate total of surjective functions

    Prove that the total of surjective functions from group with n elements to group with m elements : (n>=m),
    given by this inductive formula
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,614
    Thanks
    1581
    Awards
    1
    The proof of this is simple classical application of the inclusion/exclusion principle.
    Count the number of functions that leave at least one out of the image.
    How functions leave one member out: {m \choose 1}(m-1)^n.
    How functions leave two members out: {m \choose 2}(m-2)^n.
    But now you have counted some twice. So substract.
    Etc

    Then subtract that number from the total.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Partitions for surjective functions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 21st 2011, 10:22 AM
  2. Back calculate total participants from rate ratios
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: September 29th 2010, 12:48 PM
  3. total, injective, surjective, and bijective functions
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 24th 2010, 12:12 AM
  4. Surjective functions
    Posted in the Advanced Math Topics Forum
    Replies: 3
    Last Post: November 4th 2009, 03:51 PM
  5. Replies: 0
    Last Post: January 28th 2009, 09:29 AM

Search Tags


/mathhelpforum @mathhelpforum