Bijective Functions

A common proof technique in combinatorics, number theory, and other fields is the use of bijections to show that two expressions are equal. To prove a formula of the form $a = b$, the idea is to pick a set $S$ with $a$ elements and a set $T$ with $b$ elements, and to construct a bijection between $S$ and $T$.

Note that the common double counting proof technique can be viewed as a special case of this technique. The double counting technique follows the same procedure, except that $S = T$, so the bijection is just the identity function. Here are some examples where the two sides of the formula to be proven count sets that aren't necessarily the same set, but that can be shown to have the same size.

Given a formula of the form $a = b$, where $a$ and $b$ are finite positive integer quantities depending on some variables, here is how to prove the formula:

1. Find a set $S$ such that $|S| = a$, and a set $T$ such that $|T| = b$. These sets will not generally be exotic: sometimes they will be clear from the problem, and sometimes they will be well-known as sets that are counted by the quantities in the formula. For example, if $a$ is a binomial coefficient or a sum of binomial coefficients, then $S$ will be a set of subsets of a larger set, or ways to choose certain objects from a set.
2. Think of a way to associate elements of $T$ to elements of $S$, or vice versa. Sometimes one of these is initially easier than the other. Use this to construct a function $f \colon S \to T$ $($or $T \to S).$
3. (optional) Verify that $f$ is a bijection for small values of the variables, by writing it down explicitly.
4. Prove that $f$ is a bijection, either by showing it is one-to-one and onto, or (often easier) by constructing the inverse of $f$.

Prove that binomial coefficients are symmetric: $${n\choose k} = {n\choose n-k}.$$

---

We can prove that binomial coefficients are symmetric: $${n\choose k} = {n\choose n-k}$$ via a bijection. Since $n \choose k$ counts $k$-element subsets of an $n$-element set $S$, and $n\choose n-k$ counts $(n-k)$-element subsets of $S$, the proof consists of finding a one-to-one correspondence between those two types of subsets.

The most natural way to produce an $(n-k)$-element subset from a $k$-element subset is to take the complement. So let $S_i$ be the set of $i$-element subsets of $S$, and define $$\begin{aligned} f_k \colon &S_k \to S_{n-k} \\ f_k(X) = &S - X. \end{aligned}$$ It is easy to prove that this is a bijection: indeed, $f_{n-k}$ is the inverse of $f_k$, because $S - (S - X) = X$. So $S_k$ and $S_{n-k}$ have the same number of elements; that is, ${n\choose k} = {n \choose n-k}$. $_\square$

To illustrate, here is the bijection $f_2$ when $n = 5$ and $k = 2:$ $$\begin{aligned} \{1,2\} &\mapsto \{3,4,5\} \\ \{1,3\} &\mapsto \{2,4,5\} \\ \{1,4\} &\mapsto \{2,3,5\} \\ \{1,5\} &\mapsto \{2,3,4\} \\ \{2,3\} &\mapsto \{1,4,5\} \\ \{2,4\} &\mapsto \{1,3,5\} \\ \{2,5\} &\mapsto \{1,3,4\} \\ \{3,4\} &\mapsto \{1,2,5\} \\ \{3,5\} &\mapsto \{1,2,4\} \\ \{4,5\} &\mapsto \{1,2,3\}. \end{aligned}$$ Since this gives a one-to-one correspondence between $2$-element subsets and $3$-element subsets of a $5$-element set, this shows that ${5\choose 2} = {5\choose 3}$.

A key result about the Euler's phi function is $$\sum_{d|n} \phi(d) = n.$$ Here is a proof using bijections:

Let $S = \{ (a,d) : d\big|n, 1\le a \le d, \text{gcd}(a,d) = 1 \}$. Then the number of elements of $S$ is just $\sum_{d|n} \phi(d)$. Now let $T = \{ 1,2,\ldots,n \}$. To complete the proof, we must construct a bijection between $S$ and $T$.

Define $f \colon S \to T$ by $f\big((a,d)\big) = \frac{an}d$. Define $g \colon T \to S$ as follows: $g(b)$ is the ordered pair $\left(\frac{b}{\gcd (b,n)}, \frac{n}{\gcd (b,n)}\right).$ Then it is routine to check that $f$ and $g$ are inverses of each other, so they are bijections. $_\square$

This is an elegant proof, but it may not be obvious to a student who may not immediately understand where the functions $f$ and $g$ came from. The original idea is to consider the fractions $$\frac1{n}, \frac2{n}, \ldots, \frac{n}{n}$$ and reduce them to lowest terms. They will all be of the form $\frac{a}{d}$ for a unique $(a,d) \in S$. The set $T$ is the set of numerators of the unreduced fractions. The functions $f$ and $g$ in the proof are obtained by converting from the reduced fraction back to the unreduced fraction and vice versa, respectively.

