0
$\begingroup$

Find the number of ways in which $n$ men and $n$ women can sit around a round table such that every man can pair off with a woman sitting next to him (to form $n$ couples).

Anyone can help with this problem? Thanks :)

EDIT: Ignore rotations of the table. For example, when $n=1$ there should be only 1 seating arrangement.

$\endgroup$
  • $\begingroup$ Maybe you can simplify by sitting them in a straight line so that you have a woman at one end and a man at the other end. $\endgroup$ – BFD Oct 30 '13 at 7:43
  • $\begingroup$ So far I have the following progress: Fix a particular woman at the left end of the straight line, then among the remaining $(2n-1)$ seats, choose $n$ seats for the men - there are $\binom{2n-1}{n}$ ways to do this. Finally, there are $(n-1)!$ ways to sit the other women and $n!$ ways to seat the men, so our final answer is $\binom{2n-1}{n} (n-1)! n!$. Is this right? $\endgroup$ – heron1000 Oct 30 '13 at 7:48
  • $\begingroup$ So the men and women are distinguishable? (please don't conclude this is my general non-mathematical perspective :) ). Also, remember that if you sit a woman at one end, you must seat a man in the opposite end. $\endgroup$ – BFD Oct 30 '13 at 7:53
  • 1
    $\begingroup$ See the addendum to my answer. For the current problem as stated in the question, the answer is $(2^n-1)(n-1)!n!$. $\endgroup$ – Dan Shved Oct 30 '13 at 8:31
2
$\begingroup$

First of all, we can assign seats in two stages. First, decide which $n$ seats will be for men and which for women. Second, arrange men on male seats and women on female seats.

For the second step, there are always $(n!)^2$ possibilities. So the answer to the problem is $k \cdot (n!)^2$, where k is the number of ways to decide which $n$ seats will be for men. So what is left is to find $k$.

For convenience, let us assign numbers to seats (say, clockwise): $1, 2, \ldots, 2n$. When every male seat is paired with a nearby female seat, there are two possibilities: either the paired seats are $(1, 2), (3, 4), \ldots, (2n-1, 2n)$, or they are $(2, 3), (4, 5), \ldots, (2n-2, 2n-1), (2n, 1)$.

Let $A$ be the set of all male-female seat assignments that allow pairing of the first kind, and $B$ the set of all assignments that allow pairing of the second kind. Now $k$ is the cardinality of their union $A \cup B$.

It is easy to find $|A|$. In each pair we pick arbitrarily which seat will be male and which female. There are $2^n$ choices, so $|A| = 2^n$. In a similar fashion, $|B|=2^n$.

Now, to find $|A \cup B|$, we note that $|A \cup B| = |A| + |B| - |A \cap B|$. What is $A \cap B$? It is the set of all male-female assignments that can be split into pairs in both ways: "$(1, 2), (3, 4), \ldots$" and "$(2, 3), (4, 5), \ldots$". There are only 2 assignments like this: one is when we assign all odd seats to men and even seats to women, the other is when we do the opposite. So $|A \cap B| = 2$.

Then we see that $k = 2^n + 2^n -2$, and the answer is $(2^{n+1}-2) \cdot (n!)^2$.

UPDATE: Ok, I assumed this was clear, but maybe not. I assume that all seats are distinguishable, and so are all the $2n$ people. So, $2n$ people enter a room, and you know each of them personally. And $2n$ seats are standing at fixed places around the table, and each seat is familiar to you, and each is precious in its own way, like an old friend. Now people take their seats at the table, and for you it is important who sits where exactly. If two men swap positions - you notice, because you distinguish them. If everyone stands up and moves to the seat to the right, thus rotating the whole arrangement - you also notice, because you know and distinguish the seats as well as people.

If you decide you don't want to distinguish between different men and different women, you drop the $(n!)^2$ factor. If you decide in addition that you don't even distinguish between sexes, you divide the answer by 2.

If your understanding is that people are all distinguishable, but rotations of the table don't really change the arrangement, then simply divide my answer by $2n$. The justification is simple: given one allowed arrangement, you can get $2n$ distinct arrangements from it by rotations. I have counted each one as a separate arrangement, but for you they are all the same, so you divide the answer by $2n$ to get $(2^n - 1) \cdot n! \cdot (n-1)!$.

$\endgroup$
  • $\begingroup$ Taking $n=1$ gives a total of 2 ways, which is clearly wrong.. $\endgroup$ – heron1000 Oct 30 '13 at 7:56
  • $\begingroup$ @heron1000 how come? There is a round table with two seats, 1 and 2. There is one man and one woman. We can put the man on seat 1 and the woman on seat 2, or the other way around. So there are 2 ways. $\endgroup$ – Dan Shved Oct 30 '13 at 7:59
  • $\begingroup$ Maybe you have a different notion of which seatings are considered the same and which are considired different. In this case, please specify this precisely in your question. $\endgroup$ – Dan Shved Oct 30 '13 at 7:59
  • $\begingroup$ Hmm... usually we know that the number of ways to seat $n$ people around a round table is $(n-1)!$, so the number of ways to seat 2 people around a round table is just 1... there isn't really a 'different notion' here. $\endgroup$ – heron1000 Oct 30 '13 at 8:03
  • 2
    $\begingroup$ @heron1000 There is. I described my default understanding in my answer. Your default understanding is to think that rotations don't produce a new arrangement. For some people mirror symmetries also don't produce a new arrangement, but it seems that for you they do. Ideally, you should specify these things clearly in the problem itself. $\endgroup$ – Dan Shved Oct 30 '13 at 8:11
-1
$\begingroup$

This is what I think:

Imagine that there are $n$ seats where the men can sit, and $n$ seats in between these seats where the women can sit.
The number of ways the men can sit is $n!$, and the number of ways where the women can sit is also $n!$.
But here are 2 ways of seating these people:
man,woman,man,woman... or woman,man,woman,man...

Therefore the total number of ways is $2(n!)^2$.

Proof:

If $n=2$ then $2(n!)^2=8$

Assume that odd numbers are female and even numbers are male.
Combinations: $1234,1432,2143,2341,3214,3421,4123,4321$

$\endgroup$
  • $\begingroup$ why the vote down? $\endgroup$ – EpicGuy Oct 30 '13 at 7:49
  • $\begingroup$ Your answer is definitely wrong because first of all, you forgot to take into account rotations of the table.. (though I wasn't the one who voted you down) $\endgroup$ – heron1000 Oct 30 '13 at 7:50
  • 1
    $\begingroup$ Notice too, that $n!^2 > (2n)!=$ total ways of seating 2n people. $\endgroup$ – BFD Oct 30 '13 at 7:51
  • $\begingroup$ @EpicGuy, your answer is clearly wrong. You just counted arrangements of one kind, the kind you were able to see immediately. You haven't exhausted all the possible seatings. $\endgroup$ – Dan Shved Oct 30 '13 at 7:57
  • 1
    $\begingroup$ @BFD No, $n!^2$ is way smaller than $(2n)!$. $\endgroup$ – Dan Shved Oct 30 '13 at 7:58

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.