1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof: Permutations and Surjective Functions

  1. Mar 14, 2012 #1
    1. The problem statement, all variables and given/known data
    Let X and Y be finite nonempty sets, |X|=m, |Y|=n≤m. Let f(n, m) denote the number of partitions of X into n subsets. Prove that the number of surjective functions X→Y is n!*f(n,m).

    2. Relevant equations
    I know a function is onto if and only if every element of Y is mapped to by an element of X. That is, for all y in Y, there is an x in X such that f(x)=y. Clearly if f is a function and n≤m, a function from X to Y can be onto (but it doesn't have to be, for instance, all of X could map to the same Y).


    3. The attempt at a solution
    I tried by induction, but got lost moving from n=k to n=k+1, so I'm not sure if that works. I think that f(n, m) has something to do with the number of ways to permute the elements of X... but not sure. This is before the lecture on combinations, so I'm not sure if we need to use that method.

    Thanks in advance!
     
  2. jcsd
  3. Mar 14, 2012 #2
    Could it have something to do with creating a function from a partitioned version of X to Y?
     
  4. Mar 15, 2012 #3
    No takers?
     
  5. Mar 15, 2012 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Sure it could. You split X into subsets, each one of which maps into a unique element of Y. Then given a split (of which there are f(n,m)) you figure out how many ways there are to assign each subset to an element of Y. I don't think induction is really necessary here. Just explain it in words.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Proof: Permutations and Surjective Functions
  1. Surjective Proof (Replies: 2)

  2. Surjective function (Replies: 3)

  3. Surjective functions (Replies: 1)

  4. Surjective Proof (Replies: 1)

Loading...