Semu Serunjogi

Over this series of articles we have looked at two problems: one about friends sat around a table shaking hands and another about a two-dimensional man called Bob climbing mountains. At first glance, these problems seem to be completely unrelated, however, we’ve seen that they have a connection: the Catalan numbers. We first saw the nth Catalan number, C_n, when calculating the number of possible socially distanced handshake configurations when 2n friends sit around a circular table, before the same number appeared again when calculating the number of possible 2n-mountain-ranges.

In this article, we shall show that this is not just a coincidence and indeed explain why this is the case. First, we begin by discussing a few concepts that will help us to compare the problems in a more precise way.

{0},            {1, -1/2},           {↺, ➼, 🔺, ⥷},          {1, 2, 3, 4, 5, 6, …}

These are collections of numbers or just… stuff – we call these collections sets. {1, -1/2} is simply the set containing the numbers 1 and -1/2. {↺, ➼, 🔺, ⥷} is a set containing some cool symbols I found. An important point to note is that the order in which you write the contents of a set doesn’t matter. So {1, -1/2} and {-1/2, 1} are the same set, for example.

It’s interesting to see how we can relate one set to another. Let’s think about the sets A = {1, 2, 3, 4, 5} and B ={1, 2, 3, 4, 5, 6}. The idea is to send each number in the first set A to one number in the second set B. Something that does this is called a function from A to B. We see that 1 can be sent to six different possible numbers by a function. So can 2, 3, 4, and 5. This means that there are 6⁵ = 7776 different ways that we can do this. So there are 7776 different functions from A to B and some of them are quite interesting…

The above diagram shows one possible function from A to B where we decide to send 1, 2, 3, 4 and 5 in A all to 6 in B. But if we now look at 6 in B, we have no way of knowing how we got there. Which of 1, 2, 3, 4 and 5 in A did we come from? There is no way for us to tell. So, if we want to be able to know how we got to a number in B, we want every number in A to be sent to a different number in B. If a function from A to B has this property, we say that it is one-to-one.

An example of a one-to-one function from A to B is the function shown above, where 1 goes to 1, 2 goes to 2, 3 goes to 3, 4 goes to 4, and 5 goes to 5. This means if we look at 1, 2, 3, 4 or 5 in B, we know exactly how we got there from A. But you may notice that there’s a problem when we look at the element 6 in B. The function we have here does not send any numbers in A to 6 in B. This means that we are unable to go backwards to A from the 6 in B. So, in order to have any chance of being able to backwards from B to A, we want every number in B to have a number in A that is sent to it. If a function from A to B ‘hits’ all of the numbers in B in this way, we say that it is onto.

An example of an onto function from A = {1, 2, 3, 4, 5} and C = {2, 4, 6, 8, 10} is the function where 1 goes to 2, 2 goes to 4, 3 goes to 6, 4 goes to 8, and 5 goes to 10, which we show above. Hopefully you recognise this as just doubling the input. We can see that this is onto as every number in C has a number (half of itself) in A sent to it.

But do you see anything else? Notice that all of the numbers in A are sent to different numbers in C. This tells us that this function is in fact one-to-one as well. We have a fancy name for functions that are both one-to-one and onto: they are called bijections. The name is not overly important, just remember a bijection has these two properties. You should also notice that if I tell you a number in C that using this function outputs, you can tell me the exact number in A that had to have been used to get our output. This is called being invertible.

Whew… All of this can be generalised, showing us that all bijections are invertible functions and all invertible functions are bijections. They are exactly the same thing! If you look at the previous example, A contained 5 numbers, B contained 6, and C contained 5. We can call the number of items a set contains its size. We couldn’t find a bijection between A and B but we found one between A and C. The problem with B was that the number 6 was left over in our example. This suggests the sizes of the sets matter. In fact, if there is a bijection between two (finite) sets then they must be the same size. Using the definitions of one-to-one and onto, can you see why?

Imagine that we now have three sets A, B, C where there is a bijection from A to B and a bijection from B to C. We now know that A, B, C all have the same number of elements, so we can find a way of pairing all the members of A with the members of C and vice-versa. The way we do this is our bijection. Combining the first and second bijections to give a new bijection from A to C is guaranteed to give us a further bijection.

What was the point in all of this you ask? Well, we can now put all of the socially distanced handshake configurations for 2n friends into a set (call it A) and put all of the 2n-mountain-ranges into another set (call it C). If we can find a bijection between A and C then this will explain why there are the same number of socially distanced handshakes as there are mountain-ranges! We’ll start by working with the n = 3 case as we try to do this.

First off, let us look at something that I call ‘non-intersecting point pairings on a straight line’. Let B be the set containing all of these non-intersecting point pairings when we have six points. The name is a bit of a mouthful but not to worry, these are quite simple things. There are some examples in the diagram above between points on a straight line numbered 1, 2, 3, 4, 5, 6. The point pairings are represented by non-intersecting semicircles that connect two points. The key is that these semicircles are all on the same side of the line. From the examples, we see that 1 can only be connected to 2, 4 or 6. If 1 were connected to an odd numbered point, two semicircles would have to intersect, which is not allowed. Where have we heard of this rule before? We deduced the same constraint back in the first article when we were solving the handshake problem. This means that the handshake configurations have exactly the same structure as the non-intersecting point pairings on a straight line.

Now we need to find a bijection between A and B. If we have a handshake configuration in A, we are free to move the points around so that they lie on a straight line, and this can be done without making any lines intersect or without breaking the lines. This means that we can turn every item of A into an item in B. This process is invertible – the exact reverse process lets us go from every item in B to a different one in A. So we now have our bijection between A and B! The diagrams above show two examples of this.

Now we need to find a way to relate B and C. Let’s look at the non-intersecting point pairings in the examples in the diagrams above. We can cut each of the semicircles in half into quarter-circles. Let’s call the quarter-circles that curve upwards away from the line curve-ups and the quarter-circles that curve downwards towards the line curve-downs. Now if we count the number of curve-ups and curve-downs as we move along the line from the point 1 to the point 6 we see that the number of curve-ups is never less than the number of curve-downs, and there are three of each by the time we reach point 6 on the line. It is clear that the same is true for all of the other non-intersecting point pairing configurations that use six points.

But now let’s look at the 6-mountain-ranges in the same diagrams. If we count the number of step-ups and step-downs as we move along the path, we see that the number of step-ups is never less than the number of step-downs, and there are three of each at the end of the mountain-range. If we look at any other valid 6-mountain-range we shall find the same thing, because the path never goes below the x-axis. But this is exactly the same thing we discovered about the curve-ups and curve-downs in non-intersecting point pairing! This lets us pair up curve-ups with step-ups and curve-downs with step-downs. This is great news because we have found an invertible way for us to go between all of the non-intersecting point pairing configurations and all of the 6-mountain-ranges. Of course, this is a bijection!

We looked at the n = 6 case in our examples but there’s nothing special about it, feel free to try what we did with a general n and you will see that we are first always able to make a bijection between A and B, as well as a second one between B and C. And since we can then combine these to make a bijection between A and C, we now know that the sets A and C are of the same size.

Finally, putting all of this together explains why the number of possible socially distanced handshake configurations when 2n friends are sat around a circular table, and the number of possible 2n-mountain-ranges, are both equal to the nth Catalan number, C_n, precisely as we found in the earlier articles (drops mic).

Throughout this series of articles, we have learned about sequences and recurrence relations as well as being introduced to sets and functions, and finally bijections. All of this has come together as we have shown how two seemingly unrelated problems are actually connected. This is what I love about maths and I hope you have also enjoyed it too!