An Activity to Enumerate Surjections

An Activity to Enumerate Surjections

To start this activity, let's first ensure we're on the same page of the number of terms in the inclusion-exclusion sum.

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.

To get everyone on the same page, let's recall what a surjection is.

Another way of defining a surjection is by thinking about what the image of the function is, so let's define this as well.

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\).

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 activity, 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\).

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

Practice (17)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. Suppose that \(m=8\). How many terms are there in the sum \[\begin{aligned}\end{aligned}\]?

2. 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

3. Let \(X\) be the set of all functions from \([n]\) to \([m]\). How many elements does the set \(X\) contain?

4. 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

5. The set \(\mathcal{P}\) contains properties.

6. There are functions that satisfy \(P_1\) and functions that satisfy \(P_3\).

7. There are functions that satisfy both \(P_1\) and \(P_3\) (at the same time).

8. There are functions that satisfy both \(P_2\) and \(P_5\) (at the same time).

9. Let \(S\subseteq [5]\) with \(|S| = 3\). (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).

10. Using the inclusion-exclusion formula and an online calculator such as Desmos, we can determine that the number of surjections from \([8]\) to \([5]\) is

11. The set \(\mathcal{P}\) contains properties.

12. There are functions that satisfy \(P_1\) and functions that satisfy \(P_3\).

13. There are functions that satisfy both \(P_1\) and \(P_3\) (at the same time).

14. Let \(S\subseteq [m]\) with \(|S| = 4\). (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).

15. Let \(S\subseteq [m]\) with \(|S| = j\). (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).

16. Let \(S\subseteq [m]\) with \(|S| = j\). (That is, \(S\) is a set of \(j\) elements.) There are subsets of \([m]\) of size \(j\).

17. 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.

Symbols used here

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

i

imaginary unit
i² = −1.

n!

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Subukan ang iyong sarili

⌨ Type ✎ Draw

Ang iyong problema sa matematika

Lumutas

x²√÷×π( )=∫d/dxlim[ ]sinlogeˣ

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Higit pa sa Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs