A round table has chairs around it. Due to social distancing guidelines, no two people are allowed to sit next to each other. How many different ways are there to choose seats around the table on which guests can be seated?
Solution
Solution 1. Either there are 3 consecutive empty seats or two separate pairs of empty seats. In the first case, there are possibilities as the middle of the three empty seats can be any of the seats. In the second case, there are two pairs of empty seats. If the seats are numbered 1 to then one of the pairs of empty seats will be odd-even and the other even-odd. There are choices for the odd-even empty pair. For each of these there are choices for the odd number in the even-odd pair. That gives rise to seating arrangements. Adding the two cases gives a total of possibilities.
Solution 2. Divide the seats into pairs of consecutive seats. of these pairs contain one person and the other is empty. There are ways to choose which pair is empty. The remaining seats are occupied in the form 01 or 10 where 1 represents occupation. Working clockwise from the empty pair, the sequence starts with a (possibly empty) sequence of the form 101010...10 and finishes with a (possibly empty) sequence of the form 01...0101. Considering the possible lengths of the starting sequence we find that there are different possible sequences of this kind. This gives a total of possibilities.
Solution 3. Let be the path graph with edges. A set of vertices of a graph is an independent set if no two vertices of are adjacent. Let = the number of independent sets of size of the graph . Number the seats 1, 2, ..., . There are two options:
(A) seat 1 is occupied and so seats 2 and are empty;
(B) seat 1 is empty.
The number of possibilities in case (A) is and in case (B) is . Using the ideas from solution 1 or 2 it is easy to show that . Hence the number of possibilities is equal to .