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 Fk represent friend k. This allows us to consider the possible handshakes F1 can make.
Let’s think about what happens when F1 and F3 shake hands, as we see in Figure 1. We know that F2 is unable to shake hands with F1 or F3 because each friend may only shake hands with one person at a single time. This forces F2 to shake hands with F4, F5, or F6. F2 cannot go behind F1’s or F2’s backs to shake hands with F4, F5, or F6. These unacceptable handshakes are shown in Figure 2. So the only option for F2 is for them to shake hands across the table with F4, F5, or F6. The resulting line would intersect with the line between F1 and F3, which is of course not allowed. So, all of this tells us that F2 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 F2 to not shake hands with anyone. Therefore, in order to prevent this from happening, F1 and F3 cannot shake hands. The same argument shows that F1 can only shake hands with the even numbered F2, F4, F6 – can you see why?
Before continuing with our investigations we will first introduce some new notation. Let S6 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: S0 is the number of handshakes between zero people. This of course can only happen in one way with zero handshakes, which gives S0 = 1. Our approach to calculating S6 will be first to think about the different cases of whose hand F1 shakes. We can then add up the number of possible handshakes when F1 shakes hands with F2 to the numbers we get when F1 and F4 shake hands and when F1 and F6 shake hands. Since these are the only allowed handshakes that F1 can make, this total will give us the number of allowed handshakes, i.e. S6.
Figure 3 shows the line between F1 and F2 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 S4 valid handshakes in the circle with 4 people. Therefore, the number of valid handshakes in the case when F1 shakes hands with F2 is equal to S0 * S4.
Similarly, the case when F1 shakes hands with F4 (Figure 4) splits the circle into two groups of size two. This gives S2 * S2 handshaking configurations. Finally, the case when F1 shakes hands with F6 (Figure 5) splits the circle into a group of zero friends and a group of four – just like the case when F1 shakes hands with F2. Once again, we have S4 * S0 possible handshake setups.
Now we can add up the number of configurations we found from each of these cases in order to calculate S6:
S6 = S0 * S4 + S2 * S2 + S4 * S0
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:
S2 = S0 * S0 = 1*1 = 1
Again, using the same argument but now with four friends around a table, and substituting the values we found for S0 and S2 gives:
S4 = S0 * S2 + S2 * S0 = 1*1 + 1*1 = 2
Finally, substituting in the values for S0, S2, and S4 into the equation for S6 gives us:
S6 = 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 S8, the number of handshake configurations when you have eight people around a table:
S8 = S0 * S6 + S2 * S4 + S4 * S2 + S6 * S0
Now if we substitute in the values for S0, S2, S4, and S6 into this recurrence relation we get:
S8 = 1*5 + 1*2 + 2*1 + 5*1 = 14
Putting everything together we can see that the numbers S0, S2, S4, S6, and S8 are 1, 1, 2, 5, 14. Do you recognise these from somewhere? They are in fact the first five Catalan numbers C0, C1, C2, C3, C4 in order! This may lead you to think that S2n = Cn 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 Cn. 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.