Semu Serunjogi

Welcome back to the introductory series on recurrence relations. If you missed part 1 you can find it here.

Imagine the following situation:

6 friends are seated around a circular table. The friends have been in lockdown and have not met in a while, so they choose to shake hands to greet each other. However, they want to minimise their exposure to each other and do so by not crossing arms when shaking hands. The handshakes must happen across the table and not behind someone’s back. Nobody is allowed to shake hands with more than one friend at a time. In how many ways can 3 pairs of friends engage in handshakes so that no arms cross?

I call this problem ‘socially distanced handshakes’ due to the fact each pair is avoiding the others, in a sense. Here’s how I thought about a solution…

To start, we can ignore the table and just think about the friends and how they interact. The friends can be thought of as points arranged in a circle while the handshakes represent a way of connecting these points. It is also useful to number the points clockwise from one to six, as in Figure 1. Let F_k represent friend k. This allows us to consider the possible handshakes F₁ can make.

Let’s think about what happens when F₁ and F₃ shake hands, as we see in Figure 1. We know that F₂ is unable to shake hands with F₁ or F₃ because each friend may only shake hands with one person at a single time. This forces F₂ to shake hands with F₄, F₅, or F₆. F₂ cannot go behind F₁’s or F₂’s backs to shake hands with F₄, F₅, or F₆. These unacceptable handshakes are shown in Figure 2. So the only option for F₂ is for them to shake hands across the table with F₄, F₅, or F₆. The resulting line would intersect with the line between F₁ and F₃, which is of course not allowed. So, all of this tells us that F₂ doesn’t in fact shake hands with anyone!

However, we are looking for setups where three pairs of friends shake hands so we cannot afford for F₂ to not shake hands with anyone. Therefore, in order to prevent this from happening, F₁ and F₃ cannot shake hands. The same argument shows that F₁ can only shake hands with the even numbered F₂, F₄, F₆ – can you see why?

Before continuing with our investigations we will first introduce some new notation. Let S₆ be the number of ways the 6 friends can shake hands in the manner described in the question – i.e. this is the answer to the problem. We start with the simplest case: S₀ is the number of handshakes between zero people. This of course can only happen in one way with zero handshakes, which gives S₀ = 1. Our approach to calculating S₆ will be first to think about the different cases of whose hand F₁ shakes. We can then add up the number of possible handshakes when F₁ shakes hands with F₂ to the numbers we get when F₁ and F₄ shake hands and when F₁ and F₆ shake hands. Since these are the only allowed handshakes that F₁ can make, this total will give us the number of allowed handshakes, i.e. S₆.

Figure 3 shows the line between F₁ and F₂ separates the circle into two ‘circles’ of zero people and four people, either side of the line. These may not physically look like circles but that doesn’t change the maths. Friends on one side of the line cannot shake hands with those on the other, or else arms will cross, which is not allowed. This means that what happens in one of the new circles does not affect what happens in the other. So for each valid handshake in the the circle with zero people there are S₄ valid handshakes in the circle with 4 people. Therefore, the number of valid handshakes in the case when F₁ shakes hands with F₂ is equal to S₀ * S₄.

Similarly, the case when F₁ shakes hands with F₄ (Figure 4) splits the circle into two groups of size two. This gives S₂ * S₂ handshaking configurations. Finally, the case when F₁ shakes hands with F₆ (Figure 5) splits the circle into a group of zero friends and a group of four – just like the case when F₁ shakes hands with F₂. Once again, we have S₄ * S₀ possible handshake setups.

Now we can add up the number of configurations we found from each of these cases in order to calculate S₆:

S₆ = S₀ * S₄ + S₂ * S₂ + S₄ * S₀

To calculate the values of each of the Sn we again start by considering the smallest cases. If we have two friends around a table, using the same argument as above tells us:

S₂ = S₀ * S₀ = 1*1 = 1

Again, using the same argument but now with four friends around a table, and substituting the values we found for S₀ and S₂ gives:

S₄ = S₀ * S₂ + S₂ * S₀ = 1*1 + 1*1 = 2

Finally, substituting in the values for S₀, S₂, and S₄ into the equation for S₆ gives us:

S₆ = 1*2 + 1*1 + 2*1 = 5

And so there are exactly five ways for the six friends to shake hands with the given constraints!

At this point you may have started to spot a pattern, and with some thought (and bravery) you may be able to come up with the recurrence relation for S₈, the number of handshake configurations when you have eight people around a table:

S₈ = S₀ * S₆ + S₂ * S₄ + S₄ * S₂ + S₆ * S₀

Now if we substitute in the values for S₀, S₂, S₄, and S₆ into this recurrence relation we get:

S₈ = 1*5 + 1*2 + 2*1 + 5*1 = 14

Putting everything together we can see that the numbers S₀, S₂, S₄, S₆, and S₈ are 1, 1, 2, 5, 14. Do you recognise these from somewhere? They are in fact the first five Catalan numbers C₀, C₁, C₂, C₃, C₄ in order! This may lead you to think that S_2n = C_n for n ≥ 0 and you would be correct! To show this, try to think about how you could tackle the general problem when there are 2n friends sat around a table…

Quite amazingly, you will find that the number of socially distanced handshakes between 2n people, is given by the nth Catalan number C_n. How unexpected was that? In the next article, we shall discuss – and solve – a seemingly unrelated problem, helping us to find another formula for the Catalan numbers.