1
$\begingroup$

There are $12$ women and $12$ men. How many ways are there to sit them all on a bench where no woman can sit next to another woman?

Thank you.

$\endgroup$

closed as off-topic by Harish Chandra Rajpoot, user296602, Chris Godsil, colormegone, Leucippus Jan 31 '16 at 0:10

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Harish Chandra Rajpoot, Community, Chris Godsil, colormegone, Leucippus
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ Welcome to MSE! Can you share what you've tried and what you're having trouble with? $\endgroup$ – user296602 Jan 30 '16 at 17:53
  • 1
    $\begingroup$ @T.Bongers thanks! I thought it is 12!12!*2, but the answer should be 12!*13! $\endgroup$ – liam Jan 30 '16 at 18:00
  • 2
    $\begingroup$ You should include your attempt in the statement of your question rather than in the comments. $\endgroup$ – N. F. Taussig Jan 30 '16 at 18:27
  • 2
    $\begingroup$ @liam the answer of $12! 12! 2$ assumes only arrangements of alternating men and women, such as mwmwmwmw... or wmwmwmwm... However, there are more possibilities such as wmwmmwm... or wmmwmwm... etc that you miss with that count. $\endgroup$ – JMoravitz Jan 30 '16 at 19:32
3
$\begingroup$

Big Hint:

The phrase "no woman can sit next to another woman" can be instead interpreted as "every woman has a man or empty space to each side of her."

If you were to completely ignore the women for the time being, you can first seat the men. After the men have been seated, you may seat the women inbetween the men or outside of the men.


Worded another way, suppose you have chairs that are labeled blue for men, or red for women.

They are arranged $\color{red}{O}\color{blue}{O}\color{red}{O}\color{blue}{O}\dots\color{red}{O}\color{blue}{O}\color{red}{O}$

The blue chairs are reserved for the men and the red chairs are reserved for the women. In how many ways may the men sit in the blue chairs? In how many ways may the women sit in the red chairs? If we remove the extra chair and maintain that order and have them sit on the bench instead, does this satisfy our requirements? Are there the same number of ways to have them sit in these chairs as there are for them to sit on the bench?

$\endgroup$
1
$\begingroup$

If there are 12 men and 12 women answer is $12!13!$. More generally, if there are $m$ men and $n$ women with $m\geq n$ and no two women can sit together, the answer is $$\frac{m!(m+1)!}{(m-n+1)!}$$ This can be understood as follows: the $m$ men can sit in $m!$ ways. In each one of these permutations, there are $m+1$ places available for women. Since $m\geq n$ implies $m+1>n$, the $n$ women can be seated in $\frac{(m+1)!}{(m+1-n)!}$ different ways in the $m+1$ places.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.