Question

Suppose men and $n$ women are to be seated in a row so that no two women sit together. If $m\ \textgreater \ n$, show that the number of ways in which they can be seated is: $\frac{m!(m+1)!}{(m-n+1)!}$

Answer 1

Firstly, we'll fix the postions where the $n$ women will be. We have $n!$ forms to do that. So, we'll obtain a row like:

$\underbrace{\underline{~~~}}_{x_2}W_2 \underbrace{\underline{~~~}}_{x_3}W_3 \underbrace{\underline{~~~}}_{x_4}... \underbrace{\underline{~~~}}_{x_n}W_n \underbrace{\underline{~~~}}_{x_{n+1}}$

The n+1 spaces represented by the underline positions will receive the men of the row. Then,

$x_1+x_2+x_3+...+x_{n-1}+x_n+x_{n+1}=m~~~(i)$

Since there is no women sitting together, we must write that $x_2,x_3,...,x_{n-1},x_n\ge1$. It guarantees that there is at least one man between two consecutive women. We'll do some substitutions:

$\begin{cases}x_2=x_2'+1\\x_3=x_3'+1\\...\\x_{n-1}=x_{n-1}'+1\\x_n=x_n'+1\end{cases}$

The equation (i) can be rewritten as:

$x_1+x_2+x_3+...+x_{n-1}+x_n+x_{n+1}=m\\\\ x_1+(x_2'+1)+(x_3'+1)+...+(x_{n-1}'+1)+x_n+x_{n+1}=m\\\\ x_1+x_2'+x_3'+...+x_{n-1}'+x_n+x_{n+1}=m-(n-1)\\\\ x_1+x_2'+x_3'+...+x_{n-1}'+x_n+x_{n+1}=m-n+1~~~(ii)$

We obtained a linear problem of non-negative integer solutions in (ii). The number of solutions to this type of problem are known: $\dfrac{[(n)+(m-n+1)]!}{(n)!(m-n+1)!}=\dfrac{(m+1)!}{n!(m-n+1)!}$

[I can write the proof if you want]

Now, we just have to calculate the number of forms to permute the men that are dispposed in the row: $m!$

Multiplying all results:

$n!\times\dfrac{(m+1)!}{n!(m-n+1)!}\times m!\\\\ \boxed{\boxed{\dfrac{m!(m+1)!}{(m-n+1)!}}}$