0
$\begingroup$

We are seating 5 married couples around a circular table (the seats are identical). Let {m1,m2,m3,m4,m5} be the set of men and let {w1,w2,w3,w4,w5} be the set of their wives. In how many ways the man 1 will be seated next to his wife and the man $3$ will not seat next to his wife?

The total number of ways they could seat with no restrictions would be $(10-1)!$ to arrange themselves.

  • M1W1 must seat together Let's consider w1m1 as one unit. Thus we are left with $9$ people instead. However, w1 and m1 can be arranged among themselves in $2!$ ways, therefore, the answer is $(9-1)!*2!$ because of circular arrangement.

  • Let's consider the case where M3 and W3 are together along with M1 and W1. m1w1, m3w3 Now we have 8 people left. w1m1 can be arranged among themselves in 2! ways as w3m3 so we get $(8-1)!*2*2$ because of the circular arrangement

We need arrangements when w3 and m3 are not together..

Total arrangements = $(8!*2!)-(7!*2!*2!)$

  • Is it correct?
  • Do I need to subtract the final answer from the total number of arrangements with no restrictions?
  • How do I properly do this using the inclusion and exclusion principle?

Update: My attempt at solving it using inclusion/exclusion principle

The total number of arrangements with no restrictions would be $$(10-1)!$$

Arrangements where m1w1 are not together would be

_m2_m3_m4_m5_w2_w3_w4_w5_

We have 9 spots where we want to place 2 people and arrange them in 2 ways, then we are left up with 8 other people.

$$(8-1)! * {9-1 \choose 2 } * 2!$$

Arrangements where m3w3 are together

Considering m3w3 as one unit. Now we are left with 9 groups and we can still arrange m3w3 among themselves in 2! ways. $$(9-1)!*2$$

Arrangements where m1w1 are not together, m3w3 are together

_m3w3_m2_m4_m5_w2_w4_w5_

Again we have 2 letters to be placed in 8 spots namely m1 and w1, and then we arrange them in 2 ways. After that, we arrange the 7 other people having m3w3 as one group, so that could be done in (7-1!) in a circular table and again they could be arranged in two different ways. Therefore, we get the following:

$$ {8-1 \choose 2 } * 2! * (7-1)! * 2!$$

Final answer: $$ 9!-(7! * {8 \choose 2 } * 2! + 8!*2 - {7 \choose 2 } * 2! * 6! * 2!) $$

I am getting the same answer from this as in the above, so it means that my implementation of inclusion and exclusion is correct?

$\endgroup$
0
$\begingroup$

The total number of ways to seat them is only $9!$. You seat one person, say m1, to identify a chair, then put the others in order. Your $8!2!$ is correct for the number of ways with m1,w1 together. The subtraction for m3,w3 is also correct and you are done. You don't need to involve the total number of arrangements at all.

$\endgroup$
  • $\begingroup$ Great! So by subtracting $(8!∗2!)−(7!∗2!∗2!)$, we have the final answer? $\endgroup$ – Mr Pro Pop May 31 '18 at 16:46
  • $\begingroup$ That is correct $\endgroup$ – Ross Millikan May 31 '18 at 16:49
  • $\begingroup$ Using IE you would start with all arrangements, subtract the number that have each couple apart, then add back the ones that have both apart. This is a much more difficult route for this problem. $\endgroup$ – Ross Millikan May 31 '18 at 16:56

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.