1
$\begingroup$

N people are to be seated in a row. A, B, C, and D cannot sit next to each other*. How many arrangements are there? * No two of them can be adjacent

I thought I would first calculate all cases in which two of them are adjacent and tried to use the inclusion-exclusion principle to do so. So my first case was when two of the four are together Case 1: $$\binom{4}{2}*2*(n-1)!$$ When 3 of them are together Case 2: $$\binom{4}{3}*3!*(n-2)!$$ When 4 of them are together Case 3: $$4!*(n-3)!$$ and then I thought it would be Case 1 - Case 2 + Case 3 but I believe I am overcounting by this. Apologies for any mistakes, I'm new to StackExchange and still getting used to its workings

$\endgroup$
  • $\begingroup$ Welcome to MathSE. When you pose a question here, it is expected that you include your own thoughts on the problem. Please edit your question to show what you have attempted and explain where you are stuck so that you receive responses that address the specific difficulties you are encountering. This tutorial explains how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig May 26 at 20:14
  • $\begingroup$ You seem to be trying to count the number of seating arrangements in which at least two of the four people are seated together. In doing so, you overlooked the case in which there are two pairs of adjacent people. However, what you want to count is the number of arrangements in which no two them are adjacent. $\endgroup$ – N. F. Taussig May 26 at 21:06
1
$\begingroup$

Method 1: Arrange other $n - 4$ people in a row, which can be done in $(n - 4)!$ ways. This creates $n - 3$ spaces in which we can place $A$, $B$, $C$, and $D$, $n - 5$ between successive people and two at the ends of the row.

To illustrate what I am saying, suppose $n = 10$. Then there are $10 - 4 = 6$ people other than $A$, $B$, $C$, and $D$. $$\square P \square P \square P \square P \square P \square P \square$$ Each $P$ represents the position of one of those six people. Each of the $10 - 3 = 7$ squares represents a place where person $A$, $B$, $C$, and $D$ could be placed.

To separate $A$, $B$, $C$, and $D$, we must choose four of these $n - 3$ spaces in which to place $A$, $B$, $C$, and $D$. We can arrange $A$, $B$, $C$, and $D$ in these spaces in $4!$ ways. Hence, the number of arrangements of the $n$ people in a row so that no two of $A$, $B$, $C$, and $D$ are adjacent is $$(n - 4)!\binom{n - 3}{4}4!$$

Method 2: We use the Inclusion-Exclusion Principle.

There are $n!$ arrangements of $n$ people in a row. From these, we must subtract those arrangements in which two or more of the four people are adjacent.

A pair of the four people are adjacent: There are $\binom{4}{2}$ ways to select two of the four people to be in the pair. We then have $n - 1$ objects to arrange, the pair and the other $n - 2$ people. The objects can be arranged in $(n - 1)!$ ways. The two people can be arranged in $2!$ ways. Hence, there are $$\binom{4}{2}(n - 1)!2!$$ such arrangements, as you found.

Two pairs of people are adjacent: This can occur in two ways. Either the pairs are overlapping or they are separate.

Two overlapping pairs: This means that three of the four people are consecutive. Choose which three of the four are consecutive in $\binom{4}{3}$ ways. We now have $n - 2$ objects to arrange, the block of three people and the remaining $n - 3$ people. The objects can be arranged in $(n - 2)!$ ways. The three people can be arranged within the block in $3!$ ways, as you found. Hence, there are $$\binom{4}{3}(n - 2)!3!$$ such arrangements, as you found.

Two separate pairs: There are three ways to choose whether $B$, $C$, or $D$ is paired with $A$. We then have $n - 2$ objects to arrange, the pair containing $A$, the pair not containing $A$, and the other $n - 4$ people. The objects can be arranged in $(n - 4)!$ ways. The pairs can each be arranged in $2!$ ways. Hence, there are $$3(n - 2)!2!2!$$ such arrangements.

This is the case you omitted.

Three pairs of adjacent people: This can only occur if the four people are all consecutive. We now have $n - 3$ objects to arrange, the block of four people and the other $n - 4$ people. The objects can be arranged in $(n - 3)!$ ways. The four people can be arranged within the block in $4!$ ways. Hence, there are $$(n - 3)!4!$$ such arrangements, as you found.

By the Inclusion-Exclusion Principle, the number of admissible arrangements is $$n! - \binom{4}{2}(n - 1)!2! + 3(n - 2)!2!2! + \binom{4}{3}(n - 2)!3! - (n - 3)!4!$$

$\endgroup$
  • $\begingroup$ I decided to add an additional method of solution using the Inclusion-Exclusion Principle. $\endgroup$ – N. F. Taussig May 26 at 21:33

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.