Two persons should not sit next to each other in a row of $n$.

combinatorics

I tried an alternate approach to the one given in the book by K.D.Joshi, titled 'Foundations of Discrete Math.', there is given on page#94, for the above problem.

The book states that taking the two persons (who shouldn't sit next to each other) as a single entity, there are $n-2$ persons left. The combined entity of $n-1$ persons can be arranged in $(n-1)!$ ways. Also, the two persons can be arranged in $2!$ ways, leading to a total of $(n-1)!\cdot 2$ ways. These need be subtracted from $n!$ ways possible, to get the desired answer of $n! – 2(n-1)!$.


My failed alternate approach:
Take the possible choices to fit in first person as $n$, then second one has two choices depending on the location of the first person.
(i) if the first person is not at corner, then $(n-3)$ choices,
(ii) else, $(n-2)$ choices.

In the both cases, the other $(n-2)$ persons have $(n-2)!$ choices.

I feel need apply 'sum rule' here, as that is done for mutually exclusive cases, which they are; i.e. if case (i) occurs then case (ii) wouldn't, & vice-versa.

So, $n\cdot (n-3)\cdot (n-2)! + n\cdot (n-2)\cdot (n-2)! = n\cdot (2n-5)\cdot (n-2)!$ choices are available.

But, this is not the same as the correct answer of $n! – 2(n-1)!$.

Best Answer

Break into cases:

  • First person of our pair of troublemakers sits at a corner

    • pick which corner ($2$ options)
    • pick where the other troublemaker sits ($n-2$ options)
    • pick how the other people sit ($(n-2)!$ options)
  • First person of our pair of troublemakers doesn't sit at a corner

    • pick which center seat ($n-2$ options)
    • pick where the other troublemaker sits ($n-3$ options)
    • pick how the other people sit ($(n-2)!$ options)

This gives a total of

$$\color{red}{2}(n-2)(n-2)! + \color{red}{(n-2)}(n-3)(n-2)!$$

You mistakenly used $n$ for the above red numbers instead of $2$ and $n-2$ respectively.

This of course is equal to $n!-2(n-2)!$, as expected, as can be shown through algebraic manipulation.