# How many seating arrangements of $m$ people in a row of $n$ seats are there if $k$ of the people must sit together?

Suppose there are five people $$A, B, C, D, E$$ to be seated in a row of eight seats $$S_1, \ldots, S_8$$.

(1) How many possibilities are there if $$A$$ and $$B$$ are to sit next to each other?

(2) How many possibilities are there if $$A$$ and $$B$$ are not to sit next to each other?

My Attempt:

First Approach:

There are $$8$$ options of a seat for $$A$$. However, if $$A$$ is to be seated in $$S_1$$ or $$S_8$$, then $$B$$ can only be seated in $$S_2$$ or $$S_7$$, respectively. On the other hand, if $$A$$ is to be seated in any one of $$S_2$$ through $$S_7$$, then $$B$$ has two options of seat in each case.

Once $$A$$ and $$B$$ have been seated, there are $$6$$ seats left for $$C$$, and then $$5$$ seats left for $$D$$, and finally $$4$$ seats left for $$E$$.

In this way, the total number of seating arrangements are $$2 \times 1 \times 6 \times 5 \times 4 + 6 \times 2 \times 6 \times 5 \times 4 = 240 + 1440 = 1680.$$

Is this solution correct?

Second Approach:

Now let us treat $$A, B$$ as one entity. Then we have four entities to be accommodated in seven spots, for which there are $$7 \times 6 \times 5 \times 4 = 840$$ ways. And, each one of these $$840$$ arrangements, the members $$A$$ and $$B$$ of the block $$A, B$$ can be arranged within the block in two distinct ways. Therefore there are $$840 \times 2 = 1680$$ possible seating arrangements.

Is my answer correct? If so, then are both of my approaches also correct? If not, then where are the problems.

More generally, I have the following question:

Let $$k, m, n$$ be any natural numbers such that $$k \leq m \leq n$$. Then how many ways are there in total of seating $$m$$ people $$P_1 \ldots, P_m$$ in $$n$$ seats $$S_1, \ldots, S_n$$ such that some $$k$$ of these people insist on sitting next to each other?

My Attempt Using the Second Approach:

Let us treat that $$k$$ people as one block. Then there are

\begin{align} & (n-k+1) \underbrace{(n-k) (n-k-1) \ldots }_{(m-k) \mbox{ factors}} \\ &= (n-k+1) \big[ \ (n-k) (n-k-1) \ldots \big( (n-k) - (m-k-1) \big) \ \big] \\ &= (n-k+1)(n-k) \ldots (n-m+1) \\ &= ^{n-k+1}P_{n-m} . \end{align}

Finally, corresponding to each of the above arrangements with the $$k$$ people considered as one block, there are $$k!$$ ways of arranging the $$k$$ people within the block amongst themselves.

Hence there are a total of $$k! \ ^{n-k+1}P_{n-m}$$ ways of seating $$m$$ people in $$n$$ seats with $$k$$ people seated next to each other.

• The problem is not clearly stated until it is said which seats are next to each other. Among many possibilties two seem plausible: seats in a single row, or in a circle (in which case $S_1$ would be next to $S_8$). Nov 30, 2019 at 17:23

Both of your solutions to the first problem are correct. However, your general formula is not. Notice that in the first problem, $$n = 8$$, $$m = 5$$, and $$k = 2$$, so your formula gives $$2!P(8 - 2 + 1, 8 - 5) = 2!P(7, 3) = 2! \cdot 7 \cdot 6 \cdot 5 = 2 \cdot 210 = 420$$ Let's see what went wrong.

We wish to seat $$m$$ people, $$k$$ of whom must sit consecutively, in $$n$$ seats. Since the block takes up $$k$$ of the $$n$$ places, it must begin in one of the first $$n - (k - 1) = n - k + 1$$ positions. Once the block has been placed, there are $$n - k$$ seats left for the remaining $$m - k$$ people. They can be arranged in those seats in $$P(n - k, m - k)$$ ways. The people within the block can be arranged in $$k!$$ ways, which gives us the formula $$(n - k + 1)P(n - k, m - k)k!$$ As a sanity check, let's try our formula when $$n = 8$$, $$k = 2$$, and $$m = 5$$. It gives $$(8 - 2 + 1)P(8 - 2, 5 - 2)2! = 7 \cdot P(6, 3) \cdot 2! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 2 = 1680$$ which agrees with the answer you obtained in your example.

Observe that \begin{align*} (n - k + 1)P(n - k, m - k) & = (n - k + 1) \cdot \frac{(n - k)!}{[(n - k) - (m - k)]!}\\ & = \frac{(n - k + 1)(n - k)!}{(n - m)!}\\ & = \frac{(n - k + 1)!}{(n - m)!}\\ & = \frac{(n - k + 1)!}{[(n - k + 1) - (m - k + 1)]!}\\ & = P(n - k + 1, m - k + 1) \end{align*} so we could write our formula in the form $$P(n - k + 1, m - k + 1)k!$$ As a sanity check, note that if $$n = 8$$, $$k = 2$$, and $$m = 5$$, then $$P(8 - 2 + 1, 5 - 2 + 1)2! = P(7, 4)2! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 2 = 1680$$

• thank you so much for such a beautiful answer! Nov 30, 2019 at 18:06

For part $$a.)$$, we can work on two cases: $$AB$$ ($$A$$ to the left of $$B$$) and $$BA$$. The possibilities for $$AB$$ are $$S_{1}S_{2}, S_{2}S_{3}, …, S_{7}S_{8}$$. The possibilities for $$BA$$ are also the same. So the answer is
$$7 \times \binom{6}{3} \times 3! + 7 \times \binom{6}{3} \times 3! = 1680$$

The $$\binom{6}{3}$$ is the number of ways we can choose 3 seats, and $$3!$$ is number of possible orders of $$C,D,E$$ in the 3 seats.

For part $$b.)$$ count all possible seating without any rule, and then subtract with $$1680$$.