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 , the idea is to pick a set with elements and a set with elements, and to construct a bijection between and .
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 , 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 , where and are finite positive integer quantities depending on some variables, here is how to prove the formula:
- Find a set such that , and a set such that . 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 is a binomial coefficient or a sum of binomial coefficients, then will be a set of subsets of a larger set, or ways to choose certain objects from a set.
- Think of a way to associate elements of to elements of , or vice versa. Sometimes one of these is initially easier than the other. Use this to construct a function or
- (optional) Verify that is a bijection for small values of the variables, by writing it down explicitly.
- Prove that is a bijection, either by showing it is one-to-one and onto, or (often easier) by constructing the inverse of .
Prove that binomial coefficients are symmetric:
We can prove that binomial coefficients are symmetric: via a bijection. Since counts -element subsets of an -element set , and counts -element subsets of , the proof consists of finding a one-to-one correspondence between those two types of subsets.
The most natural way to produce an -element subset from a -element subset is to take the complement. So let be the set of -element subsets of , and define It is easy to prove that this is a bijection: indeed, is the inverse of , because . So and have the same number of elements; that is, .
To illustrate, here is the bijection when and Since this gives a one-to-one correspondence between -element subsets and -element subsets of a -element set, this shows that .
A key result about the Euler's phi function is Here is a proof using bijections:
Let . Then the number of elements of is just . Now let . To complete the proof, we must construct a bijection between and .
Define by . Define as follows: is the ordered pair Then it is routine to check that and are inverses of each other, so they are bijections.
This is an elegant proof, but it may not be obvious to a student who may not immediately understand where the functions and came from. The original idea is to consider the fractions and reduce them to lowest terms. They will all be of the form for a unique . The set is the set of numerators of the unreduced fractions. The functions and 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 into odd parts is equal to the number of partitions of into distinct parts. For example, and , so there are four of each kind for .
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 , where is odd. Rewrite each part as parts equal to . For example, for , To show that this correspondence is one-to-one and onto, it is easiest to construct its inverse. Given a partition of into odd parts, collect the parts of the same size into groups. Suppose there are parts of size . Then write in binary as where the are distinct. Change the parts into parts: . For instance, It is straightforward to check that this gives a partition into distinct parts and that these two conversions are inverses of each other.
Let be the number of partitions of . Let be the number of partitions of into exactly parts. For example, because Compute
Definition: A partition of an integer is an expression of the integer as a sum of one or more positive integers, called parts. Two expressions consisting of the same parts written in a different order are considered the same partition ("order does not matter").
The Catalan numbers count many different objects; in particular, the Catalan number is the size of the set of sequences where and the partial sums 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 equally spaced points around a circle. How many ways are there to connect those points with line segments that do not intersect each other?
There are ways to do this. Number the points in order around the circle. Let if point is connected to a point with a higher index, and 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 of ways to connect the set of points to the set of sequences of copies of with nonnegative partial sums.
The inverse function is not hard to construct; given a sequence in , find a part of the sequence that goes . Connect those two points. Now forget that part of the sequence, find another copy of , and repeat. Again, it is routine to check that these two functions are inverses of each other.
For example, given a sequence , connect points and , then ignore them to get . Then we connect the points and (the first pair) and and (the second pair).
Since has elements, so does .
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 the number of ways is equal to , e.g. , etc. Once the two sets are decided upon, the only question is how to identify one of the points with one of the members of the sequence of values.