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.

이제 너 계산기는 이것을 해결하지 않지만, 그 조각은 계산 가능합니다. 아래의 하나를 시도하거나 자신의 것을 입력하십시오.

⌨ 종류 ✎ 그려

수학 문제

π 해결

연습 (17)

먼저 종이에 각각을 시도해 보세요. 확인하기 위해 답을 드러내세요. 확인된 답은 각 단계의 솔버에서 열 수 있습니다.

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.

    끝내주는 걸 힌트

자신의 작업을 유지

무료 계정은 모든 수업에 노트를 추가, 당신이 완료 한 기록, 당신이 해결 한 문제를 한 곳에, 그리고 당신이이 페이지에 대해 물어 수업 지도자. 수학 자체는 모두에게 열려 있습니다, 로그인 여부.

가입하기 로그인

여기서 사용된 기호

기호를 탭하면 전체 정의, 이미지 및 각 문자의 의미를 확인할 수 있습니다.

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.

사람들이 묻는 질문

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.

이 페이지의 일부는 다음에서 변경되었습니다. Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). 여기서 압축하고 다시 설명; 오류는 우리의.

에 더 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