# Recitation of May. 2, 2013

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:

• On modular arithmetic: 7.21
• On the Pigeonhole and inclusion/exclusion principle: 10.14, 10.33, 10.34
• On probability: 9.3, 9.10, 9.11
• A bonus exercise on probability: 8000 out of the 10000 emails a user has received are spam. From those spams, half of them contain the word "money", whereas only 20 of the 2000 nonspam messages she has received contain this word. A new message containing the word "money" comes in. What is the probability it is a spam ? (Hint: use Bayes formula)