Semu Serunjogi

Bob is a two-dimensional man who lives in a two-dimensional world – meaning he can only move in 2 directions: horizontally (via the positive x-axis) and vertically (via the positive y-axis). Bob likes to climb mountains.

Let’s consider a mathematical model to describe Bob and his mountaineering adventures. We define ‘step-ups’ and ‘step-downs’ as in the picture below. Furthermore, a ‘6-mountain-range’ means a line made up of step-ups and step-downs that starts at (0, 0) and ends at (0, 6), without ever going below the positive x axis. With this setup, an interesting question that we may want to solve is: what is the total number of possible 6-mountain-ranges that Bob may climb?

Here are some diagrams of valid and invalid 6-mountain-ranges to give you an idea of how it works:

My solution:

To solve the problem we need to find the total number of ways of getting from (0, 0) to (6, 0) using step-ups and step-downs. Some of these paths will be valid 6-mountain-ranges, the rest will be invalid. If we can find the total number of invalid 6-mountain-ranges, then we can subtract this from the total number of ways of getting from (0, 0) to (6, 0) to leave us with the total number of valid 6-mountain-ranges that Bob can walk along.

Before we start, let’s talk about a concept that will help us to calculate the total number of paths from (0, 0) to (6, 0). Imagine there are four different sweets available and you can choose two. In how many different ways can you choose 2 sweets? It’s helpful to imagine putting the sweets in order: there are 4 choices for the first sweet, 3 choices for the second, then 2 and then 1. This can be seen in the above diagram. So there are 4*3*2*1 = 24 different ways that we could order the sweets. This can be written as 4! where the exclamation mark – known as a factorial – shows this repeated multiplication.

Now let’s number the sweets 1, 2, 3, 4. There are six different ways of picking two sweets: 1 and 2, 1 and 3, 1 and 4, 2 and 3, 2 and 4, 3 and 4. I found these by always making the second number bigger than the fixed first number and then increasing the first number so I know that I’ve found all of the choices. I urge you to try doing this with some physical sweets if you can get your hands on any!

Now that we’ve seen this, we could also choose to separate the sweets into two groups: the two you picked and the two you didn’t. You may notice that for the first choice of two sweets, for instance, I could have said pick 2 and 1. This is obviously the same thing as 1 and 2. This tells us that the order in which you pick sweets doesn’t matter – what’s important is which sweets you end up with in the end. The same is true for the sweets you don’t pick.

For each group containing 2 sweets there are 2! = 2*1 = 2 different pairings you can select (just as there were 4! different options when picking 4 sweets). What this means is that when you put the sweets in an order, the ones that were picked can be treated as being the same and those that weren’t picked can also be treated as being the same (in terms of their ordering). This tells us that, for ANY given order of sweets, we can swap the 2 sweets you picked amongst themselves and the 2 sweets you didn’t pick amongst themselves without changing the line of sweets – as we see in Figure 2. So the 4! different ordering of sweets we had before can now be separated into identical groups of size (2!)*(2!).

This tells us that there are (4!) / [(2!)*(2!)] = 6 genuinely different lines of sweets and hence 6 ways to pick 2 sweets from 4, as we expected. We can write this number as ₄C₂, which is pronounced “4 choose 2” for obvious reasons. If you were choosing 3 from 5 different available sweets, this could be done in ₅C₃ = 5! / [(3!)(2!)] = 10 different ways. These are known as binomial coefficients. I urge you to try listing all the different possible choices of sweets to convince yourself that we’ve counted all of them.

Now, back to Bob and his mountaineering adventures. The goal here is to use our new tool of binomial coefficients to calculate the number of paths from (0, 0) to (6, 0) that only use step-ups and step-downs. A step-up increases the y and x values by 1 while a step-down increases the x value by 1 and decreases the y value by 1. This means that in order to go from (0, 0) to (6, 0), we must use the same number of step-ups as step-downs. Here, the x value has increased by 6 so there must have been 3 step-ups and 3 step-downs. Different orders of step-ups and step-downs lead to different paths from (0, 0) to (6, 0) and vice-versa. Each path is made by choosing the three positions in which the step-ups occur from the six positions in total. Therefore, using binomial coefficients, there are ₆C₃ = 6! / [(3!)*(3!)] = 20 different paths from (0, 0) to (6, 0) using step-ups and step-downs.

We have some examples of these 20 possible paths above. As indicated in the captions, we can identify each path by the order in which we put the step-ups (U) and step-downs (D).

It’s now time for us to look at invalid 6-mountain-ranges. We might first ask what is special about these mountain-ranges that makes them invalid? Well, it’s the fact that they go below the x-axis at some point on their path. This means that they must hit the line y = -1 for the first time at some point, let’s call it P (as shown in the above diagram). We can consider an invalid 6-mountain-range in two paths: the path before P (black line), and the path after P (solid green line).

