$2n$ people around the table, ways to place exactly $r$ out of $n$ men next to their wives given that $n$ women are already sitting at the table

Question

I'm having some hard time interpreting the following solution.

Let $n\ge 3.$ At the round table with $2n$ seats, there are $n$ women sitting so that there is an empty seat between each two consecutive women. For $0\le r\le n,$ $M(n,r)$ denotes the number of ways to seat their $n$ husbands so that exactly $r$ of them seat next to their wives: $$M(n,r)=\sum_{k=r}^n(-1)^{k-r}\binom{k}r\frac{2n}{2n-k}\binom{2n-k}k(n-k)!.$$

The formula above has to be a result of the inclusion-exclusion formula, but I'm not sure about the setting. Let $$S_k=\{ k\text{ husbands sit next to their wives }\}, r\le k\le n\\ A=\{ \text{ strictly more than } r\text{ husbands sit next to their wives }\}\\ B=\{\text{ exactly } r\text{ husbands sit next to their wives}\}.$$ Then $\left(\bigcup_{k=r}^n S_k\right)\setminus A=B,$ but this is to messy, so I tried to analyze the formula part by part. To understand the factor $$\frac{2n}{2n-k}\binom{2n-k}k(n-k)!,$$ I searched the site and found this and this answer dealing with non overlapping arrangements of $k$ dominoes on a circle. I thought we could first take $k$ couples and view them as dominoes. Then, we're left with $$(2n-2k)=2(n-k)$$ places for $n-k$ men and $n-k$ women. Now, I reached an obstacle as I can't choose $n-k$ seats for women in $\binom{2(n-k)}{n-k}$ ways and I still have to deal with $\binom{k}r$ and $(n-k)!.$

Can somebody provide a hint or an explanation?

Answer 1

Start with two people, a man and a woman, necessarily married. There are two ways to place them in the required manner.

Add another chair to the table. Now there are problems fulfilling the requirements because in one direction they sit next to each other and in the other direction there is always an empty chair between them.

The next act is to add another chair. Then this disambiguation is present with two chairs maximum between and a pairing on the other side.

The next step is another married pair added. Now the problem is hard. Only the woman, man, woman, man order is appropriate. They can swap their seats making four seatings suiting. The pair can swap order to generate a new configuration but just in pairs. We have counted one already. So we have eight seatings. Interpair seat swapping is a new seating, so woman and man of a pair swap seats. woman, woman, man, a man with the restriction that the inner pair is married and the outer pair is married.

Those are only fitting seating if no seat is taken already. Between one to three chairs can be taken. But the orders of the seating are not freshly created by the taken seats. There is always a sure knowledge necessary to whom the sitting persons are married to judge whether this is a valid seating.

Seat taking is drawn without return and the same is selecting the couple. The pairs can not be divided so we have only n pairs to match our condition. $n!$ possibilities to seat them pairwise. The allowed seatings are taken like in the induction initiation. The pair can swap seats, man to man and woman to woman allowed as long as the interpair is still correct.

This constraint has to be applied to the r already taken seats. That is clear from completing such a valid seating. If only one chair remains and there is a couple left the seating is invalid. Same for three chairs and so on. It is like distributing into a paired cell or matching the dominos. But the distribution is more flexible since we can turn the domino.

So the couple constraints mark the seats. $2 n$ chairs for $n$ couples fit our problem.

A literature solution can You find in David A. Santos - Probability: An Introduction: An Introduction on page 110.

Santos states:

$R_n=(n-1)!\sum_{k=0}^{n}(-1)^k\frac{2n}{2n-k}\binom{2 n - k}{k}(n-k)!$

for the number of ways of seating n husband with n wives around a circular table, men alternating with woman, so that no husband sits next to his wife.

He presents a proof using a formular that answers your question.

On the other hand taking into account that the seating you are interested in and the one given by the above formula to the total of all possible seatings than you are done.

Santos helps that problem with the formula:

$S_n=2 n R_n$= $2 n (n-1)! \sum_{k=0}^{n}(-1)^k\frac{2n}{2n-k}\binom{2 n - k}{k}(n-k)!$

Excuse for not confirming Your formula and shorting the paragraph of Santos book so that this is not ab initio understandable.

$card$ is short for cardinality so number of elements, distinguishable parts or constituents of a set for Santos.