Surjective Functions and PIE

Welcome back! In our last session, we used the Principle of Inclusion-Exclusion (PIE) to count derangements. The core idea was to calculate the total number of permutations and then systematically subtract the "bad" cases—those where at least one element remained in its original position.

Today, we will see that this powerful strategy is not limited to permutations. We will apply the exact same logic to another fundamental problem in enumerative combinatorics: counting the number of surjective functions between two finite sets. A solid grasp of this technique is essential for tackling many Olympiad-style counting problems that involve mappings or distributions.

Our goal is to derive and apply a general formula for the number of surjective functions using PIE. By the end of this lesson, you will be able to translate word problems into questions about functions and choose the most effective method to solve them.

What is a Surjective Function?

First, let's clarify our object of study. A function $f : A \to B$ is surjective (or onto) if every element in the codomain $B$ is "hit" by at least one element from the domain $A$ . In other words, the range of the function is equal to its codomain.

The video below gives a brief and clear introduction to the concept of surjectivity.

Counting Surjections ("onto" functions)

This video, "Counting Surjections," by Dr Barker, starts with a clear definition of what it means for a function to be "onto."

Watch the initial segment from the beginning to understand the definition and see visual examples for both infinite and finite sets.

The image below shows the key difference. On the left, every element in set B has an arrow pointing to it, so the function is surjective. On the right, element 'g' is missed, so the function is not surjective.

On the left, a surjective function where every element in codomain B is an image of at least one element from domain A. On theright, a non-surjective function where element 'g' in codomain B has no pre-image in A.

Framing the Problem for PIE

Our task is to find the number of surjective functions from a set $A$ with $m$ elements to a set $B$ with $n$ elements. Let's set this up for a PIE argument, just as we did for derangements.

The Universe (U): The set of all possible functions from $A$ to $B$ . For each of the $m$ elements in $A$ , we have $n$ choices for its image in $B$ . By the product rule, the total number of functions is $∣ U ∣ = n^{m}$ .
The "Bad" Property: A function is "bad" if it is not surjective. This means at least one element in the codomain $B$ is missed (i.e., not in the range).
Defining Properties for PIE: Let $B = {y_{1}, y_{2}, \dots, y_{n}}$ . We define property $P_{i}$ to mean that the element $y_{i} \in B$ is not in the range of the function. Let $S_{i}$ be the set of all functions that have property $P_{i}$ .

The set of all non-surjective functions is the union $S_{1} \cup S_{2} \cup \dots \cup S_{n}$ . The number of surjective functions is therefore:
$Number of Surjections = ∣ U ∣ - ∣ S_{1} \cup S_{2} \cup \dots \cup S_{n} ∣ = n^{m} - ∣ S_{1} \cup \dots \cup S_{n} ∣$
Our goal is now to calculate the size of this union using PIE.

Applying PIE to Count Surjections

The logic is a step-by-step process of adding and subtracting the sizes of intersections of the sets $S_{i}$ . The following video walks through a concrete example before deriving the general formula.

Counting Surjections ("onto" functions)

The same video continues by applying the PIE logic to a specific example and then generalizes it.

First, watch the detailed calculation for functions from a set of size 7 to a set of size 4. This runs from the example. Pay close attention to how the "bad" cases are counted and then corrected for overcounting. Next, watch the derivation of the general formula. This formalizes the pattern you saw in the example.

Let's recap the logic from the video and express it as a formula.

Step 1: Subtract functions that miss one element.
The size of $S_{i}$ (functions missing $y_{i}$ ) means all $m$ elements of $A$ must map to the remaining $n - 1$ elements of $B$ . There are $(n - 1)^{m}$ such functions. Since there are $(1 n)$ ways to choose the one element to miss, this term is $(1 n) (n - 1)^{m}$ .
Step 2: Add back functions that miss two elements.
The size of $S_{i} \cap S_{j}$ (functions missing both $y_{i}$ and $y_{j}$ ) means all $m$ elements of $A$ map to the $n - 2$ elements left in $B$ . There are $(n - 2)^{m}$ such functions. There are $(2 n)$ pairs to choose. This term is $(2 n) (n - 2)^{m}$ .
General Step k: The term for functions missing $k$ specific elements is $(k n) (n - k)^{m}$ .

