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!

| cite | improve this question | | | | |
  • $\begingroup$ @rogerl Thanks for the link $\endgroup$ – MathMan Oct 30 '19 at 17:29

Browse other questions tagged or ask your own question.