# Given a group of 5 women and 4 men, how many different combinations of them exist where all 4 men are kept separate?

Sorry to have to ask such an elementary question, but I’ve been struggling with this for about half an hour or so to no avail. The problem in question is:

Given a group of 5 women and 4 men, how many different combinations of them exist where all 4 men are kept separate?

When approaching the problem initially, I saw there were $4!$ ways of arranging the 4 men, and $5!$ ways of arranging the women; since there are 5 different spots between the men where the women could stand, this (I thought incorrectly) would lead to an extra three different combinations by varying the position of the fifth woman. This gave me an answer of $$3 \times 4! \times 5!=8640,$$ which is wrong.

Next I took a more thorough approach, first starting by again observing that the four men can be arranged in $4!$ different ways; I then looked at the different arrangements of the five women. If they inhabit only the middle three spaces between the men, then I reasoned that there would be $${}^5C_2 \times {}^3C_2$$ ways of arranging them (as you choose two from the five for the first space, two from three for the second space, and only have one left for the final space — it now occurs to me that I missed the possibility where three are in one space and one in each other). If they take four of the five spaces (which must include the middle three so they men remain separated), then there are: $$2\times \left({}^5C_3 \times 3!\right)$$ ways of arranging them, as we choose three of five to go in each of the middle spaces, then have $3!$ ways of arranging them (I again notice now I’ve missed some possibilities). This is all multiplied by $2$ as they could be in slots $1,2,3,4$ or $2,3,4,5$. Finally, if they inhabit all five slots, there are $$5!$$ ways of arranging them.

When I put this all together, I got: $$4! \times \left(\left({}^5C_2 \times {}^3C_2\right)+\left(2\times \left({}^5C_3 \times 3!\right)\right)+5!\right)=7920$$ which is again, infuriatingly, wrong.

According to the textbook the correct answer is $43200$.

I’m aware this sounds like a ‘do it for me’ question (because it kind of is), but I’ve really tried my best with it and am clearly from struggling from some lapse of understanding. Any help is greatly appreciated! :)

• There is only one partition of the group where all of the men will be separate. – Doug M Jan 22 '18 at 22:23
• Of course we are speaking of arranging the people along a linear row. Then the fundamental point is : are you distinguishing only by gender ? or ,also, by (say) the name ? – G Cab Jan 22 '18 at 22:24
• I don’t think so; you could have MWMWWMWMW or WWMWMWMWM, both of which are different, which doesn’t even take into account the different orders the different men/women could be arranged in – aidangallagher4 Jan 22 '18 at 22:26
• @GCab sorry this probably needs clarification; they are differentiated by gender and name (ie no male or female can be taken to be the same — like in life! ;) ) – aidangallagher4 Jan 22 '18 at 22:27

The five women can be arranged in a row in $5!$ ways. This creates six spaces where we can place the men, four between successive women and two at the ends of the row. $$\square w \square w \square w \square w \square w \square$$ To separate the men, we must choose four of these spaces in which to place a man, which can be done in $\binom{6}{4}$ ways. The men can be arranged in the chosen spaces in $4!$ ways. Hence, there are $$5!\binom{6}{4}4!$$ arrangements in which the men are separated.
There must be at least one woman to fill between any two adjacent men. Take $x_1$ as the number of women filling between men 1 and 2, $x_2$ and $x_3$ as the number of women filling between men 2 and 3 and 3 and 4 respectively and x any y as number of remaining women. Then we must find the number of answers of the equation $x_1+x_2+x_3+x+y=5$ with respect to $x_1,x_2,x_3\ge 1$. There are exactly $\binom{5+1-2}{2}=15$ such answers there altogether each contributing 5! different cases. This combinatorial attitude can be used also for men which gives us 4! different cases and 15$\times$4!$\times$5!=43200 in general.
• I suggest specifying that $x$ is the number of women to the left of the first man and that $y$ is the number of women to the right of the last man. – N. F. Taussig Jan 22 '18 at 23:01