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.

Nyt sinä Yksikään laskin ei ratkaise tätä, mutta sen osat ovat yhtä totta. Kokeile alla olevaa tai kirjoita omasi.

⌨ Tyyppi ✎ Piirrä se

Matematiikkaongelmasi

π Ratkaise

Harjoittelu (17)

Kokeile ensin kutakin paperilla. Tarkista vastaus, varmistuneet voidaan avata ratkaisijassa jokaista vaihetta varten.

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

   Käy se läpi Vinkki

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

   Käy se läpi Vinkki

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

   Käy se läpi Vinkki

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

   Käy se läpi Vinkki

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

   Käy se läpi Vinkki

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

   Käy se läpi Vinkki

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

   Käy se läpi Vinkki

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

   Käy se läpi Vinkki

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

   Käy se läpi Vinkki

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

    Käy se läpi Vinkki

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

    Käy se läpi Vinkki

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

    Käy se läpi Vinkki

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

    Käy se läpi Vinkki

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

    Käy se läpi Vinkki

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

    Käy se läpi Vinkki

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

    Käy se läpi Vinkki

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.

    Käy se läpi Vinkki

Pidä oma työsi

Vapaa tili lisää muistiinpanoja jokaiseen oppituntiin, muistiinpanoja siitä, mitä olet saanut päätökseen, ratkaistuja ongelmiasi yhdessä paikassa ja ohjaajaa, jolta voit kysyä tästä sivusta. Matematiikka on kaikille avoin, kirjautunut tai ei.

Rekisteröidy Kirjautuminen

Symbolit, joita käytetään täällä

Napauta symbolia koko määrittelyn, kuvan ja sen jokaisen kirjaimen osalta.

x \in Aelement of, subset
x belongs to A; every element of A is in B.iimaginary 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_ksummation
Add a_k for k = 1 up to n.\prod_{k=1}^{n} a_kproduct
Multiply a_k for k = 1 up to n.\emptysetempty set, cardinality
The set with no elements; the number of elements of A.

Kysymyksiä

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.

Osaa tästä sivusta on muokattu Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Tässä on tiivistetty ja selitetty uudelleen, virheet ovat meidän.

Lisää 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