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?

  • $\begingroup$ Your solution certainly works in the extreme cases that $n = 2k$ and $n = m + k$. $\endgroup$ – N. F. Taussig Jul 9 '17 at 10:19
  • $\begingroup$ Give an explanation, please $\endgroup$ – 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 !

  • $\begingroup$ 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. $\endgroup$ – N. F. Taussig Jul 9 '17 at 12:01
  • 1
    $\begingroup$ @N.F. Taussig: I am adding a line for greater lucidity. $\endgroup$ – 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.


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.