2
$\begingroup$

Question: How many ways there are to sit h men, m women in a circular table with n chairs in a way that no woman is going to be sit next to other woman?


The objective of this post: I would like for someone to check if what I've done, including my reasoning, is correct. If it is, I'd like to know if there is an easier solution. If it's not, I'd like to know what is my mistake. Thank you:


My answer:

I started thinking about the cases:

First I thought about what would be the answer if $n<h+m$. There would be no answer since at least a man or a woman wouldn't sit.

Next I thought about the case where $n=h+m$. That is easy and I used the following strategy:

1) In the beginning, each seat is the same, so you sit any woman to differ the seats.

2) After the first woman has seated, then each seat is different, so you sit the remaining women: $(m-1)!$.

3) Now we just need to separate woman by sitting men between them. We use stars and bars method to get all the possibilities of how many men are going to be between each woman: ${h-1 \choose m-1}$.

4) Then we create a line of men and tell them to sit according to the past result. Hence the answer is: $(m-1)!\cdot {h-1 \choose m-1} \cdot h!$

Next I thought about the cases where $n>h+m$. That case only differs from the previous one because there are more chairs, so an answer, which is a sequence, would differ because of where those extras chairs are positioned... Hence I used a similar strategy:

1) In the beginning each seat is the same, so you sit any woman to differ the seats.

2) After the first woman has seated, then each seat is different, so you sit the remaining women: $(m-1)!$.

3) Now, instead of sitting the men, we're going to position chairs between each woman using stars and bars method. There are $n-m$ remaining seats that we want to position between each woman in a circular table, hence: ${n-m-1 \choose m-1}$.

4) Finally, we make each men choice a remaining seat to sit: $P_{h}^{n-m}$.

5) Therefore, the result is:$(m-1)!\cdot{n-m-1\choose m-1}\cdot P_{h}^{n-m}$.


EDIT:

The reason for this edit is that I noticed that N. F. Taussig answer and the one that I gave are actually the same!

Let's introduce the same change of variables. Let n be the number of seats; let m be the number of men; let w be the number of women.

First case:

My answer: $$ \begin{align*} (w-1)!\cdot {m-1 \choose w-1} \cdot m! &= \frac{(w-1)!(m-1)!(m!)}{(w-1)!(m-w)!}\\ &=\frac{(m-1)!(m!)}{(m-w)!} \end{align*} $$

N. F. Taussig answer's:

$$ \begin{align*} (m - 1)!\binom{m}{w}w! &= \frac{(m-1)!(m!)(w!)}{w!(m-w)!}\\ &= \frac{(m-1)!(m!)}{(m-w)!} \end{align*} $$

Second Case:

My answer: $$ \begin{align*} (w-1)!\cdot{n-w-1\choose w-1}\cdot P_{m}^{n-w} &= \frac{(w-1)!(n-w-1)!(n-w)!}{(w-1)!(n-2w)!(n-w-m)!}\\ &=\frac{(n-w-1)!(n-w)!}{(n-2w)!(n-w-m)!} \end{align*} $$

N. F. Taussig answer's:

$$ \begin{align*} \binom{n - w - 1}{m - 1}(m - 1)!\binom{n - w}{w}w! &= \frac{(n-w-1)!(m-1)!(n-w)!w!}{(m-1)!(n-w-m)!w!(n-2w)!}\\ &= \frac{(n-w-1)!(n-w)!}{(n-w-m)!(n-2w)!}\\ \end{align*} $$


Anyway, thank you for answering N. F. Taussig!


Any help, comments, and answers are highly appreciated.

Thank you for your time and support!

$\endgroup$
  • $\begingroup$ If there is an empty seat between two women, do you consider the women to be sitting next to each other? $\endgroup$ – N. F. Taussig Sep 22 '18 at 21:41
  • 1
    $\begingroup$ @N.F.Taussig No, a seat separates two women just as a man would do. $\endgroup$ – Bruno Reis Sep 22 '18 at 21:43
1
$\begingroup$

Let's introduce a change of variables. Let $n$ be the number of seats; let $m$ be the number of men; let $w$ be the number of women.

As you observed, the problem only has a solution if $n \geq m + w$.

Case 1: $n = m + w$

Since the women must be separated by the men, there must be at least as many men as women, so we require that $m \geq w$.

Hand each person a chair. Suppose Andrew is one of the $m$ men. Seat him first. The other men can be seated around the table in $(m - 1)!$ ways as we proceed clockwise around the table from Andrew. Seating the $m$ men creates $m$ spaces in which we can place a woman. To separate the women, we must choose $w$ of those $m$ spaces, which can be done in $\binom{m}{w}$ ways. The women can be arranged in those $w$ spaces in $w!$ ways as we proceed clockwise around the table from Andrew. Hence, there are $$(m - 1)!\binom{m}{w}w!$$ seating arrangements in which no two of the women are adjacent.

Case 2: $n \geq m + w$

Since the women must be separated by the men or by an empty seat, we require that $w \leq \left\lfloor \dfrac{n}{2} \right\rfloor$.

Place $n - w$ chairs at the table. Place Andrew in one of them (it does not matter which one since we will use Andrew as our reference point). That leaves $n - w - 1$ seats where the remaining $m - 1$ men can be seated. Choose $m - 1$ of these $n - w - 1$ seats for the men, which can be done in $\binom{n - w - 1}{m - 1}$ ways. The men can be arranged in these seats in $(m - 1)!$ ways as we proceed clockwise around the table from Andrew. Hand each woman a chair. We now have $n - w$ spaces in which a woman can be placed, one to the left of each of the $n - w$ chairs at the table. To separate the women, choose $w$ of these spaces, which can be done in $\binom{n - w}{w}$ ways. The women can be arranged in these chosen spaces in $w!$ ways as we proceed clockwise around the table from Andrew. Hence, there are $$\binom{n - w - 1}{m - 1}(m - 1)!\binom{n - w}{w}w!$$ seating arrangements in which no two of the women are adjacent.

As a check, observe that if $m + w = n$, then our formula reduces to $$\binom{m + w - w - 1}{m - 1}(m - 1)!\binom{m + w - w}{w}w! = \binom{m - 1}{m - 1}(m - 1)!\binom{m}{w}w! = (m - 1)!\binom{m}{w}w!$$

$\endgroup$
  • 1
    $\begingroup$ Thank you for answering, but please, check the edit :). Ty anyway! $\endgroup$ – Bruno Reis Sep 22 '18 at 22:58

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.