Bijective Proofs and Catalan Numbers
Combinatorics is the study of counting, and typically we are interested in counting the size of a set of objects. This post describes a tool and proof technique that can relate set to each other, making them easier to count, and the Catalan numbers, which is a recurrence that is used to describe many different sets of mathematical objects.
Counting and Bijective Proofs
The number of possible hands in a game of poker, how many ways to select a 3 number of people from a group of 5, and the number of ways to arrange books on a book self are all examples of sets that can be counted. These are relatively simple problems that can be enumerated with basic combinations and permutations, but the complexity of a sets in counting problems can grow quickly.
A bijective proof is a tool that can be used to prove 2 sets are the same size, without actually counting the size of both of them. If you know the size of 1 set, this can tell you the size of the other set, but even if you don’t know the size of either set, it is still possible to show they are the same size.
Bijective Functions
A bijective function is an invertible function. If you are unfamiliar with a bijective or invertible function, you should read the post below, which discusses these function types and the Pigeonhole Principle, another great idea in combinatorics.
The key idea behind invertible functions, a function f: X → Y for example, is that every element in X is mapped to a specific element in Y, and the inverse function maps every element in Y to a specific element in X.
For a bijective function f: X → Y, there exist an inverse, bijective function f{-1}: Y →X. The composition of these functions becomes the identity function. This means that for any x in X, f{-1}(f(x)) = x, and for any y in Y, f(f{-1}(y))=y.
Using bijective functions, we can have an invertible map between 2 sets that shows they are exactly the same size.
Bijective Proofs
If we have 2 sets and show there exist a bijective function between them, then the sets must be the same size. This follows from the fact that if 1 set were larger (or smaller) than the other, then it would not be possible to have an invertible function between them.
As a simple example, consider the case of selecting k friends from a set of n friends to get ice cream with (where k ≤ n, and both are positive numbers). The set we will count is the number of ways this can be selected. If you have seen combinations before, this is the very simple case of n choose k. However, rather than working with the combination, we will show this set is the same size as the number of ways to choose n-k friends to invite for ice cream, still from the same set of n friends.
If you have seen basic counting before, this is equivalent to showing:
n choose k = n choose (n-k)
An outline for what a bijective proof of this looks like is as follows:
Proof: To show (n choose k) = (n choose (n-k)) using a bijective proof, we must define a function f between these 2 sets and show the function is bijective.Consider the initial case of selecting k friends from the set of n. Let f be a function from the set of k friends to the set of n-k friends defined so that every friend not selected in the first k friends is selected in the n-k friends. There exist an inverse function f{-1} from the set of n-k friends to the set of k friends defined so that every friend not selected in the first n-k friends is selected in the k friends.Since there exist an invertible or bijective function between (n choose k) and (n choose (n-k)), it follows that these sets must be the same size.
The general structure of this bijective proof is correct. Often, more work can be done to rigorously show your function is invertible or bijective. Depending on the level of proof and what assumptions you are willing to make, defining and demonstrating a function between 2 sets can become much more complicated, but in the case of picking groups, it should be intuitive that the above function which selects the complement group is invertible. The key insight is that if 2 sets have an invertible function between them, then they must be the same size.
Catalan Numbers
What do polynomial triangulations, rooted binary trees, and lattice walks have in common? There exist a bijective proof between each of these sets.
Catalan Numbers are a set of numbers that can count an extraordinary number of sets of objects. Defined with a recurrence relation and generating function, some of the patterns between these objects seem entirely unrelated.
The above recurrence relation is very complicated and often not the easiest to work with. Rather than demonstrating a set of objects fits this recurrence relation, it can be much simpler to find a bijective function between the set you are working with and any one of the hundreds of sets counted by Catalan numbers. This makes use of the bijective proof technique and can save you a big headache from working with massive summation terms.
Catalan numbers are some of my favorite sets to work with because they arise in so many different cases. The book “Catalan Numbers” by Richard Stanley, a professor at MIT, discusses 214 different sets that can be counted by this recurrence relation, even though they are often easier to count with a bijection.
I plan to write another post specifically on Catalan Numbers and the sets they count soon.
If you made it this far, hit the clap button. I’m new to Medium, and trying to crank out some content about how I think about math, data science, and computers. Follow me that’s if your sort of thing.
