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.
To get everyone on the same page, let’s recall what a surjection is.
Definition7.21.
A function \(f\colon X\to Y\) is called a surjection provided that for every \(y\in Y\text{,}\) there is at least one \(x\in X\) such that \(f(x) = y\text{.}\) Surjections are also called onto functions.
Another way of defining a surjection is by thinking about what the image of the function is, so let’s define this as well.
Definition7.22.
The image of a function \(f\colon X\to Y\) is the set
\begin{equation*}
\{y\in Y\colon \text{ there is }x\in X\text{ such that }f(x) = y\}\text{.}
\end{equation*}
Sometimes the image is also called the range of the function, but different authors use “range” in different ways, so we will use “image”, which is likely consistent with what you might have seen in a linear algebra class. In this way, a function \(f\colon X\to Y\) is a surjection provided that the image of \(f\) is equal to the set \(Y\text{.}\)
Checkpoint7.23.
Which of the following functions from \([6]\) to \([4]\) are surjections?
\(x\)
1
2
3
4
5
6
\(f(x)\)
3
3
3
2
4
2
\(x\)
1
2
3
4
5
6
\(g(x)\)
1
3
3
2
4
2
\(x\)
1
2
3
4
5
6
\(h(x)\)
1
2
3
1
2
4
\(f\)
\(g\)
\(h\)
None of the above
Checkpoint7.24.
Let \(X\) be the set of all functions from \([n]\) to \([m]\text{.}\) How many elements does the set \(X\) contain?
\(n^m\)
\(n\cdot m\)
\(P(n,m)\)
\(m^n\)
\(P(m,n)\)
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 activity, 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{.}\)
Checkpoint7.25.
Define \(f\colon [8] \to [5]\) as shown below. Which properties does \(f\) satisfy?
\(x\)
1
2
3
4
5
6
7
8
\(f(x)\)
5
2
3
3
2
5
2
3
\(P_1\)
\(P_2\)
\(P_3\)
\(P_4\)
\(P_5\)
None of the above
Let’s first focus on the case of counting surjections from \([8]\) to \([5]\text{.}\)
Checkpoint7.26.
The set \(\mathcal{P}\) contains properties.
Checkpoint7.27.
There are functions that satisfy \(P_1\) and functions that satisfy \(P_3\text{.}\)
Checkpoint7.28.
There are functions that satisfy both \(P_1\) and \(P_3\) (at the same time).
Checkpoint7.29.
There are functions that satisfy both \(P_2\) and \(P_5\) (at the same time).
Checkpoint7.30.
Let \(S\subseteq [5]\) with \(|S| = 3\text{.}\) (That is, \(S\) is a set of three elements.) There are functions that satisfy all the properties with subscripts in \(S\) (at the same time).
Checkpoint7.31.
Using the inclusion-exclusion formula and an online calculator such as Desmos 1
desmos.com
, we can determine that the number of surjections from \([8]\) to \([5]\) is
Let’s now think about counting surjections from \([n]\) to \([m]\) with \(n\gt m\text{.}\) Your answers to the previous activity will be a good guide, as the “eightness” of \(8\) and the “fiveness” of \(5\) weren’t critical.
Checkpoint7.32.
The set \(\mathcal{P}\) contains properties.
Checkpoint7.33.
There are functions that satisfy \(P_1\) and functions that satisfy \(P_3\text{.}\)
Checkpoint7.34.
There are functions that satisfy both \(P_1\) and \(P_3\) (at the same time).
Checkpoint7.35.
Let \(S\subseteq [m]\) with \(|S| = 4\text{.}\) (That is, \(S\) is a set of four elements.) There are functions that satisfy all the properties with subscripts in \(S\) (at the same time).
Checkpoint7.36.
Let \(S\subseteq [m]\) with \(|S| = j\text{.}\) (That is, \(S\) is a set of \(j\) elements.) There are functions that satisfy all the properties with subscripts in \(S\) (at the same time).
Checkpoint7.37.
Let \(S\subseteq [m]\) with \(|S| = j\text{.}\) (That is, \(S\) is a set of \(j\) elements.) There are subsets of \([m]\) of size \(j\text{.}\)
Checkpoint7.38.
Using the inclusion-exclusion formula, we can determine that the formula for the number of surjections from \([n]\) to \([m]\) is given as a summation. Do your best to express that summation in the box below.
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.
