Proof: Permutations and Surjective Functions
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! 
Re: Proof: Permutations and Surjective Functions
Could it have something to do with creating a function from a partitioned version of X to Y?

Re: Proof: Permutations and Surjective Functions
No takers?

Re: Proof: Permutations and Surjective Functions
Quote:

All times are GMT 5. The time now is 11:04 AM. 
Powered by vBulletin Copyright ©2000  2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums