number of surjections formula

It is quite easy to calculate the total number of functions from a setXwithmelements to a setYwithnelements (nm), and also the total number of injective functions (nm−−, denoting the falling factorial). But I am thinking about how to calculate the total number of surjective functionsf:X↠Y.

The way I thought of doing this is as follows: firstly, since allnelements of the codomainYneed to be mapped to, you choose anynelements from themelements of the setXto be mapped one-to-one with thenelements ofY. This results inn!possible pairings. But the number of ways of choosingnelements frommelements ism!(m−n)!n!, so the total number of ways of matchingnelements inXto be one-to-one with thenelements ofYism!(m−n)!n!×n!=m!(m−n)!.

Now we have 'covered' the codomainYwithnelements fromX, the remaining unpairedm−nelements fromXcan be mapped to any of the elements ofY, so there arenm−nways of doing this. Therefore I think that the total number of surjective functions should bem!(m−n)!nm−n.

one can get a formula for the number of surjections using inclusion-exclusion, applied to the setsX1,...,Xm, where for eachithe setXiis defined to be the set of functions that never take the valuei. This gives rise to the following expression:mn−(m1)(m−1)n+(m2)(m−2)n−(m3)(m−3)n+….