Results 1 to 2 of 2

Math Help - [SOLVED] number of onto functions

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    80

    [SOLVED] number of onto functions

    How many onto functions are there from a set with n elements to a set with three elements?

    Could somebody explain how to do this, perhaps substituting 5 in for n?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    You can solve it by recusive definition: suppose n\geq 3
    Let A_n be the number of onto function from a set with n elements to a set with three elements, B_n be the number of onto function from a set with n elements to a set with two elements.
    then what is the recusive relation between A_{n+1}, A_n and B_n?
    A_{n+1}=3A_n+3B_n
    while it is easy to see that A_3=6,B_n=2^n-2.
    Last edited by Shanks; December 13th 2009 at 05:39 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of functions from one set to another?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 8th 2011, 10:46 AM
  2. Replies: 2
    Last Post: August 19th 2010, 10:32 PM
  3. Replies: 11
    Last Post: November 15th 2009, 12:22 PM
  4. Replies: 7
    Last Post: August 12th 2009, 05:41 PM
  5. Replies: 5
    Last Post: October 7th 2008, 01:55 PM

Search Tags


/mathhelpforum @mathhelpforum