On the probleme des menages solution on Titu Andreescu book

Question

The probleme des menages consists of the following:

How many ways can $n$ married couples si at a round table in such a way that there is one man between every two women and no man is seated next to his wife?

The solution on Titu Andreescu's book A path to combinatorics for undergraduates, is by Inclusion-Exclusion.

First it states that by treating the seats as being indistinguishable there are $(n-1)!$ ways to seat all of the women, so if we let $M_n$ denote the number of ways to seat the men for a fixed arrangement of women we can say that the answer is $(n-1)!M_n$. First why there are $(n-1)!$ ways to seat the women? Shouldn't it be $n!$?

Second, later in the solution it takes the seats as distinguishable and lets $B_k$ be the set such that if we label the women and men $w_1, \dots w_n$ and $m_1,\dots,m_n$ with $m_i$ married to $w_i$, $B_k$ consists of the arrangements such that $w_i$ and $m_i$ are next to each other for $1\leq i \leq k$. Next it states that the first $k$ couples need to find $k$ pairs of adjacent seats to sit in. And because of this there are $(n-k)!^2$ ways to seat everyone else and

$$|B_k| = 2(k!)(n-k)!^2G_k$$

Where $G_k$ denotes the number of ways to choose $k$ pairs of seats. My question is why there are $(n-k)!^2$ ways to seat everyone else? Shouldn't $B_k$ consist of the arrangements such that only the first $k$ couples are next to each other? Or is it that each arrangements can allow other couples to be next to each other?

Any help would be appreciated thanks.

Answer 1

First why there are (−1)! ways to seat the women? Shouldn't it be !?

In circular permutations, when seats are indistinguishable, the total number of permutations is $(n-1)!$. That's because each unique permutation in the indistinguishable case gives $n$ unique permutations in the distinguishable case - by rotation of an arrangement around the $n$ seats. So, $\dfrac{n!}{n} = (n-1)!$

...why there are $(−)!^2$ ways to seat everyone else?

After $k$ couples have been seated, there will be $2n - 2k = 2(n-k)$ seats remaining. Of these, $n-k$ seats will be occupied by men and the remaining $n-k$ seats by women. Each group of $n-k$ people can be arranged among themselves in $(n-k)!$ ways. Hence, $(n-k)!^2$.

We consider them separately because as the question states, "there is one man between every two women." otherwise it would have been $(2(n-k))!$.

Shouldn't $_$ consist of the arrangements such that only the first $$ couples are next to each other?

If there was a simple and easy way to calculate this, the solution would be (much?) shorter and simpler. We would just find the value for $k = 0$ and that would be the answer. [I know in the present formulation, $k > 0$.]

Since there isn't one, we must find the values for cases with at least $k$ couples are seated next to each other and then use the inclusion-exclusion principle.