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

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

• vonbrand, can you explain me why you use derangements to seat the men? – Has Jan 8 '16 at 23:55
• Men can't sit across their wives – vonbrand Jan 8 '16 at 23:56
• Are you accounting for the case where women sit across from each other? There's no rule that a woman must sit across from a man? – barrycarter Jan 9 '16 at 4:35
• Under the assumptions that men and women must sit across each other, nice and simple answer (+1) – true blue anil Jan 10 '16 at 8:13

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 !

• If my answer of $4,348,800$ is multiplied by $2^6$, (given as an option, as did @vonbrand), the answer of $278,323,200$ is the same as that of @Marc van Leeuwen. I wonder whether there is an OEIS sequence for my version. – true blue anil Jan 10 '16 at 12:18
• No that is not the case. – Marc van Leeuwen Jan 10 '16 at 15:58

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.

• Assuming heterosexual couples, $12 \times 11 \times \cdots \times 7$ counts cases where women sit opposite other women, which is what you wanted to exclude. (Oh, and women can sit across from other women at rectangular tables. It's amazing what we can do when we put our minds to it.) – Rebecca J. Stones Jan 9 '16 at 8:18
• Also, if you are permuting women thus, what is the "original" place for men against which derangements are being counted ? – true blue anil Jan 9 '16 at 11:59

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

• The $(12-j)!$ does not seem right. If we have $j=1$, we choose one couple whose partners must sit opposite, then that couple can sit in $6$ positions ($\times 2$ for when they're flipped), and the remaining people can sit in $10!=(12-2j)!$ ways. It looks like it should be $\sum_{j=0}^6 (-1)^j \binom{6}{j} 2^j [6]_j (12-2j)!$, where $[6]_j=6 \times \cdots \times (6-j+1)$. (Also, the problem statement does not stipulate genders; they could all be of the same gender.) – Rebecca J. Stones Jan 9 '16 at 8:01
• @Rebecca J. Stones: I have eliminated genders. Re the other point, I first seated all in a row with no couples together, then transferred to the other side. I will take a closer look. – true blue anil Jan 9 '16 at 8:59
• @Rebecca J. Stones: I have checked my result of no couples together in a row. It tallies with oeis.org/A007060 – true blue anil Jan 9 '16 at 10:17
• I dislike this answer: suppose one member of a couple is seated in position 1 and the other is seated in position 12. If in a row, they are not next to each other. At a rectangular table, however, they are. Linking math.stackexchange.com/questions/1125114 – barrycarter Jan 9 '16 at 17:27
• I don't see how seat 1 and seat 12 can be next to each other. They are on different sides ! I am sending "non-couple" 1 and 2 to seats 1 and 7, and so on, see "further explanation". – true blue anil Jan 9 '16 at 17:39