7.3: 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 integers 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<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,…,m\), we say that \(f\) satisfies property \(P_i\) if \(i\) is not in the range of \(f\).

Lemma 7.8.

For each subset \(S \subseteq [m]\), \(N(S)\) depends only on \(|S|\). In fact, if \(|S|=k\), then

\(N(S) = (m-k)^n\).

Proof

Let \(|S|=k\). Then a function \(f\) satisfying property \(P_i\) for each \(i \in S\) is a string of length \(n\) from an alphabet consisting of \(m−k\) letters. This shows that

\(N(S) = (m-k)^n\).

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

Theorem 7.9

The number \(S(n,m)\) of surjections from \([n]\) to \([m]\) is given by:

\(S(n,m) = \displaystyle \sum_{k=0}^m (-1)^k \dbinom{m}{k} (m-k)^n\).

For example,

\(S(5,3) = \dbinom{3}{0}(3-0)^5 - \dbinom{3}{1}(3-1)^5 + \dbinom{3}{2}(3-2)^5 - \dbinom{3}{3}(3-3)^5\)

\(=243 - 96 + 3 - 0\)

\(=150\).

Returning to our lottery ticket distribution problem at the start of the section, we see that there are \(S(15,4)=1016542800\) ways for the grandfather to distribute his 15 lottery tickets so that each of the 4 grandchildren receives at least one ticket.