Several classical results on partitions have natural proofs involving bijections. A partition of an integer is an expression of the integer as a sum of positive integers called "parts." The order does not matter; two expressions consisting of the same parts written in a different order are considered the same partition.

Show that the number of partitions of $n$ into odd parts is equal to the number of partitions of $n$ into distinct parts. For example, $5+1 = 3+3 = 3+1+1+1 = 1+1+1+1+1+1$ and $6 = 5+1 = 4+2 = 3+2+1$, so there are four of each kind for $n = 6$.

---

The goal is to give a prescription for turning one kind of partition into the other kind and then to show that the prescription gives a one-to-one correspondence (a bijection). It is probably more natural to start with a partition into distinct parts and "break it down" into one with odd parts. The most obvious thing to do is to take an even part and rewrite it as a sum of odd parts, and for simplicity's sake, it is best to use odd parts that are equal to each other.

That is, take the parts of the partition and write them as $2^a b$, where $b$ is odd. Rewrite each part as $2^a$ parts equal to $b$. For example, for $n = 6$, $$\begin{aligned} 6 &= 3+3 \\ 5+1 &= 5+1 \\ 4+2 &= (1+1+1+1)+(1+1) \\ 3+2+1 &= 3+(1+1)+1. \end{aligned}$$ To show that this correspondence is one-to-one and onto, it is easiest to construct its inverse. Given a partition of $n$ into odd parts, collect the parts of the same size into groups. Suppose there are $d$ parts of size $r$. Then write $d$ in binary as $2^{a_1} + 2^{a_2} + \cdots + 2^{a_k},$ where the $a_i$ are distinct. Change the $d$ parts into $k$ parts: $2^{a_1}r + 2^{a_2}r + \cdots + 2^{a_k}r$. For instance, $$\begin{aligned} 3+3 &= 2\cdot 3 = 6 \\ 5+1 &= 5+1 \\ 1+1+1+1+1+1 &= 6 \cdot 1 = (4+2) \cdot 1 = 4+2 \\ 3+1+1+1 &= 3+ 3\cdot 1 = 3+(2+1)\cdot 1 = 3+2+1. \end{aligned}$$ It is straightforward to check that this gives a partition into distinct parts and that these two conversions are inverses of each other. $_\square$

The Catalan numbers $C_n = \frac1{n+1}\binom{2n}{n}$ count many different objects; in particular, the Catalan number $C_n$ is the size of the set of sequences $(a_1,a_2,\ldots,a_{2n})$ where $a_i = \pm 1$ and the partial sums $a_1 + a_2 + \cdots + a_k$ are always nonnegative. Often the best way to show that the Catalan numbers count a certain set is to furnish a bijection between that set and another set that the Catalan numbers are known to count.

Take $2n$ equally spaced points around a circle. How many ways are there to connect those points with $n$ line segments that do not intersect each other?

---

There are $C_n$ ways to do this. Number the points $1,2,\ldots,2n$ in order around the circle. Let $a_k = 1$ if point $k$ is connected to a point with a higher index, and $-1$ if not. Then it is not hard to check that the partial sums of this sequence are always nonnegative. This gives a function sending the set $S_n$ of ways to connect the set of points to the set $T_n$ of sequences of $2n$ copies of $\pm 1$ with nonnegative partial sums.

The inverse function is not hard to construct; given a sequence in $T_n$, find a part of the sequence that goes $1,-1$. Connect those two points. Now forget that part of the sequence, find another copy of $1,-1$, and repeat. Again, it is routine to check that these two functions are inverses of each other.

For example, given a sequence $1,1,-1,-1,1,-1$, connect points $2$ and $3$, then ignore them to get $1,-1,1,-1$. Then we connect the points $1$ and $4$ (the first $1,-1$ pair) and $5$ and $6$ (the second pair).

Since $T_n$ has $C_n$ elements, so does $S_n$. $_\square$

Again, it is not immediately clear where this bijection comes from. In practice, it is often easier with this type of problem to decide first what the answer will be, by noticing that for small values of $n,$ the number of ways is equal to $C_n$, e.g. $C_1 = 1, C_2 = 2, C_3 = 5$, etc. Once the two sets are decided upon, the only question is how to identify one of the $2n$ points with one of the $2n$ members of the sequence of $\pm 1$ values.

• Discrete Mathematics

• Bijection, Injection, And Surjection