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

Printable View

- Mar 17th 2009, 03:12 PMsulimancalculate 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 PMPlato
The proof of this is simple classical application of the

.**inclusion/exclusion principle**

Count the number of functions that leaveout of the image.**at least one**

How functions leaveout: $\displaystyle {m \choose 1}(m-1)^n$.**one member**

How functions leaveout: $\displaystyle {m \choose 2}(m-2)^n$.**two members**

But now you have counted some twice. So substract.

Etc

Then subtract that number from the total.