Bijective Proofs for Set Equivalence

Hello! It's great to see you again. Last time, we explored the "Stars and Bars" method, a clever technique for counting distributions and integer solutions. The magic of that method was in how we transformed one problem (distributing items) into another, simpler one (arranging symbols). We relied on the fact that for every valid distribution, there was exactly one unique arrangement of stars and bars, and vice-versa.

Today, we're going to formalize this powerful idea. The concept of a one-to-one correspondence is called a bijection, and using it to prove that two sets are the same size is a fundamental technique in advanced combinatorics called a bijective proof or proof by bijection. Your goal of solving Olympiad-level problems requires a deep understanding of this method, as it provides elegant arguments that are often more insightful than algebraic manipulation. This lesson will equip you with the tools to construct and use these proofs.

Solutions to Previous Practice Problems

Before we dive in, let's quickly go over the solutions to the problems from our lesson on Stars and Bars.

Integer Solutions I: We need to find the number of non-negative integer solutions to $x_{1} + x_{2} + x_{3} + x_{4} = 15$ . Here, $n = 15$ (stars) and $k = 4$ (variables/bins). The formula is $(k - 1 n + k - 1)$ .
$(4 - 1 15 + 4 - 1) = (3 18) = \frac{18 \times 17 \times 16}{3 \times 2 \times 1} = 3 \times 17 \times 16 = 816$
Candy Distribution:
a. 20 identical candies, 5 children. This is $n = 20, k = 5$ . The number of ways is:
$(5 - 1 20 + 5 - 1) = (4 24) = \frac{24 \times 23 \times 22 \times 21}{4 \times 3 \times 2 \times 1} = 10, 626$
b. Each child receives at least two pieces. We first give each of the 5 children 2 pieces, using up $5 \times 2 = 10$ pieces. We have $20 - 10 = 10$ pieces left to distribute without restriction. Now, $n = 10, k = 5$ .
$(5 - 1 10 + 5 - 1) = (4 14) = \frac{14 \times 13 \times 12 \times 11}{4 \times 3 \times 2 \times 1} = 1, 001$
Investment Portfolio: This is equivalent to distributing 100 identical "thousand-dollar units" into 4 distinct funds. $n = 100, k = 4$ .
$(4 - 1 100 + 4 - 1) = (3 103) = \frac{103 \times 102 \times 101}{3 \times 2 \times 1} = 103 \times 17 \times 101 = 176, 851$
Rolling Dice: We need to find the number of integer solutions to $x_{1} + x_{2} + x_{3} = 12$ where $1 \leq x_{i} \leq 6$ . This problem involves an upper bound, which we haven't covered yet (it requires the Principle of Inclusion-Exclusion, a future topic). This was a challenge problem to show the limits of our current tool. For those curious, the answer is 25. The solutions are permutations of (1,5,6), (2,4,6), (2,5,5), (3,3,6), (3,4,5), and (4,4,4).

What is a Bijection?

A bijective proof is a strategy for showing that two sets, $A$ and $B$ , have the same size by finding a perfect pairing between their elements. This perfect pairing is a function called a bijection.

To be precise, a function $f : A \to B$ is a:

Injection (one-to-one): If every element in the domain $A$ maps to a unique element in the codomain $B$ . Formally, if $a_{1} \neq = a_{2}$ , then $f (a_{1}) \neq = f (a_{2})$ .
Surjection (onto): If every element in the codomain $B$ is mapped to by at least one element from the domain $A$ .
Bijection: If it is both an injection and a surjection.

The image below gives a great visual summary of these concepts.

This diagram illustrates the three main types of functions. An injective function ensures no two elements from set A map to the same element in set B. A surjective function ensures every element in B is "hit" by at least one element from A. A bijective function does both, creating a perfect one-to-one correspondence.

The fundamental idea is simple: if you can pair up every element of $A$ with exactly one element of $B$ , with no elements left over on either side, then the two sets must have the same number of elements.

To learn the formal details, let's turn to a clear guide on the topic.

Bijections | An Invitation to Enumeration

