We discussed Problem 9.40 from the homework. The proof of this using the binomial theorem (which was explicitly forbidden) is obtained simply by expanding ((-1) + 2)n in two different ways.
We talked about the numbers of surjections from [k] to [n]. First of all, if k < n, there is no surjection. If k = n, surjections are also injections, so they are bijections, and hence there are n! many of them.
If k > n, things become nasty. The formula from the inclusion-exclusion principle I gave is correct, and I don't think there is a much simpler formula in the general case. Another less explicit way to do it is to use the Stirling numbers of the second kind S(n,k) which count the number of ways to partition a set of size n into k non-empty disjoint sets.
There is a recursive formula to compute them, and then one can write that the number of surjections from k to n is S(n,k) k! . I will let you think about why this is true !
If you need practice, here are some suggested exercises I haven't had time to go through in class: