-1
$\begingroup$

I've looked other questions that might help solve my problem, but haven't found any people who've used my method to solve it. The problem goes like this: Suppose there are 7 men and 5 women, and they have to be seated around a circular table in such a way that no two women are seated together. Here's how i reason: We first choose 5 men. There are ${7\choose 5}$ ways of doing this. We then sit them at the table. There are $4!$ ways of doing this (since we divide by the number of rotations). Now we have to arrange the 5 women to sit between the men. There are $5!$ ways of doing this, once the 5 men are already seated. So far, we've seated 5 men and 5 women and haven't left two women seating together. Now, we are left with two men that are still standing, and here's were the tricky part comes: the 6th man has no restrictions to seat, and can seat between any pair of consecutive people who are already seated. So this man has 10 ways of doing such thing. Now, the 7th man, because of the same reasons, has 11 places to seat once the 6th man has seated (the 6th man creates a new possible place once he seats). So now, the number of total ways is $${7\choose 5} \cdot4! \cdot 5! \cdot10\cdot11$$ Ugh, i said "seated" and "ways" a lot of times. Sorry for the tediousness. Anyways, is my reasoning right?

$\endgroup$
1
$\begingroup$

Although less chivalrous, I'd seat the men first in 6! ways, insert 5 chairs for the women in the 7 gaps in ${7\choose5}$ ways, and seat the women in 5! ways.

$6!\cdot{7\choose 5}\cdot5! = 1814400$ ways

$\endgroup$
  • $\begingroup$ You just made my day better. $\endgroup$ – David Alexander Hulett Aug 2 '15 at 20:09
  • $\begingroup$ You're welcome ! :) $\endgroup$ – true blue anil Aug 2 '15 at 20:17
0
$\begingroup$

No, it's not right; you counted lots of configurations several times, because you could have chosen other groups of $5$ men and arrived at the same configuration. Also you can't easily correct for this overcounting, since depending on whether you added the two extra men in the same group of men or in two different groups of men, you overcounted by a factor or $4$ or $3$ respectively. You could sort that out with some bookkeeping, but this is more straightforward:

Seat the $5$ women, in $4!$ cyclically distinct ways. Put $5$ men's places between them, and distribute $2$ extra men's places over those $5$ "bins", in $\binom62=15$ different ways. Then distribute the men in $7!$ different ways over their $7$ seats, for a total of $4!\cdot15\cdot7!=1814400$ possibilities.

Note that this is $3\frac23$ times less than your count, consistent with the above argument that you overcounted some cases by a factor of $3$ and some by a factor of $4$.

$\endgroup$
  • $\begingroup$ Why $\dbinom 62$? $\endgroup$ – Bernard Aug 2 '15 at 0:13
  • $\begingroup$ @Bernard: You can apply either of the two theorems given here. $\endgroup$ – joriki Aug 2 '15 at 0:18

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.