How many ways to arrange people on a bench so that no woman sits next to another woman? 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.
 A: 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?
A: 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. 
