# Derive the formula for the number of onto functions from a set $A$ containing $n$ elements to a set $B$ containing $k$ elements [duplicate]

Derive the formula for the number of onto functions from a set $$A$$ containing $$n$$ elements to a set $$B$$ containing $$k$$ elements.

As per the answer here : You can write an expression using inclusion-exclusion. There are $$n^m$$ total functions from $$A$$ to $$B$$. Subtract off the ones that do not cover one element. There are $$(n-1)^m$$ that skip one particular element, so you would subtract $$n(n-1)^m$$ to remove the ones that skip some element. You have removed all the ones that skip two elements twice, so we need to add them back in. There are $${n \choose 2}(n-2)^m$$ that skip two elements.

Now we have removed the ones that skip three elements three times and added them back three times, so we need to subtract $${n \choose 3}(n-3)m$$. The final expression is $$n^m+\sum_{i=1}^{n-1}(-1)^i{n \choose i}(n-i)^m$$

I do not understand the argument about skipping three elements three times. Could someone please give an explanation. Thanks a lot!

• @rogerl Thanks for the link – MathMan Oct 30 '19 at 17:29