Massachusetts Institute of Technology Handout 42 6.042J/18.062J: Mathematics for Computer Science October 30, 1998 Professors Nancy Lynch and Srini Devadas

Problem for Recitation 8 (10/30/98)

Problem 1. In a company there are n engineers and m projects (and, thankfully, there are more engineers than projects.) Each engineer works on exactly one project, and each project must have at least one engineer assigned to it. In how many ways can the boss assign projects to the engineers?

The above problem is equivalent to the problem of counting the number of surjective functions f : A → B between two non-empty sets A and B such that |A| = n (engineers) and |B| = m (projects).

(a) Find the number of functions f : A → B.

(b) Use Inclusion-Exclusion to derive a formula expressing the number of nonsurjective functions f : A → B in terms of binomial coefficients.

(c) Use the previous steps to prove that the number of surjections f : A → B is

∑_{k=0}^{m}(−1)^{k}\binom{m}{k}(m − k)^{n}

where n = |A| and m = |B|.