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

Question

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.

Answer 1

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$$

Answer 2

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$.