This resource provides rigorous definitions and outlines the two primary methods for proving that a function is a bijection.

Please read the first part of this chapter. Start from the beginning and read down to the end of the section just before the example on permutation matrices. Pay close attention to the formal definitions, the lemma stating that a function is a bijection if and only if it has an inverse, and the two methods for proving a bijection.

To summarize the reading, we can prove a function $f : A \to B$ is a bijection by either:

Showing it is both injective and surjective.
Defining an inverse function $g : B \to A$ and showing that $g (f (a)) = a$ for all $a \in A$ and $f (g (b)) = b$ for all $b \in B$ .

For many combinatorial proofs, the second method is more direct and intuitive.

The Bijective Proof in Action

Let's start with a classic, visual example that is foundational in combinatorics.

Example 1: Lattice Paths

How many paths are there from the origin $(0, 0)$ to the point $(m, n)$ if you are only allowed to take unit steps up (U) or to the right (R)?

This is a counting problem. We want to find the size of the set of all such paths. Let's call this set $A$ . Directly counting these paths by drawing them would be impossible for large $m$ and $n$ . Instead, we can create a bijection to a set we already know how to count.

Consider the set $B$ of all strings of length $m + n$ that contain exactly $m$ 'R's and $n$ 'U's. We know how to count this from our first lesson: it's the number of ways to choose $m$ positions for the 'R's out of $m + n$ total positions, which is $(m m + n)$ .

Now, let's define the bijection.

[PDF] Bijections - Yufei Zhao

This PDF from a Math Olympiad course by Yufei Zhao provides a concise and clear explanation of the lattice path bijection.

Read the first page of the document, from the start down to the end of the section on Problem 1. Focus on how a path is encoded and how this creates a bijection.

As the reading explains, we can define a function $f : A \to B$ where $f$ takes a path and outputs the sequence of moves (e.g., RRU...). This function is a bijection:

It's well-defined: Every path from $(0, 0)$ to $(m, n)$ must consist of exactly $m$ right moves and $n$ up moves, so its encoding will be a string in set $B$ .
It has an inverse: Given any string in $B$ , we can uniquely construct the path it represents by starting at $(0, 0)$ and following the sequence of moves.

Since we have a bijection between $A$ and $B$ , we know $∣ A ∣ = ∣ B ∣$ . Therefore, the number of lattice paths is $(m m + n)$ .

Example 2: A Familiar Identity

Let's prove the identity $(k n) = (n - k n)$ using a bijective argument. While you can prove this by expanding the factorials, the bijective proof reveals why it's true from a combinatorial perspective.

We need to find two sets, one of size $(k n)$ and one of size $(n - k n)$ , and show they are in bijection.

Let $U = {1, 2, ..., n}$ be a set of $n$ elements.
Let $A$ be the set of all $k$ -element subsets of $U$ . By definition, $∣ A ∣ = (k n)$ .
Let $B$ be the set of all $(n - k)$ -element subsets of $U$ . By definition, $∣ B ∣ = (n - k n)$ .

How can we create a perfect pairing between these two sets?

Bijections | An Invitation to Enumeration

This section of the "Bijections" chapter provides a perfect, concise proof for this identity.

Please read the first example in the "Combinatorial Proofs" section, which starts with the identity we are discussing.

The bijection is the complement function. For any $k$ -element subset $S \in A$ , its complement $U ∖ S$ is a unique $(n - k)$ -element subset in $B$ . The inverse of this function is itself: taking the complement twice returns the original set. Since a bijection exists, $∣ A ∣ = ∣ B ∣$ , proving the identity.

Example 3: A Deeper Result from Partitions

A partition of a positive integer $n$ is a way of writing $n$ as a sum of positive integers, where the order doesn't matter. For example, the partitions of 4 are: 4, 3+1, 2+2, 2+1+1, 1+1+1+1.

Let's prove a beautiful result using a bijection:

The number of partitions of $n$ into exactly $k$ parts is equal to the number of partitions of $n$ whose largest part is exactly $k$ .

