Results 1 to 2 of 2

Thread: [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 $\displaystyle n\geq 3$
    Let $\displaystyle A_n$ be the number of onto function from a set with n elements to a set with three elements, $\displaystyle 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 $\displaystyle A_{n+1}$,$\displaystyle A_n$ and $\displaystyle B_n$?
    $\displaystyle A_{n+1}=3A_n+3B_n$
    while it is easy to see that $\displaystyle A_3=6,B_n=2^n-2$.
    Last edited by Shanks; Dec 13th 2009 at 04: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, 09:46 AM
  2. Replies: 2
    Last Post: Aug 19th 2010, 09:32 PM
  3. Replies: 11
    Last Post: Nov 15th 2009, 11:22 AM
  4. Replies: 7
    Last Post: Aug 12th 2009, 04:41 PM
  5. Replies: 5
    Last Post: Oct 7th 2008, 12:55 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum