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