Enumerating Surjections

As our first example of the power of inclusion-exclusion, consider the following situation: A grandfather has \(15\) distinct lottery tickets and wants to distribute them to his four grandchildren so that each child gets at least one ticket. In how many ways can he make such a distribution? At first, this looks a lot like the problem of enumerating integer solutions of equations, except here the lottery tickets are not identical! A ticket bearing the numbers \(1\), \(3\), \(10\), \(23\), \(47\), and \(50\) will almost surely not pay out the same amount as one with the numbers \(2\), \(7\), \(10\), \(30\), \(31\), and \(48\), so who gets which ticket really makes a difference. Hopefully, you have already recognized that the fact that we're dealing with lottery tickets and grandchildren isn't so important here. Rather, the important fact is that we want to distribute distinguishable objects to distinct entities, which calls for counting functions from one set (lottery tickets) to another (grandchildren). In our example, we don't simply want the total number of functions, but instead we want the number of surjections, so that we can ensure that every grandchild gets a ticket.

For positive integers \(n\) and \(m\), let \(S(n,m)\) denote the number of surjections from \([n]\) to \([m]\). Note that \(S(n,m)=0\) when \(n\lt m\). In this section, we apply the Inclusion-Exclusion formula to determine a formula for \(S(n,m)\). We start by setting \(X\) to be the set of all functions from \([n]\) to \([m]\). Then for each \(f\in X\) and each \(i=1,2,\dots,m\), we say that \(f\) satisfies property \(P_i\) if \(i\) is not in the image of \(f\).

Now the following result follows immediately from this lemma by applying the , as there are \(C(m,k)\) \(k\)-element subsets of \([m]\).

For example, \[\begin{aligned}S(5,3) \amp = \binom{3}{0}(3-0)^5-\binom{3}{1}(3-1)^5+\binom{3}{2}(3-2)^5-\binom{3}{3}(3-3)^5 \\ \amp = 243 -96+3-0 \\ \amp = 150.\end{aligned}\]

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.