maths.free › Combinatorics & Graph Theory › Inclusion-Exclusion › 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.
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.
Şimdi sen Hiçbir hesap makinesi bu soruyu çözemez, ama parçaları hesaplanabilir. Aşağıdakilerden birini deneyin veya kendinizinkini yazın.
Pratik (17)
Her birini önce kağıt üzerinde deneyin. Çözümü kontrol etmek için gösterin; doğrulanmış olanlar her adım için çözümleyicide açılabilir.
-
Suppose that \(m=8\). How many terms are there in the sum \[\begin{aligned}\end{aligned}\]?
-
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 -
Let \(X\) be the set of all functions from \([n]\) to \([m]\). How many elements does the set \(X\) contain?
-
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 -
The set \(\mathcal{P}\) contains properties.
-
There are functions that satisfy \(P_1\) and functions that satisfy \(P_3\).
-
There are functions that satisfy both \(P_1\) and \(P_3\) (at the same time).
-
There are functions that satisfy both \(P_2\) and \(P_5\) (at the same time).
-
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).
-
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
-
The set \(\mathcal{P}\) contains properties.
-
There are functions that satisfy \(P_1\) and functions that satisfy \(P_3\).
-
There are functions that satisfy both \(P_1\) and \(P_3\) (at the same time).
-
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).
-
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).
-
Let \(S\subseteq [m]\) with \(|S| = j\). (That is, \(S\) is a set of \(j\) elements.) There are subsets of \([m]\) of size \(j\).
-
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.
Burada kullanılan sembolleri
Tüm tanım, resim ve her harfin anlamı için herhangi bir sembolü tıklayın.
Sık sorulan sorular
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.
Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Burada tekrar özetlenmiş ve açıklanmıştır. Hatalar bizim.
More in 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