0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I want a solution for this problem $\endgroup$ – Arshia R Apr 3 '17 at 13:20
  • $\begingroup$ Yes, I know you want a solution, but have you already tried to solve this problem? You should explain what you have done already. $\endgroup$ – Connor Harris Apr 3 '17 at 13:27
  • $\begingroup$ @ConnorHarris excuse me . $\endgroup$ – Arshia R Apr 3 '17 at 14:03
0
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ The question said 6 couples, not 6 people. $\endgroup$ – J.G. Apr 3 '17 at 13:50
  • $\begingroup$ Oh, you're right. $\endgroup$ – Connor Harris Apr 3 '17 at 13:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.