For dinner, $n$ people came and sat at a round table at random. If Ana, Ivan and Mark were among them, how many ways could they sit so ...

Question

Problem:

For dinner, $n$ ($n \geq 4$) people came and sat at a round table at random. If Ana, Ivan and Mark were among them, how many ways could they sit so that Ana and Ivan do not sit next to each other and at least one of them sits next to Mark? (Note: the round table implies seating arrangements that differ only in rotation.)

My attempt:
If I have $n$ people sitting around circular table, the number of different arrangements are $(n-1)!$.
If I have $2$ people Mark and Ana number of arrangements that they can sit next to each other is $2 \cdot (n-2)!$. So the number of arrangements that Mark sit next to Ivan is also $2 \cdot (n-2)!$, and sitting next to Ana also $2 \cdot (n-2)!$.

That all I know about this problem.

Answer 1

Method 1: Seat Mark. We will use him as our reference point.

Only Ana sits next to Mark: She can be seated in two ways, to his left or to his right. That leaves $n - 2$ seats. Since Ivan cannot sit next to Ana or Mark, he may be seated in $n - 4$ ways. The remaining $n - 3$ people can be seated in the remaining $n - 3$ seats in $(n - 3)!$ ways as we proceed clockwise around the table relative to Mark. Hence, there are $2(n - 4)(n - 3)!$ such arrangements.

Only Ivan sits next to Mark: By symmetry, there are $2(n - 4)(n - 3)!$ such arrangements.

Both Ana and Ivan sit next to Mark: There are two ways to seat Ana, to Mark's left or to his right. Ivan must sit on the other side of Mark. The remaining $n - 3$ people may be seated in the remaining $n - 3$ seats in $(n - 3)!$ ways as we proceed clockwise around the table relative to Mark. Hence, there are $2(n - 3)!$ such seating arrangements.

Total: Since the three cases are mutually exclusive and exhaustive, the number of admissible seating arrangements is \begin{align*} 2(n - 4)(n - 3)! + 2(n - 4)(n - 3)! + 2(n - 3)! & = [4(n - 4) + 2](n - 3)!\\ & = (4n - 14)(n - 3)! \end{align*}

Method 2: Seat Mark. We will use him as our reference point.

Choose whether Ana or Ivan sits next to him. Choose on which side of Mark that person sits. Seat the remaining $n - 2$ people as we proceed clockwise around the circle relative to Mark. This gives $$2 \cdot 2 \cdot (n - 2)! = 4(n - 2)!$$ seating arrangements.

From these, we must subtract those arrangements in which Ana and Ivan sit next to each other. For this to happen, they must both sit on the same side of Mark. Choose which of them sits next to Mark. Choose on which side of Mark that person sits. If that person is Ana, there is only one way to seat Ivan next to her since Mark is on her other side. Similarly, if Ivan sits next to Mark, there is only one way to seat Ana next to Ivan since Mark is on his other side. Once those three seats have been filled, seat the remaining $n - 3$ people in the remaining $n - 3$ seats as we proceed clockwise around the table. There are $$2 \cdot 2 \cdot (n - 3)! = 4(n - 3)!$$ such seating arrangements.

We must also subtract those seating arrangements in which both Ana and Ivan sit next to Mark since we have counted them twice in our initial count, once when we designated Ana as the person who sits next to Mark and once when we counted Ivan as the person who sits next to Mark. As we showed above, there are $$2(n - 3)!$$ seating arrangements in which both Ana and Ivan sit next to Mark.

Hence, the number of admissible seating arrangements is $$4(n - 2)! - 4(n - 3)! - 2(n - 3)! = [4(n - 2) - 4 - 2](n - 3)! = (4n - 14)(n - 3)!$$

Answer 2

First consider just the arrangements of A,M and I.

There are $2$ arrangements for all three to be together since M must be in the middle.

There are $4(n-4)$ arrangements for just two to be together since we choose one of A and I to be on one or other side of M and then place the third of them in one of $n-4$ seats.

We therefore have $4n-14$ arrangements for the named people and for each of these arrangements there are $(n-3)!$ arrangements of the remaining guests; a total of $(4n-14)(n-3)!$ arrangements.

Answer 3

The types of possibilities for Ana, Mark, Ivan, and $n-3$ empty chairs can be written as

1. $AMI-$
2. $IMA-$
3. $AM-I-$
4. $MA-I-$
5. $IM-A-$
6. $MI-A-$,

where $-$ indicates a row of at least one chair. Each configuration corresponds to $(n-3)!$ seatings, accounting for the placement of the remaining $n-3$ people in chairs. 1. and 2. are unique configurations (the row of chairs has length $n-3$); the remaining items correspond to $n-4$ configurations each, since the length of the first row of chairs can be $1,2,\ldots,n-4$. So the total is $$ (n-3)!\cdot(2 + 4\cdot(n-4)) = (4n-14)(n-3)! $$

Answer 4

Let $A$ represent the number of seating arrangements when either Ana is next to Mark or Ivan is next to Mark, but not both. If $n \ge 5$ it is not difficult to show that

$\tag 1 A = 4 (n-3) (n-4) \,(n-4)!$

The factor of $4 = 2 \times 2$ is obtained by doubling for the Ana/Ivan interchange and the left/right interchange. The remaining $n - 2$ factors result from applying the rule of product while seating the remaining $n - 2$ people (the last person seated corresponds to a factor of $1$). But $A = 0$ when $n = 4$ and so $\text{(1)}$ also supplies the correct count for $n \ge 4$.

Let $B$ represent the number of seating arrangements when both Ana and Ivan are next to Mark. It is not difficult to show that

$\tag 2 B = 2 \,(n-3)!$

The factor of $2$ is obtained by doubling for the Ana/Ivan interchange which also incorporates, at the same time, the left/right interchange. Again, we seat each of the remaining people while using the rule of product.

Employing algebra we compute

$\tag 3 A + B = (4n - 14) \, (n - 3)!$

Compare the above technique to N. F. Taussig's Method 1 (a slight difference).

Answer 5

We can also find the answer using recursive techniques.

This problem only has solutions when $n \ge 4$. For $n \ge 4$ define

$\quad A(n) = \text{the number of solutions where Mark IS NOT next to BOTH Ana and Ivan.}$

$\quad B(n) = \text{the number of solutions where Mark ---IS---- next to BOTH Ana and Ivan.}$

We want to find the sum $C(n) = A(n) + B(n)$.

We can insist that our seating counting algorithm is accomplished by seating a single person at a time to the existing multiplicity of seating arrangements as they 'arrive'. Also, the first three people to arrive are Mark, Ana and Ivan.

So when the fourth person arrives we have

$\quad A(4) = 0 \text{ and } B(4) = 2$

seating arrangements.

Suppose we have a list of all the seating arrangements for $n$ people, and now we have to seat the next $(n+1)^{\text{th}}$ person. Using combinatorial/counting arguments, it can be demonstrated that

$\tag A A(n+1) = (n-1)A(n) + 4B(n)$

and

$\tag B B(n+1) = (n-2) B(n)$

---

A fun thing about combinatorial problems is they can often be solved in several ways, and then you can confirm the answer when the different solutions give the same result. The interested reader can work on the following:

Exercise: Using inductin, show that the recursive model discussed here gives the same results as the the seating arrangement methods found in this answer.

---

It is also possible to derive the closed formula answer starting with this recursion model - see this.