(adsbygoogle = window.adsbygoogle || []).push({}); 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!

**Physics Forums - The Fusion of Science and Community**

# Proof: Permutations and Surjective Functions

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: Proof: Permutations and Surjective Functions

Loading...

**Physics Forums - The Fusion of Science and Community**