For $n = 6, k = 3$ , the partitions into 3 parts are:

4 + 1 + 1
3 + 2 + 1
2 + 2 + 2

The partitions with largest part 3 are:

3 + 3
3 + 2 + 1
3 + 1 + 1 + 1

Both sets have size 3. This seems to hold! But how do we prove it for any $n$ and $k$ ? The key is a visual representation called a Ferrers diagram.

[PDF] Bijections - Yufei Zhao

This section explains Ferrers diagrams and uses a clever bijection called conjugation to prove the partition identity.

Read from the heading Problem 2 down to just before Problem 3. Pay close attention to the definition of a Ferrers diagram and the operation of taking its conjugate.

The bijection here is conjugation: reflecting the Ferrers diagram across its main diagonal. This operation swaps the number of rows and columns.

The number of parts in a partition corresponds to the number of rows in its diagram.
The size of the largest part corresponds to the number of columns (the length of the first row).

By taking the conjugate, we create a bijection between partitions with $k$ rows (i.e., $k$ parts) and partitions with $k$ columns (i.e., largest part is $k$ ). This proves the two sets have the same size, without any complex counting!

Practice Problems

Now it's your turn to build some bijections. For each problem, the goal is not just to get the answer, but to explicitly define the two sets and the bijection between them.

The Committee and the Chair: Prove the identity $k (k n) = n (k - 1 n - 1)$ with a combinatorial argument.
Hint: Consider the task of forming a committee of $k$ people from a group of $n$ , and then selecting one person from the committee to be the chair. Count the number of ways to do this in two different orders. This is known as "counting in two ways" or a "double counting proof," which is a cousin of the bijective proof.
Even vs. Odd Subsets: Prove that for any non-empty set $S$ with $n$ elements, the number of subsets with an even number of elements is equal to the number of subsets with an odd number of elements (both are $2^{n - 1}$ ).
Hint: Let $E$ be the set of even-sized subsets and $O$ be the set of odd-sized subsets. Pick one special element, say $x \in S$ . Define a function $f : E \to O$ based on whether $x$ is in a given subset. What does the function do if $x$ is present? What if it's absent? Show that this function is a bijection.
Compositions and Subsets: In the last lesson, we found that the number of positive integer solutions to $x_{1} + x_{2} + \dots + x_{k} = n$ is $(k - 1 n - 1)$ . We also know that the number of $(k - 1)$ -element subsets of ${1, 2, \dots, n - 1}$ is $(k - 1 n - 1)$ . Construct an explicit bijection between these two sets:
- Set $A$ : The set of compositions (ordered tuples) $(x_{1}, \dots, x_{k})$ such that $x_{i} \geq 1$ and their sum is $n$ .
- Set $B$ : The set of all $(k - 1)$ -element subsets of ${1, 2, \dots, n - 1}$ .
  Describe a function $f : A \to B$ and its inverse $g : B \to A$ .

Conclusion

Today you've learned one of the most elegant and powerful proof techniques in combinatorics. A bijective proof shifts the focus from "how many?" to "what is the underlying structure?". By finding a one-to-one correspondence, you can prove that two seemingly different collections of objects are, from a combinatorial perspective, the same.

Key Takeaways:

A bijection is a function that is both one-to-one (injective) and onto (surjective).
If a bijection exists between two finite sets $A$ and $B$ , then $∣ A ∣ = ∣ B ∣$ .
A bijective proof establishes that $∣ A ∣ = ∣ B ∣$ by constructing an explicit bijection between $A$ and $B$ .
To prove a function is a bijection, you can either show it's injective and surjective, or you can construct its inverse.
This method can be used to prove combinatorial identities and establish surprising connections between different types of objects (like lattice paths and strings, or partitions and their conjugates).

In our next lesson, we will continue to use bijective arguments, but we'll focus on applying them to prove a wider range of combinatorial identities without relying on algebraic formulas.

Recommended resources

Solutions to Previous Practice Problems

What is a Bijection?

The Bijective Proof in Action

Practice Problems

Conclusion