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)
Best Answer
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.