Since step-ups increase the x-value by 1 and step-downs decrease it by 1, the path passes through the line y = -1 if and only if there has been one more step-down than step-up. This means that there is one more step-down than step-up before P and one more step-up than step-down after P. 

Ok, now let’s choose to reflect the path after P in the line y = -1. This may seem completely random, and I admit that there’s a little bit of a leap at this point, but there’s a method to the madness. We have already seen that the line y = -1 is crucial so it makes sense that we focus on it. All invalid 6-mountain-ranges meet this line and none of the valid ones do. We also know that at the special point P on the line, there’s one more step-down than step-up to the left of P and one more step-up than step-down after P. A reflection of the part of the path after P in the line y = -1 switches the step-ups and step-downs after P with each other. So we now get a new path that has a different number of step-ups to step-downs which provides us with an interesting way of analysing the invalid 6-mountain-ranges.

In our diagram above the solid green line has been reflected in the line y = -1 in order to give us the dotted green line. As we’ve discussed, this reflection turns step-ups into step-downs and vice-versa, which causes the new path to now have two more step-downs than step-ups. This means that the new path now goes from (0, 0) to (6, -2).

Now imagine we have a path that uses step-ups and step-downs to go from (0, 0) to (6, -2). An example of such a path is shown above. This path must clearly pass through the line y= -1 for the first time at some point. Let us give this point the name P’. By the same reasoning as before, reflecting the path after P’ in the line y = -1 creates a new path from (0, 0) to (6, 0) that touches the line y = -1 at least once (it clearly does at P’). Looking at the above diagram, we have reflected the solid green line in the line y = -1 and created a new dotted green line which goes to (6, 0). This means that overall we have a path that goes from (0, 0) to (6, 0) and goes below the x-axis. But this is of course an invalid 6-mountain-range!

Let’s take a moment to understand what we have done here. We have found a way of turning every invalid 6-mountain-range into a path from (0, 0) to (6, -2), as well as turning every path from (0, 0) to (6, -2) into a 6-mountain-range with the opposite method. This means each invalid 6-mountain-range can be paired up with a unique path from (0, 0) to (6, -2) and vice-versa, which tells us that the total number of 6-mountain-ranges equals the total number of paths from (0, 0) to (6, -2). We can see that any path from (0, 0) to (6, -2) must use 4 step-downs and 2 step-ups. Using binomial coefficients, we can calculate that there are ₆C₄ = 6! / [(4!)*(2!)] = 15 of these paths. Therefore, we now know that there are 15 invalid 6-mountain-ranges. Finally, we subtract the number of invalid paths from the total number of paths found earlier to give 20 – 15 = 5 valid 6-mountain-ranges for Bob to walk along!

You may think that there is nothing special about the number 6, and you would be correct. For the more general case, let M_2n be the total number of possible 2n-mountain-ranges for n ≥ 0. A 0-mountain-range is just the path from (0, 0) to (0, 0), going nowhere. Clearly, only one such path exists. This tells us that M₀ = 1.

Since a path from (0, 0) to (2n, 0) must have n step-ups and n step-downs, as before we can choose where to put the step-ups to create a path, so there are _2nC_n of these paths. We also see that there are _2nC_n+1 invalid 2n-mountain-ranges, thanks to the same reasoning that we used before. These values – along with some algebra – gives us the total number of valid 2n-mountain-ranges, M_2n:

M_2n = _2nC_n – _2nC_n+1 = (2n!) / [(n!)*(n!)] – (2n!) / [(n+1)!(n-1)!] = (2n!)*(n+1) – (2n!)*n / [(n+1)!n!] = 1 / [n+1] * (2n!) / [(n!)*(n!)] = 2_nC_n \ [n+1]

Don’t be intimidated by the algebra, just remember how we use factorials to show repeated, decreasing multiplication. Now let’s use this formula to calculate the number of different 2n-mountain-ranges for the first few values of n to check that everything seems sensible:

M₀ = 0! / [0!*0!] * 1\ [0 + 1] = 1 (where 0! = 1)

M₂ = 2! / [1!*1!] * 1 / [1 + 1] = 1

M₄ = 4! / [2!*2!] * 1 / [2 + 1] = 2

M₆ = 6! / [3!*3!] * 1 / [3 + 1] = 5

M₈ = 8! / [4!*4!] * 1 / [4 + 1] = 14

Now, where have we seen the numbers 1, 1, 2, 5, 14 before? These are the first five Catalan numbers C₀, C₁, C₂, C₃, C₄, as well as the answers to the handshake problem when there are 0, 2, 4, 6, and 8 friends around a table! Could it possibly be true that  M_2n = C_n  for all n ≥ 0? After all, there are no coincidences in mathematics…

In the next article (COMING SOON), we shall explore how on Earth two seemingly unrelated problems about friends shaking hands and a two-dimensional man climbing mountains can give us the same answer – see you then!