Lemma 7.8.
For each subset \(S\subseteq [m]\text{,}\) \(N(S)\) depends only on \(|S|\text{.}\) In fact, if \(|S|=k\text{,}\) then
\begin{equation*}
N(S)=(m-k)^n.
\end{equation*}
Section 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 integer solutions of equations, except here the lottery tickets are not identical! A ticket bearing the numbers \(1\text{,}\) \(3\text{,}\) \(10\text{,}\) \(23\text{,}\) \(47\text{,}\) and \(50\) will almost surely not pay out the same amount as one with the numbers \(2\text{,}\) \(7\text{,}\) \(10\text{,}\) \(30\text{,}\) \(31\text{,}\) and \(48\text{,}\) 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\text{,}\) let \(S(n,m)\) denote the number of surjections from \([n]\) to \([m]\text{.}\) Note that \(S(n,m)=0\) when \(n\lt m\text{.}\) In this section, we apply the Inclusion-Exclusion formula to determine a formula for \(S(n,m)\text{.}\) We start by setting \(X\) to be the set of all functions from \([n]\) to \([m]\text{.}\) Then for each \(f\in X\) and each \(i=1,2,\dots,m\text{,}\) we say that \(f\) satisfies property \(P_i\) if \(i\) is not in the image of \(f\text{.}\)
Proof.
Let \(|S|=k\text{.}\) 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
\begin{equation*}
N(S)=(m-k)^n.
\end{equation*}
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]\text{.}\)
Theorem 7.9.
The number \(S(n,m)\) of surjections from \([n]\) to \([m]\) is given by:
\begin{equation*}
S(n,m) = \sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n.
\end{equation*}
For example,
\begin{align*}
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{align*}
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.
You have attempted of activities on this page.
