Here is the question:
The 10 members of a school board are having a meeting around a circular table. 3 members, Anna, Bob, and Carl dislike each others ideas, and refuse to sit next to each other. In how many ways can the school board members gather around the table? Rotations are considered the same, but reflections are considered distinct.
I decided to use complementary counting. I found that there are $30240$ ways for A, B, and C to sit together because of $7! \times 6$. Then I broke up the pairs AB, AC, and BC into three identical cases.
AB: $8! \times 2 = 80640 – 30240 = 50400$
AC: $50400$
BC: $50400$
$50400 \times 3 + 30240 = 181440 \Longrightarrow 362880-181440 \Longrightarrow 181440$
However, $181440$ isn't listed the correct answer. It is $151200$. I don't understand this answer because I feel like that would be overcounting the complementary cases. Which answer is correct, and why? Thanks!
Best Answer
Method 1: We seat the other seven people, then seat Anna, Bob, and Carl.
There are $6!$ distinguishable ways to seat seven people in a circle. Seating these seven people creates seven spaces, one to the right of each person at the table, in which Anna, Bob, and Carl can be seated. To separate them, we must choose three of these spaces in which to place them. Anna can be placed in seven ways, leaving six ways to place Bob, and five ways to place Carl. Therefore, the number of admissible seating arrangements is $$6! \cdot 7 \cdot 6 \cdot 5 = 151,200$$
Method 2: We use the Inclusion-Exclusion Principle.
There are $9!$ distinguishable ways to seat ten people in a circle. From these arrangements, we must subtract those arrangements in which two or more of Anna, Bob, and Carl sit in adjacent seats.
Anna sits next to Bob: We have nine objects to arrange, the block containing Anna and Bob and the other eight people. The nine objects can be arranged in a circle in $8!$ distinguishable ways. Anna and Bob can be seated within the block in $2!$ ways. Hence, there are $8!2!$ such seating arrangements.
By symmetry, there are also $8!2!$ seating arrangements in which Anna sits next to Carl and $8!2!$ seating arrangements in which Bob sits next to Carl.
However, if we simply subtract $3 \cdot 8!2!$ from $9!$, we will have subtracted too much since we have subtracted arrangements in which Anna sits next to both Bob and Carl twice, once when we subtracted arrangements in which she sits next to Bob and once when we subtracted arrangements in which she sits next to Carl. Similarly, we have also subtracted arrangements in which Bob sits next to both Anna and Carl and arrangements in which Carl sits next to both Anna and Bob twice. We only want to subtract such arrangements once, so we must add them back.
Anna sits next to Bob and Carl: We have eight objects to arrange, the block containing Anna, Bob, and Carl and the other seven people. The eight objects can be arranged in a circle in $7!$ distinguishable ways. Bob and Carl can be arranged in the seats adjacent to Anna in $2!$ ways. Hence, there are $7!2!$ such seating arrangements.
By symmetry, there are also $7!2!$ seating arrangements in which Bob sits next to Anna and Carl and $7!2!$ seating arrangements in which Carl sits next to Anna and Bob.
Hence, the number of admissible seating arrangements is $$9! - 3 \cdot 8!2! + 3 \cdot 7!2! = 151,200$$
Method 3: We correct your count.
You are correct that there are a total of $9! = 362,880$ seating arrangements and $3 \cdot 7!2! = 30,240$ seating arrangements in which Anna, Bob, and Carl all sit together.
However, your count for having exactly two people together is incorrect.
Anna and Bob sit together but Carl sits separately from them: As we calculated above, there are $8!2! = 80,480$ arrangements in which Anna sits next to Bob.
You incorrectly subtracted the $3 \cdot 7!2! = 30,240$ arrangements in which all three people sit together from the total to find the number of arrangements in which Anna and Bob sit together but Carl sits separately from them. The reason this does not work is that these arrangements include those in which Carl sits between Anna and Bob, which is not possible if Anna and Bob are sitting together.
Suppose Anna and Bob sit together and Carl is adjacent to them. Anna and Bob can sit next to each other in $2!$ ways. In either case, Carl can sit next to Anna or next to Bob. They form a block of three people, so we have eight objects to arrange, the block with Anna, Bob, and Carl and the other seven people. The eight objects can be arranged in a circle in $7!$ distinguishable ways. Thus, there are $2 \cdot 2! \cdot 7!$ such seating arrangements.
Hence, the number of seating arrangements in which Anna and Bob sit together but Carl sits separately is $$8!2! - 2 \cdot 2! \cdot 7! = 80,640 - 20,160 = 60,480$$
By symmetry, there are also $60,480$ seating arrangements in which Anna and Carl sit together but Bob sits separately and $60,480$ seating arrangements in which Bob and Carl sit together but Anna sits separately.
Consequently, the number of seating arrangements in which two or more of Anna, Bob, and Carl sit in adjacent seats is $$3(8!2! - 2 \cdot 2! \cdot 7!) + 3 \cdot 7!2! = 3 \cdot 60,480 + 30,240 = 181,440 + 30,240 = 211,680$$ Hence, the number of admissible seating arrangements is $$9! - 3(8!2! - 2 \cdot 2! \cdot 7!) - 3 \cdot 7!2! = 362,880 - 211,680 = 151,200$$ in agreement with the two methods shown above.