In how many ways can four men and four women be seated at a round table if no two men are to be in adjacent seats?

Question

In how many ways can four men and four women be seated at a round table if no two men are to be in adjacent seats?

Please use principle of inclusion exclusion to solve.

My approach:

Let $S_i$ represent the number of arrangements where $i$ men are adjacent. Thus, $S_2$, for instance, would be ${4 \choose 2}(2!)(6!)$, treating the two adjacent men as one person in the circular arrangement (leaving seven people so $6!$ ways), and there are $2!$ ways to arrange these two adjacent men.

The whole equation would look like:

$$7! - S_2 + S_3 - S_4 = 7! - {4 \choose 2}(2!)(6!) + {4 \choose 3}(3!)(5!) - {4 \choose 4}(4!)(4!) = -1296$$

I am not sure what I did wrong as the result should be positive.

Answer 1

You're overcounting. Take $S_2$: after picking the 2 men AB that are adjacent, you allow everyone else to be placed in $6!$ ways. However, that will include ways in which the other 2 men CD are adjacent as well. So, you are double counting ways in which AB are adjacent and CD are adjacent.

I'll leave it to you to correct your formulas to account for those over-counts. However, please that with the same number of men and women, they all need to alternate if you want to avoid placing two men adjacent to each other, meaning that starting with 1 woman, you have $3!$ ways to place the other $3$ women, and $4!$ ways to place the $4$ men. So, the total should come out to $3!4!$. And for $n$, it should be $(n-1)!n!$

Answer 2

The error you made was counting the number of consecutive men rather than the number of pairs of adjacent men. Let $|A_i|$ be the number of pairs of adjacent men.

Let Angela be one of the women. Seat Angela. We will use her as our reference point. Relative to her, we can arrange the other seven people in $7!$ ways as we proceed clockwise around the table. From these, we must subtract those arrangements in which there are one or more pairs of adjacent men.

A pair of adjacent men: Seat Angela. Choose which two of the four men will sit in adjacent seats. We now have six objects to arrange in the remaining seats, the block of two men and the other five people. Those objects can be arranged in $6!$ ways as we proceed around the table. The two men can be arranged within the block in $2!$ ways. Hence, there are $$|A_1| = \binom{4}{2}6!2!$$ such seating arrangements, which agrees with your count for two consecutive men.

Two pairs of adjacent men: This can occur in two ways. Either the pairs overlap, in which case there are three consecutive men or they are disjoint, so that there are two separate pairs of adjacent men. You did not consider the second of these possibilities.

Two overlapping pairs of adjacent men: Seat Angela. Choose which three of the four men will sit in consecutive seats. We have five objects to arrange in the remaining seats, the block of three men and the other four people. The objects can be arranged in $5!$ ways as we proceed clockwise around the table. Within the block, the three men can be arranged in $3!$ ways. Hence, there are $$\binom{4}{3}5!3!$$ such seating arrangements, which agrees with your count for three consecutive men.

Two disjoint pairs of adjacent men: Seat Angela. Choose which of the other three men is paired with the youngest man. The other two men must form the other pair of adjacent men. We have five objects to arrange in the remaining seats, the two blocks of adjacent pairs of men and the other three women. The objects can be arranged in $5!$ ways as we proceed clockwise around the table. Within each block of two men, the men can be arranged in $2!$ ways. Hence, there are $$\binom{3}{1}5!2!2!$$ such seating arrangements.

Thus, $$|A_2| = \binom{4}{3}5!3! + \binom{3}{1}5!2!2!$$

Three pairs of adjacent men: Since there are only four men, this can only occur if the three pairs are overlapping, that is, if the four men sit in consecutive seats. Seat Angela. We have four objects to arrange in the remaining seats, the block of four men and the other three women. The objects can be arranged in $4!$ ways. The four men can be arranged within the block in $4!$ ways. Hence, $$|A_3| = \binom{4}{4}4!4!$$ which agrees with your count for four consecutive men.

Thus, by the Inclusion-Exclusion Principle, the number of seating arrangements of four men and four women at a round table in which no two men sit in adjacent seats is $$7! - \binom{4}{2}6!2! + \binom{4}{3}5!3! + \binom{3}{1}5!2!2! - \binom{4}{4}4!4! = 144$$

Check: Since there are four men and four women, as Bram28 points out, the only way for the men not to sit in adjacent seats is if the men and women alternate seats. Seat Angela. Doing so determines which of the remaining seats will be filled by women and which will be filled by men. The three seats that are available to the other three women can be filled in $3!$ ways as we proceed clockwise around the table relative to Angela. Once those seats have been filled, the remaining four seats can be filled by the four men in $4!$ ways as we proceed clockwise around the table relative to Angela. Hence, there are $$3!4! = 144$$ seating arrangements of four men and four men at a round table in which no two of the men are adjacent, which agrees with the result we obtained by using the Inclusion-Exclusion Principle.