*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_{1} can make.

Let’s think about what happens when F_{1} and F_{3} shake hands, as we see in Figure 1. We know that F_{2} is unable to shake hands with F_{1} or F_{3} because each friend may only shake hands with one person at a single time. This forces F_{2} to shake hands with F_{4}, F_{5}, or F_{6}. F_{2} cannot go behind F_{1}’s or F_{2}’s backs to shake hands with F_{4}, F_{5}, or F_{6}. These unacceptable handshakes are shown in Figure 2. So the only option for F_{2} is for them to shake hands across the table with F_{4}, F_{5}, or F_{6}. The resulting line would intersect with the line between F_{1} and F_{3}, which is of course not allowed. So, all of this tells us that F_{2} 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_{2} to not shake hands with anyone. Therefore, in order to prevent this from happening, F_{1} and F_{3} cannot shake hands. The same argument shows that F_{1} can only shake hands with the even numbered F_{2}, F_{4}, F_{6} – can you see why?

Before continuing with our investigations we will first introduce some new notation. Let S_{6} 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_{0} is the number of handshakes between zero people. This of course can only happen in one way with zero handshakes, which gives S_{0} = 1. Our approach to calculating S_{6} will be first to think about the different cases of whose hand F_{1} shakes. We can then add up the number of possible handshakes when F_{1} shakes hands with F_{2} to the numbers we get when F_{1} and F_{4} shake hands and when F_{1} and F_{6} shake hands. Since these are the only allowed handshakes that F_{1} can make, this total will give us the number of allowed handshakes, i.e. S_{6}.

Figure 3 shows the line between F_{1} and F_{2} 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_{4} valid handshakes in the circle with 4 people. Therefore, the number of valid handshakes in the case when F_{1} shakes hands with F_{2} is equal to S_{0} * S_{4}.

Similarly, the case when F_{1} shakes hands with F_{4} (Figure 4) splits the circle into two groups of size two. This gives S_{2} * S_{2} handshaking configurations. Finally, the case when F_{1} shakes hands with F_{6} (Figure 5) splits the circle into a group of zero friends and a group of four – just like the case when F_{1} shakes hands with F_{2}. Once again, we have S_{4} * S_{0} possible handshake setups.

Now we can add up the number of configurations we found from each of these cases in order to calculate S_{6}:

S_{6} = S_{0} * S_{4} + S_{2} * S_{2} + S_{4} * S_{0}

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_{2} = S_{0} * S_{0} = 1*1 = 1

Again, using the same argument but now with four friends around a table, and substituting the values we found for S_{0} and S_{2} gives:

S_{4} = S_{0} * S_{2} + S_{2} * S_{0} = 1*1 + 1*1 = 2

Finally, substituting in the values for S_{0}, S_{2}, and S_{4} into the equation for S_{6} gives us:

S_{6} = 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_{8}, the number of handshake configurations when you have eight people around a table:

S_{8} = S_{0} * S_{6} + S_{2} * S_{4} + S_{4} * S_{2} + S_{6} * S_{0}

Now if we substitute in the values for S_{0}, S_{2}, S_{4}, and S_{6} into this recurrence relation we get:

S_{8} = 1*5 + 1*2 + 2*1 + 5*1 = 14

Putting everything together we can see that the numbers S_{0}, S_{2}, S_{4}, S_{6}, and S_{8} are 1, 1, 2, 5, 14. Do you recognise these from somewhere? They are in fact the first five Catalan numbers C_{0}, C_{1}, C_{2}, C_{3}, C_{4} 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.

[…] Using this, we can calculate the first few terms as 1, 1, 2, 5, 14 … (try this!). The reason this is my favourite sequence is two-fold: the symmetry of the recurrence relation and the fact that it uses all previous terms. There’s just something inviting about it that makes you wonder if there is a simplification or trick that would make calculating Cn easier… However, my initial attempts to simplify the recurrence relation led nowhere. Throughout the course of this series of articles, we shall explore the Catalan numbers further and find an alternative method of calculating them. See you for part II. […]

LikeLike

[…] before? These are the first five Catalan numbers C0, C1, C2, C3, C4, 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 M2n = […]

LikeLike