Results 1 to 4 of 4

Math Help - Counting onto functions

  1. #1
    Junior Member
    Joined
    Aug 2010
    Posts
    32

    Counting onto functions

    How many onto functions are there from A to B, if |A| = 10 and |B| = 4?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member Tinyboss's Avatar
    Joined
    Jul 2008
    Posts
    433
    Let f:A\to B be onto. Then some element of A has to go to the first element of B, and there are 10 possibilities for that. Some other element has to go to the second element of B, so 9 possibilities there, and so on. So there are 10*9*8*7 ways to choose four elements of A and send them onto the four elements of B. Once that's done, f is surjective, and we may choose its value on the other 6 elements of A arbitrarily, so the total number is 10*9*8*7*4^6.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2010
    Posts
    32
    I'm getting something different. The book says the formula for the number of onto functions from a set with m elements to a set with n elements, with m ≥ n, is

    n^m - C(n, 1)(n - 1)^m + C(n, 2)(n - 2)^m - ... + (-1)^(n - 1)C(n, n - 1)*1^m

    Letting m = 10 and n = 4, we get

    4^10 - C(4, 1)*3^10 + C(4, 2)*2^10 - C(4, 3) = 4^10 - (4!/3!)*3^10 + [4!/(2!*2!)]*2^10 - 4!/3! = 4^10 - 4*3^10 + 6*2^10 - 4 = 818,520

    onto functions from A to B
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,792
    Thanks
    1687
    Awards
    1
    Quote Originally Posted by quiney View Post
    How many onto functions are there from A to B, if |A| = 10 and |B| = 4?
    Unfortunately the method suggested in reply #2 results is a gross over-count. This is a standard inclusion/exclusion problem. The number of surjections (onto functions) from a set of N to a set of K is  \displaystyle\sum\limits_{j = 0}^K {( - 1)^j \binom{K}{j}\left( {K - j} \right)^N } . Note we must have N\ge K.

    You should the answer here is 818520.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Counting functions on the set {1, 2, 3}
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 27th 2011, 11:32 AM
  2. Counting Zeroes of Complex Functions
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: November 14th 2010, 01:12 AM
  3. Counting functions problem 4
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 3rd 2010, 01:58 PM
  4. Counting
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: November 6th 2009, 01:26 PM
  5. Counting!
    Posted in the Statistics Forum
    Replies: 2
    Last Post: June 18th 2008, 07:11 AM

Search Tags


/mathhelpforum @mathhelpforum