The PIE formula for the number of non-surjective functions is:
$∣ S_{1} \cup \dots \cup S_{n} ∣ = (1 n) (n - 1)^{m} - (2 n) (n - 2)^{m} + \dots + (- 1)^{n - 1} (n n) (n - n)^{m}$
$∣ S_{1} \cup \dots \cup S_{n} ∣ = \sum_{k = 1}^{n} (- 1)^{k - 1} (k n) (n - k)^{m}$

Therefore, the number of surjective functions from a set of size $m$ to a set of size $n$ is:
$n^{m} - \sum_{k = 1}^{n} (- 1)^{k - 1} (k n) (n - k)^{m} = \sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)^{m}$

For a more formal proof, you can refer to the following resource.

[PDF] Week 6-8: The Inclusion-Exclusion Principle

This PDF provides a concise and formal derivation of the formula for counting surjective functions.

Read the section titled "Surjective Functions," which begins with the definition and then presents Theorem 4.1 and its proof. This formalizes the logic we've just discussed.

An Alternative Perspective: Choosing Your Method

Since you are aiming for Olympiad-level mastery, it's crucial to recognize when a problem can be solved in multiple ways and to choose the most efficient one. Counting surjective functions is a great example of this.

Consider the problem of assigning $m$ distinct jobs to $n$ distinct employees such that every employee gets at least one job.

This is a function from jobs (domain) to employees (codomain).
"Every employee gets at least one job" means the function must be surjective.

This problem can be solved with our new PIE formula, but sometimes a more direct combinatorial argument is simpler. The next video explores this trade-off.

Lecture 24D - Onto Functions - Inclusion Exclusion Principle | Combinatorics | Discrete Mathematics

This lecture from GO Classes for GATE CS discusses a problem that can be solved in two ways, highlighting the strategic choice involved.

First, watch the segment that solves the problem of assigning 5 jobs to 4 employees using two different methods: our PIE approach and a direct counting method. Then, watch the discussion on which method is better for different scenarios. This is key for developing problem-solving intuition.

As the video explains, when the difference between the domain size ( $m$ ) and codomain size ( $n$ ) is small, direct counting by cases can be faster. For example, to map 4 elements to 3, one element in the codomain must have two pre-images. You can count this directly. However, as the difference grows (e.g., 10 elements to 5), the number of cases for direct counting explodes, and PIE becomes far more efficient and reliable.

Practice Problems

Let's put this into practice.

Direct Formula Application: Consider sets $A$ and $B$ with $∣ A ∣ = 10$ and $∣ B ∣ = 5$ . How many functions $f : A \to B$ are surjective? (This is Exercise 12 from the "Advanced Counting Using PIE" text).
Choosing Your Method: How many surjective functions are there from a set with 4 elements to a set with 3 elements? Solve this using both the PIE formula and a direct combinatorial argument (as discussed in the second video). Which method felt more straightforward for this specific case?
Word Problem: How many ways are there to distribute 8 different toys to 5 different children if each child must receive at least one toy?
A Special Case: How many surjective functions are there from a set of 5 elements to a set of 5 elements? What is the special name for this type of function? (Hint: think about permutations).

Conclusion

Today, we've extended our mastery of the Principle of Inclusion-Exclusion to a new domain: counting surjective functions. You saw how the same "total minus bad cases" strategy from our lesson on derangements applies here, leading to another powerful combinatorial formula.

Key Takeaways:

A function $f : A \to B$ is surjective if every element in $B$ is in the function's range.
The number of surjective functions from a set of size $m$ to one of size $n$ is given by the PIE formula: $\sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)^{m}$ .
Counting surjective functions is equivalent to counting the ways to distribute $m$ distinct items into $n$ distinct boxes such that no box is empty.
Depending on the specific values of $m$ and $n$ , a direct combinatorial argument might be more efficient than applying the general PIE formula.

In our next lesson, we will look at a closely related concept: Stirling numbers of the second kind. These numbers count the ways to partition a set into a given number of non-empty subsets and provide yet another elegant way to solve problems involving distributions.

Recommended resources