My question is from discrete and combinational mathematics by R.Grimaldi . The question is : Six married couples are to be seated at a circular table In how many ways can they arrange themselves so that no wife sits next to her husband ? How to solve it with inclusion and exclusion and does it have any combinatorial solutions ? Thanks
THIS IS WRONG (SEE COMMENTS). I'M LEAVING IT UP AS AN EXAMPLE OF A POSSIBLE METHOD.
Let's call the people Mr. and Mrs. A, B, and C. Let's number the seats at the table clockwise 1 through 6, and say that Mr. A always sits in seat 1. (As the table is circular, seating patterns count as identical if they differ by rotation, so every seating pattern is equivalent to a seating pattern with Mr. A in seat 1.) We know Mrs. A can't be in seat 2 or 6. Now let's break into cases, depending on whether the occupants of seats 2 and 6 are married.
Case 1: the occupants of seats 2 and 6 are married. Four symmetrical sub-cases: Mr. B is in seat 2 and Mrs. B is in seat 6 (or vice versa), or Mr. C is in seat 2 and Mrs. C is in seat 6 (or vice versa). Let's take the first sub-case for concreteness. Then Mrs. A and Mr. and Mrs. C have to occupy seats 3, 4, and 5. Mrs. A has to take seat 4 (otherwise Mr. and Mrs. C would sit next to each other), so there are two ways to arrange seats 3, 4, and 5 (either Mr. C takes seat 3, or Mrs. C does). The other three sub-cases are identical, giving $2 \times 4 = 8$ seating patterns.
Case 2: the occupants of seats 2 and 6 are unmarried. Four symmetrical sub-cases: Mr. B in seat 2 and Mrs. C in seat 6 (or vice versa), or Mrs. B in seat 2 and Mr. C in seat 6 (or vice versa). Let's take the first case for concreteness. Mrs. A, Mrs. B, and Mr. C are in seats 3, 4, and 5, with the restrictions that Mrs. B can't take seat 3 and Mr. C can't take seat 5. In this case, any of the three can take seat 4, but the occupants of seats 3 and 5 are determined by the occupant of seat 4 (because Mrs. B and Mr. C must take seats 5 and 3, respectively, if they are not chosen for seat 4). This gives three patterns per sub-case, so $3 \times 4 = 12$ overall.
The total number of possibilities is $8 + 12 = 20$.