2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$). $\endgroup$ Nov 30, 2019 at 17:23

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ thank you so much for such a beautiful answer! $\endgroup$ Nov 30, 2019 at 18:06
0
$\begingroup$

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

$\endgroup$

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.