An A-level Permutation Problem

Question

Find the number of ways in which $n$ boys and $n$ girls ($n>1$) can be seated in a row of seats if the boys and the girls are to have alternate seats and one particular boy and one particular girl must not sit next to each other.

P.S.: Official A-level Pure Maths (1969) Answer is $2(2(n!)-1-2(n-1))$ but my answer is $2((n!)^2-1-2(n-1))$, what's wrong here?

After my deep thought, the official answer makes no sense to me. However, my answer is $2((n!)^2-(n-1)-2(n-1)(n-1)^2)$. Simply listing all possible permutation, which has $(n!)^2$ ways, and cancels those where the boy and the girl sitting next to each other, which has $(n-1)+2(n-1)^3$ ways.

Answer 1

(Total no of cases) minus (cases boy 1 and girl 1 are together)

$=2 (n!)^2 - \text{($n-1$ girls and $n-1$ boys seat alternatively)} \times (2n-1)$ [As there are $2n-1$ gaps, and in each, boy $1$ and girl $1$ can only be fitted in $1$ way so that boys and girls sit alternatively]

$= 2(n!)^2 - 2{(n-1)!}^2 \times (2n-1)$

$= 2{(n-1)!}^2 [ n^2 - 2n +1]$

I may be wrong but i think u should check the answer again

Answer 2

The answer by @aryanbansal is correct. Here are some comments on the wrong answers, and an alternative derivation of the correct answer.

(1) The "official" answer is clearly wrong because the correct answer has to grow almost as $n!^2$.

(2) The OP's answers are also wrong because the number of eliminated cases has to include permutations of the other $(n-1)$ boys and the other $(n-1)$ girls, so the term to be subtracted from $2(n!)^2$ must have something like $(n-1)!^2$ (or something that grows almost like that). The term to be subtracted cannot simply be a quadratic or cubic in $n$. Any logic that results in a simple low-degree polynomial is most likely reasoning about fractions, or probabilities, like in...

(3) Re-derivation: There are $2(n!)^2$ arrangements where boys and girls sit alternately. Suppose each of these is equally probable. What is the prob of $E=$ event that boy $1$ and girl $1$ would be next to each other?

Let $A =$ event that boy $1$ is at either end of the row, and $A^c$ be the complement (i.e. he is in the middle). We have:

• $P(E) = P(E \mid A) P(A) + P(E \mid A^c) P(A^c)$

• $P(A) = {2 \over 2n} = \frac1n, P(A^c) = 1 - P(A) = {n-1 \over n}$

• $P(E\mid A) = \frac1n$ because there is only one "girl seat" next to boy $1$

• $P(E \mid A^c) = \frac2n$ for similar reason

Putting everything together:

$$P(E) = \frac1n \frac1n + {n-1\over n} \frac2n = {1 + 2n-2 \over n^2} = {2n -1 \over n^2}$$

So the number of arrangements when $E$ does not happen is:

$$(n!)^2 (1 - P(E)) = (n!)^2 {n^2 - 2n + 1 \over n^2} = (n-1)!^2 (n^2 - 2n + 1)$$

agreeing with @aryanbansal