Results 1 to 4 of 4

Math Help - calculating number of onto functions

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    80

    calculating number of onto functions

    Please confirm I'm doing this correctly:

    How many onto functions are there from a set with eight elements to a set with 3 elements?

    Steps

    1. There are 3^8=6561 functions total.

    2. There are 3 functions with 1 element in range.

    3. There are 2^8-2 functions with 2 elements in the range for each pair of elements in the codomain.

    4. There are "3 choose 2"=3 ways to choose 2 elements from a set of 3.

    5. Considering steps 1. through 4., the number of onto functions is:

    3^8-(3*(2^8-2)+3)=5796 onto functions

    I'm almost positive this is correct. Could somebody please confirm?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1
    The number of surjections (onto functions) from a set of N elements to a set of M is given by:
    Surj(N,M) = \sum\limits_{k = 0}^M {\left( { - 1} \right)^k \binom{M}{k}\left( {M - k} \right)^N } of course N\ge M.

    So 5796 is correct.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by Plato View Post
    The number of surjections (onto functions) from a set of N elements to a set of M is given by:
    Surj(N,M) = \sum\limits_{k = 0}^M {\left( { - 1} \right)^k \binom{M}{k}\left( {M - k} \right)^N } of course N\ge M.

    So 5796 is correct.
    Can you please prove it?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,801
    Thanks
    1691
    Awards
    1
    Quote Originally Posted by Also sprach Zarathustra View Post
    Can you please prove it?
    The proof is simply repeated use of the inclusion/exclusion principle.
    Count the number of functions which fail to have certain terms in the range: taken one at a time; taken two at a time; taken three at a time; etc.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Calculating the number of moles
    Posted in the Math Topics Forum
    Replies: 4
    Last Post: June 8th 2011, 01:14 AM
  2. Replies: 2
    Last Post: December 3rd 2010, 02:45 AM
  3. Calculating the number of possible outcomes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: October 12th 2010, 10:15 PM
  4. [SOLVED] Calculating number of possible combinations
    Posted in the Statistics Forum
    Replies: 4
    Last Post: October 5th 2010, 04:32 AM
  5. Calculating the Number of Combinations?
    Posted in the Statistics Forum
    Replies: 1
    Last Post: March 27th 2006, 03:42 AM

Search Tags


/mathhelpforum @mathhelpforum