# A round table of six chairs, how many permutations where no husband sits next to his wife?

There are three couples: H1 W1, H2 W2 and H3 W3

Let us fix H1 at the top of the table

then 3 choices for W1

then 4 choices for H2

There is only one choice for W2 to ensure H3 and W3 do not sit together

In addition H1 can sit on any of the six chairs and in each permutation wives and swap with husbands

Hence is the total number 3 x 4 x 6 x 2^3

2^3 as there are three couples

• This can't be correct, as it exceeds $6!$, the number of ways to seat them without restriction. Do you count rotations as distinct? – Ross Millikan Nov 30 '14 at 16:22

There are flaws in your proof.

For instance, that there is only one choice for W2 is wrong in the configuration [H1, *, *, W1, *, *] where, for any choice of H2, there are two compatible choices of W2.

Notice also that if you allow H1 to move and switch H1 and W1, you introduce duplicates.

By looking carefully at all cases, you can have for the H1/W1 couple, one of the 3 configurations

• [H1, *, W1, *, *, *]
• [H1, *, *, W1, *, *]
• [H1, *, *, *, W1, *]

First case: [H1, *, *, W1, *, *]

Then you are left with two contiguous pairs (a,b) and (c,d), so there is one of each couple in each pair, in any order, with any sex. There are thus $2\times2\times2\times2$ solutions: $2\times2$ for the sex of each one in (a,b), another factor two for the order (2,3) or (3,2) in (a,b), and another factor two for the same order in pair (c,d). Hence, 16 solutions.

Second case: [H1, *, W1, *, *, *]

You have (a) alone, and (b,c,d) in a row. Then, whoever you put alone, there will be only one possibility for his/her husband/wife, that is, in the (c) position. And there are then two possibilities, swapping (b) and (d). But you can put any of the four remaining in (a), hence there are 8 solutions.

Third case: [H1, *, *, *, W1, *]

Notice it's the same as the second case, by symmetry. Hence 8 more solutions.

All in all, 32 solutions.

Here is a solution by program, using Mathematica

Select[Permutations[{1, -1, 2, -2, 3, -3}],
And[#[[1]] == 1,
Not[Or @@
Table[Abs[#[[Mod[i, 6] + 1]]] == Abs[#[[Mod[i + 1, 6] + 1]]],
{i, 0, 5}]]] &]

{{1, 2, -1, 3, -2, -3}, {1, 2, -1, -3, -2, 3},
{1, 2, 3, -1, -2, -3}, {1, 2, 3, -1, -3, -2},
{1, 2, 3, -2, -1, -3}, {1, 2, -3, -1, -2, 3},
{1, 2, -3, -1, 3, -2}, {1, 2, -3, -2, -1, 3},
{1, -2, -1, 3, 2, -3}, {1, -2, -1, -3, 2, 3},
{1, -2, 3, -1, 2, -3}, {1, -2, 3, -1, -3, 2},
{1, -2, 3, 2, -1, -3}, {1, -2, -3, -1, 2, 3},
{1, -2, -3, -1, 3, 2}, {1, -2, -3, 2, -1, 3},
{1, 3, -1, 2, -3, -2}, {1, 3, -1, -2, -3, 2},
{1, 3, 2, -1, -2, -3}, {1, 3, 2, -1, -3, -2},
{1, 3, 2, -3, -1, -2}, {1, 3, -2, -1, 2, -3},
{1, 3, -2, -1, -3, 2}, {1, 3, -2, -3, -1, 2},
{1, -3, -1, 2, 3, -2}, {1, -3, -1, -2, 3, 2},
{1, -3, 2, -1, -2, 3}, {1, -3, 2, -1, 3, -2},
{1, -3, 2, 3, -1, -2}, {1, -3, -2, -1, 2, 3},
{1, -3, -2, -1, 3, 2}, {1, -3, -2, 3, -1, 2}}


The meaning of the numbers is rather obvious: 1, 2, 3 for the couple, sign for husband/wife.

There are thus $32$ solutions, and $192$ if you allow H1 to take any place (thus 6 rotations).

As a follow-up, let's have a look at the general case of $n$ couples. Here is a program

Couples[n_] :=
Select[Permutations[Flatten[Outer[Times, Range[n], {1, -1}]]],
And[#[[1]] == 1,
Not[Or @@
Table[Abs[#[[Mod[i, 2 n] + 1]]] ==
Abs[#[[Mod[i + 1, 2 n] + 1]]], {i, 2 n}]]] &]

Table[Length[Couples[n]], {n, 2, 5}]
{2, 32, 1488, 112512}


This is sequence A129348 in OEIS. You'll find formulas there to compute the number of solutions more quickly.

For example, with the program given,

Prepend[
Table[Sum[(-1)^i Binomial[n, i] (2 n - 1 - i)! 2^i, {i, 0, n}],
{n, 2, 16}], 0]

{0, 2, 32, 1488, 112512, 12771840, 2036229120, 434469611520,
119619533537280, 41303040523960320, 17481826772405452800,
8902337068174698086400, 5370014079716477003366400,
3786918976243761421064601600, 3087031512410698159166482022400,
2880726660365605475506018320384000}


For the general formula, see How do I tackle this combinatorics problem about married couples around a table? and the site linked from there about relaxed ménage problem

• 6! total arrangements. To answer the questions we subtract the arrangements where we have couples sitting next to each other. Case I: One couple sits together. C(3,1)*C(3,1)*2*2*2*2 ways to do this. Case II: Two couples sit together C(3,2)*C(3,2)*2*2*2 ways to do this Case III: All couples sit together 3! * 2^3 ways to do this 6! -240 = 480 Where did I go wrong? – Dunka Nov 30 '14 at 20:19
• @Dunka Difficult to explain without a drawing, but I obtain respectively $3\times6\times2^4=288$ for case I, $3\times6\times2^3=144$ for case II and $6\times2^4=96$ for case III. Thus there are $192$ permutations left. – Jean-Claude Arbaut Nov 30 '14 at 21:45
• Interesting. I first selected a couple to stay together C(3,1) ways to do this. We then have 3 couples seats to place them in. I think that's where I made my mistake, there are still 6 seats even though I've chosen to represent the six people as 3 couples briefly. – Dunka Nov 30 '14 at 23:31
• @Dunka For case I, I do this: first select the couple, 3 choices. Place of the couple around the table, 6 rotations. Place of W/H in this couple, 2 choices. Then for the other two couples, you can have (2,3,2,3) or (3,2,3,2), 2 choices. And exchange W/H, that's 2 choices for each couple. Thus $6\times3\times2^4$. You have to be very careful to get all possibilities, without duplicates, so be as "orthogonal" as possible about the different parameters. – Jean-Claude Arbaut Dec 1 '14 at 7:19