# $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

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?

• Sorry, I'd actually made a comment saying that the formula might be wrong because I tested out the case $r=n$ and felt that there were clearly more than $2$ ways in which every husband can sit next to their wives. That's false, there are actually exactly two ways because the wives' positions are fixed. Commented Nov 10, 2021 at 11:54
• In fact, it looks like this answers your question. Commented Nov 10, 2021 at 19:23
• @TeresaLisbon, my searching obviously failed me. I'm very grateful and would like the bounty go to you for your time and patience! This helped enormously. I don't know if the bountied questions can be closed. Commented Nov 10, 2021 at 22:38
• Unfortunately, it cannot be closed. But I'm happy that I was able to find your solution, after about 35 minutes of searching! What is important here is that you were able to get some kind of solution. The problem is not very easy, as the solution shows. Commented Nov 11, 2021 at 2:35

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.

$$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)!$$
$$card$$ is short for cardinality so number of elements, distinguishable parts or constituents of a set for Santos.