# Seating men and women combinatorics problem

Consider $n$ seats in which $k$ distinct men and $m$ distinct women are going to be seated ($n \ge \max \{m+k,2k\}$). In how many ways is this possible given that no two men sit next to each other?

My approach is the following:

First seat the $k$ distinct men in $k!$ different ways. Then you need to distribute the remaining $n-k$ seats between them which give rise to the following linear equation for the empty seats:

$$x_1 + x_2 + \dots + x_{k+1} = n - k \\ x_1,x_{k+1} \ge 0 \quad x_i \ge 1 \; \forall i \ne 1, k+1$$

which has $|X| = C(n-k+1, k)$ integer solutions. Then we need to seat the $m$ distinct women (which can be arranged in $m!$ different ways) in the empty seats made possible by the men. That leads to the linear equation:

$$y_1 +y_2 + \dots + y_{k+1} = m \\ y_i \le x_i$$ By letting $z_i = x_i - y_i \ge 0$ the equation becomes

$$\sum_{i=1}^{k+1} (x_i - z_i) = m \iff \sum_{i=1}^{k+1} z_i = n -k - m \\ z_i \ge 0$$

Which has $|Y| = C(n-m, n - k - m)$ solutions.

So the final result is given

$$k!m!|X||Y| = k! m! C(n-k,n-k-m)C(n-k+1, k) = \frac {(n-k+1)!(n-k)!}{(n-2k + 1)!(n-k-m)!}$$

Am I right?

• Your solution certainly works in the extreme cases that $n = 2k$ and $n = m + k$. – N. F. Taussig Jul 9 '17 at 10:19
• Give an explanation, please – bolzano Jul 9 '17 at 11:32

I'll change the notation slightly, m for men and w for women.

Take an unnumbered row of (n-m) seats, which have (n-m+1) "gaps" (including the ends), where seats for men can be put in $\binom{n-m+1}{m}$ ways.

Place the women in $\binom{n-m}{w}$ ways in vacant seats, and now number the seats.

Since the men have been placed in non-adjacent seats, they can't be "next to each other", they are "next to" to women / vacant seats

Now people are distinct, so taking this into account and putting together the pieces, we get $m!w!\binom{n-m+1}{m}\binom{n-m}{w}$

which simplifies to the expression you got ! Bully for you !

• This is a clever solution. However, it took me a while to realize you were placing men next to locations to be filled by women or empty seats. – N. F. Taussig Jul 9 '17 at 12:01
• @N.F. Taussig: I am adding a line for greater lucidity. – true blue anil Jul 9 '17 at 14:22

Your solution is correct, as true blue anil's elegant alternative solution shows.

As a sanity check, let's verify the extreme case: $n = m + k$, with $m \geq k$

We can arrange $m$ women in $m!$ ways. This creates $m + 1$ gaps, $m - 1$ between successive women and two at the ends of the row. To ensure no two men sit in adjacent seats, we choose $k$ of these $m + 1$ gaps for the men. The men can be arranged in the selected seats in $k!$ ways. Hence, when $n = m + k$, the number of permissible seating arrangements is $$k!m!\binom{m + 1}{k}$$ Substituting $m + k$ for $n$ in your formula $$k!m!\binom{n - k}{n - k - m}\binom{n - k + 1}{k}$$ yields $$k!m!\binom{m + k - k}{m + k - k - m}\binom{m + k - k + 1}{k} = k!m!\binom{m}{0}\binom{m + 1}{k} = k!m!\binom{m + 1}{k}$$ as expected.