# Placing 8 people around a table so that 2 people never sit together

The Question:
"Eight people are to be seated around a table; the chairs don't matter, only who is next to whom, but left and right are different. Two people, X and Y, cannot be seated next to each other. How many seating arrangements are possible?"

My Method:
First, I imagined the combinations of just seating 8 people at the table, by placing a person in a chair. This leaves 7! total possible combinations of seating arrangements. However, this is too many combinations - it includes the combinations where X and Y are sitting together.
To correct this, I determined how many invalid options we created by seating X and Y together. By treating X and Y as a single entity, XY, taking up 2 seats, I treated the new problem as picking 7 seats with 7 people. As before, I placed a person in a seat, giving a total of 6! unique combinations too many.
However, this overshoot (6!) is still not correct, as it only takes into account the combination XY (YX would have also been counted in the original number of total combinations). Since there are 2 ways that X and Y can be combined, the actual overshoot is 2$*$6!.
With this, we can say that 7! gives the total possible combinations, while 2$*$6! gives the overshoot, meaning that there are 7!-(2$*$6!) combinations (3600 combinations).
Does this method work and produce the correct answer? If it does produce the correct answer, is there a better (or more ideal) way to view this problem? If it does not work, where did I go wrong?

I am working my way through "Introduction to Combinatorics and Graph Theory", by David Guichard (which is where this problem comes from) on my own, and I don't have any real way to determine how well I am grasping the material yet (I haven't found a solutions manual to verify even the numbers are correct, let alone the method to reach the solution)

Your solution is correct. We can see this by taking another approach.

Seat $X$. We can then seat $Y$ in five places since the seats next to $X$ are prohibited. That leaves six seats open. The remaining people can be seated in $6!$ ways as we proceed clockwise around the table relative to $X$. Hence, there are $5 \cdot 6! = 3600$ permissible seating arrangements, as you found.

• Shouldn't it be $8\cdot 5\cdot 6!$ because we can seat $X$ on any chair? The question asserted "the chairs don't matter" thus when seating $X$, it shouldn't be fixed, and so we would have to apply your method $7$ times more. Commented Feb 14, 2020 at 5:01
• @MrPie The convention for circular permutations is that only the relative order of the people matters. Therefore, it does not matter where $X$ sits. Once $X$ sits, we measure permutations relative to $X$. There are $(n - 1)!$ distinguishable permutations of $n$ people at a circular table since once we seat a particular person, there are $(n - 1)!$ orders in which we can seat the remaining $n - 1$ people as we proceed clockwise around the table from that person. Commented Feb 14, 2020 at 8:58
• I see what you mean. Thanks for the explanation, and sorry to bug you given that this answer is 2 years old. Commented Feb 14, 2020 at 10:42
• @MrPie You should feel free to ask questions about old answers or questions. They are meant to be a resource. I summarized some results about circular permutations here. Commented Feb 14, 2020 at 15:18