3
$\begingroup$

Its my first time posting here, so if I am doing something wrong please inform me.

My question:

Find the number of ways to seat $n$ married couples around a table if men and women alternate.

I seen the solution where you seat $n$ men first and then the women. but I don't get why my solution is incorrect:

First we seat them in a row in the following way: we put a man in the first seat ($n$ ways), then a woman in the second ($n$ ways) and so on and we get $n!\times n!$.

Now there are $2n$ people on the row, to turn it into a table sitting we divide by $2n$ and we get $\dfrac{n!(n-1)!}{2}$ which is an incorrect answer.

I would like to understand where I made a mistake

The correct answer: $n!(n-1)!$

Edit: Just wanted to thank all of you! you really helped me there. If anybody have anything to add/more approaches to solving the problem - please do, I will gladly read it.

$\endgroup$
  • $\begingroup$ Another approach: 1) number the chairs $1,2,3\dots$ such that the chairs numbered $i,i+1$ are consecutive chairs 2) choose whether the men sit on even or on odd numbered chairs 3) place the men 4) place the women 5) rectify (the $2n$ stairs are not distinguishable) by dividing with $2n$. Solution $2n!n!/(2n)=(n-1)!n!$ $\endgroup$ – drhab Nov 17 '18 at 10:21
  • $\begingroup$ Thanks a lot! Another way to look at it :] $\endgroup$ – Johnny Nov 17 '18 at 19:39
7
$\begingroup$

Note that with your approach you start by seating one of the $n$ men, rather than any of the $2n$ persons. That is, the $n!n!$ you initially come up with is the number of possible orderings for a straight table (or line-up) that start with a man. A such, when you take into account that the table is round, and that different rotations correspond to the same straight ordering, you should just divide by the number of men, rather than the number of total people.

Alternatively, you could first calculate the number of possible orderings for a straight line-up starting with any person. That means that you start with any of $2n$ choices ... but now that the gender is fixed, you have only $n$ choices for a person of the opposite sex for the second person, then $n-1$ choices for the third, $n-1$ for the fourth, etc. So, there are 2n(n−1)!n! possible straight orderings starting with man or woman. And now there are indeed $2n$ rotations per such ordering, so divide that by $2n$, and you get $(n−1)!n!$

Finally, let's do a concrete example to see what is happening. Suppose you have men $A$ and $B$ and women $C$ and $D$. Now, if you start the straight line-ups with a man, the possible straight orderings are $ACBD, ADBC, BCAD$, and $BDAC$ ( which is $4$ .. which is indeed $2!2!$). But how many circular orderings are there? There are $2$, so you need to divide by $2$ ... the number of men. Indeed, ACBD and BDAC are the same, and same for the other pair.

Alternatively, you could first consider all possible line-ups, starting with man or woman. So now you also have $CBDA, CADB, DACB$, and $DBAC$ as possible line-ups, for a total of $8$. And now you need to divide by $4$ (e.g. $ACBD, BDAC, CBDA$, and $DACB$ are all the same for a circular table)

$\endgroup$
  • $\begingroup$ I dont understand why I need to divide by n. I made a round table with 2n people right? then to get rid of the 2n same rotations i divide by 2n? $\endgroup$ – Johnny Nov 16 '18 at 13:02
  • 1
    $\begingroup$ @Johnny No, that's what I just tried to explain. Your initial orderings started with the men, not just any person. So, there are only $n$ rotations that give you the same ordering. Let's do an example; you have men A and B and women C and D. Now, you start with a man, the possible straight orderings are ACBD, ADBC, BCAD, and BDAC ( which is 4 .. which is 2!2!). But how many circular orderings are there? There are 2, so you need to divide by 2 ... indeed, ACBD and BDAC are the same, and same of the pther pair. But since you do not have CBDA or DACB initially, you do not divide by 4 $\endgroup$ – Bram28 Nov 16 '18 at 13:10
  • $\begingroup$ Another way to think about this: of course you could start by making the straight ordring starting with any person, so that's $2n$ chpices ... after which the next person has to be one of $n$, the next person one of of $n-1$, the next person one of $n-1$, etc. So, there are $2n(n-1)!n!$ possible straight orderings starting with man or woman. And now there are indeed $2n$ rotations possible, so divide that by $2n$, and you get $(n-1)!n!$ $\endgroup$ – Bram28 Nov 16 '18 at 13:15
  • $\begingroup$ wow! It took me a bit of time to understand it but your in depth explanation and concrete examples are is really awesome And the alternative way you provided is in itself a great solution + it helped me understand the overall picture. Really thank you!!!!! $\endgroup$ – Johnny Nov 16 '18 at 13:57
  • 1
    $\begingroup$ Another way to look at it is to imagine that the first chair in your row is red. You have counted all possible permutations of alternating men and women where a man is sitting in the red chair and there are $n!\cdot n!$ of them. Given one particular arrangement $a$ of the men and women around a table, you have only counted $n$ of the $2n$ different row arrangements that correspond to $a$. (Out of the $2n$ row arrangements corresponding to $a$, half have a woman in the red chair and were not counted.) $\endgroup$ – Steve Kass Nov 16 '18 at 14:12
2
$\begingroup$

@Bram already gave a nice answer concerning your misunderstanding. This answer only provides in another strategy to solve the problem.

For convenience assume that the men involved have distinct ages.

1) place the youngest man on a seat (it is inevitable that someone is the first right?).

2) place the remaining $n-1$ men on seats in such a way that no pair sits next to each other. This can be done on $(n-1)!$ ways.

3) place the women on the remaining seats. This can be done on $n!$ ways.

So there are $(n-1)!n!$ possibilities.

$\endgroup$
  • $\begingroup$ I would love to understand this strategy. As I understood: 1. we seat the youngest somewhere among the 2n seats. 2. because we dont want the pairs to sit next to each other, there are n-1 choices for the next brother,n-2 for the next and so on, therefore its (n-1)! 3. Then we seat women, the first 1 has n choices, and so on so its n! 4. so we multiple it as u said and its the result. Now if I understood it correctly, we dont count the number of posibilies for where we place the youngest man on a seat(2n). Why is that? $\endgroup$ – Johnny Nov 16 '18 at 16:23
  • $\begingroup$ Now that I think about it, it seems it has to do with the relative position of them. Because doesnt matter where we put the first 1 we can rotate him to any position but the others are placed relative to him. I am still not 100% sure so if possible would love to understand your thought process of how that works $\endgroup$ – Johnny Nov 16 '18 at 16:30
  • $\begingroup$ The correct answer you mentioned in your question indicates that the chairs are not distinguishable. So all what counts is the number of arrangements w.r.t. the first person who takes a seat. If the chairs have numbers then in special case $n=2$ there would be not $(2-1)!2!=2$ possibilities but $4(2-1)!2!=8$ possibities (in general $2n(n-1)!n!=2n!n!$). This because we then start with a choice of the chair out of $4$ for the youngest man. So your understanding of the strategy is correct. If the chairs are distinguishable then $2n!n!$ possibilities, if not then $(n-1)!n!$ possibilities. $\endgroup$ – drhab Nov 16 '18 at 17:38
  • $\begingroup$ Ok now I understand. Thank you so much! Your approach helped me undestand things more and helped me clear more of my confusions! $\endgroup$ – Johnny Nov 16 '18 at 19:25
  • $\begingroup$ You are very welcome. $\endgroup$ – drhab Nov 16 '18 at 19:36

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.