# calculate total of surjective functions

• Mar 17th 2009, 03:12 PM
suliman
calculate total of surjective functions
Prove that the total of surjective functions from group with n elements to group with m elements : (n>=m),
given by this inductive formula
http://up.arabseyes.com/upfiles/L3x83609.jpg
• Mar 17th 2009, 03:29 PM
Plato
The proof of this is simple classical application of the inclusion/exclusion principle.
Count the number of functions that leave at least one out of the image.
How functions leave one member out: ${m \choose 1}(m-1)^n$.
How functions leave two members out: ${m \choose 2}(m-2)^n$.
But now you have counted some twice. So substract.
Etc

Then subtract that number from the total.