# Combinatorics/variation dinner problem

I’m stuck in the following math challenge. The situation is as follows:

When six couples organize some dinners, they take place at a rectangular table with six places on each sides. Since one should never sit in front of his or her partner, these places are numbered.
What is the number of dinners that can be organized if the 12 people should never sit on the same place as during a previous dinner?

I closely examined this problem for several times and I think it’s a variation with repitition, but I got stuck with the conditions described above.

#### Solutions Collecting From Web of "Combinatorics/variation dinner problem"

You can do this by inclusion-exclusion. It is just like the famous derangements problem, though the formula is more complicated, and there appears to be no direct relation between the outcomes.

For $0\leq k\leq n$ let us count the number of ways a specific subset of $k$ couples will be opposite each other (not caring about whether any other couples are). The women of those $k$ couples can choose their places in $2n(2n-2)\ldots(2n-2k+2)=2^kn^{\underline k}=2^k\binom nkk!$ ways, their partner then have no choice; there remain $(2n-2k)!$ permutations for the remaining $(n-k)$ people. Now one must also take into account that the subset of $k$ couples can be chosen in $\binom nk$ ways. Then inclusion-exclusion says we must sum all this with a sign $(-1)^k$ attached
$$f(n)=\sum_{k=0}^n(-1)^k\binom nk2^k\binom nkk!(2n-2k)!$$
This allows us to compute $f(6)=278\,323\,200$ rapidly.

The formula can be simplified. One can observe that $2^nn!$ divides $f(n)$, which is related to the fact that the centraliser in the group $S_{2n}$ of the involution that interchanges each pair of opposite places acts simply on the set of solutions. This factor $2^nn!$ divides each term of our sum, which we can make evident by extracting from $(2n-2k)!$ a factor $2^{n-k}(n-k)!$ (the product of the even factors) leaving a quotient $q(n)=\prod_{i=1}^n(2i-1)$ (sometimes written $(2n-1)!\!!$, but I won’t); the products $2^k2^{n-k}=2^n$ and $\binom nkk!(n-k)!=n!$ can then be extracted from the sum, giving
$$f(n)=2^nn!\sum_{k=0}^n(-1)^k\binom nkq(n-k).$$
The summation can now be recognised as the inverse binomial transform of the sequence $(q(n))_{n\in\Bbb N}=(1,1,3,15,105,495,10395, 135135, \ldots)$, which can be computed by repeatedly applying the forward difference operator to the sequence
$$\matrix{ 1&&1&&3&&15&&105&&945&&10395\\ &0&&2&&12&&90&&840&&9450&\\ &&2&&10&&78&&750&&8610&\\ &&& 8 && 68 &&672 &&7860\\ &&&&60&&604&&7188\\ &&&&&544&&6584\\ &&&&&&6040 }$$
from which one can read off that $f(6)=2^6\times6!\times6040$, which is indeed the number I reported before. The sequence $\left(\frac{f(n)}{2^nn!}\right)_{n\in\Bbb N}=(1, 0, 2, 8, 60, 544, 6040, 79008,\ldots)$ is A053871.

Note that the sequence of derangement numbers (subfactorials) is similarly the inverse binomial transform of the sequence $(n!)_{n\in\Bbb N}$ of factorials.

Seat the 6 women on one side. This can be done in $6!$ ways. Now seat the men, this can be done in $D_6$ ways (here $D_n$ is the number of derangements). If you also consider the possibility of seating women at random on both sides of the table, another factor of $2^6$. In all:

$$6! \cdot D_6 \cdot 2^6$$

For simplicity, I shall assume man-woman couples, and discuss under two conditions:

(a) men-women must sit opposite to each other.

(b) men-women need not (but could) sit opposite to each other.

The only stipulation is that couples can’t sit opposite to each other.

Case (a) has been dealt with by vonbrand and I agree with the answer. It is case (b) that has been proving a bother.

There are 6 pairs of seats that are opposite each other. Suppose $k$ of them seat couples.

The seats for the $k$ couples can be chosen in $\binom6{k}$ ways,
and the couples can be placed in them in $_6P_k$ ways.

The remaining $(12-k)$ can be placed in $\frac{(12-k)!}{2^{(n-k)}}$ ways

Applying inclusion-exclusion, ways with no couples sitting opposite

$= 12!/2^6$ – ways with at least one couple opposite + ways with at least 2 couples opposite – …

$$= \sum_{k=0}^6(-1)^k\cdot\binom{6}{k}\cdot \;_6P_k\frac{(12-k)!}{2^{(6-k)}} = 4,348,800$$

I have not permuted objects between the two sides. If you want to do that, multiply by $2^6$

I guess the questioner might have had the simpler problem in mind, but this one was more fun !

THIS ANSWER IS WRONG PER REBECCA’S COMMENT BELOW. Leaving it up for legacy reasons only.

NOTE: This answer assumes men and women must sit across from each other (just as long as they don’t sit across from their partners). If women can sit across from other women, this answer does not apply.

You can seat the 6 women in 12*11*10*9*8*7 or 665,280 ways.

In theory, the men can fill the remaining 6 chairs in 6! or 720 ways, but many of these ways would put a man across from his wife. Only 265 of these ways are “derangements” where no man sits across from his wife.

Thus, the total number of ways is 665,280*265 = 176,299,200 ways.

I interpreted “if the 12 people should never sit on the same place as during a previous dinner” as meaning: it’s ok if 10 people sit in the same place as a previous dinner, provided that all 12 people don’t occupy the exact same chairs as they did at a previous dinner.

The other interpretation is that one person may never occupy the same chair twice, in which case there could be at most 12 dinners.

There is no rule forbidding any arrangement other than couples sitting opposite each other.

Consider a row of 12 seats. Ways in which no couples sit together can be found using inclusion-exclusion, treating couples sitting together as “flippable individuals“, (i.e. single objects), hence

$12! – \binom61\cdot2^1\cdot11! + \binom62\cdot2^2\cdot10! – …..$
$$= \sum_{j=0}^6(-1)^j\cdot\binom{6}{j}\cdot 2^j\cdot(12-j)! = 168422400$$

Now let persons in odd numbered chairs remain,
and shift the rest opposite so that $1$ and $2,\;\;3$ and $4$ …. are opposite each other.

Further explanation:

It may be easier to understand, if we imagine the two numbered rows
$01-02-03-04-05-06$
$07-08-09-10-11-12$

to be interleaved into one row
$01-07-02-08-03-09-04-10-05-11-06-12$,
and simply count how many ways there are to seat the people so that no couple is together.

The answer obtained for such a count has been confirmed at OEIS