How many ways can 4 couples sit around a table so that no couple sits together?

4.8k Views Asked by At

The tools I have at my disposal and want to use are multiplication and composition of ordinary and exponential generating functions.

Initially I thought one approach would be to think of the people as a multiset {1,1,2,2,3,3,4,4}. Then we could use e.g.f. to break it up into unspecified number of subsets, and on each of them find a way to satisfy the requirement of the question. Lastly we would permute the subsets.

Yet I'm worrying that this might lead to double-counting. Also it might be the case that the endpoints of the subsets still violate the requirement, i.e. we could have something like {1,2,3},{3,2,4,1,4}.

1

There are 1 best solutions below

0
On BEST ANSWER

Since the OP says the couples sit "around" a table, I'm assuming this is a round table, and arrangements which differ only by a circular shift are considered equivalent. The following solution uses the Principle of Inclusion and Exclusion (PIE).

If we disregard the constraint on couples sitting together, the $8$ people can be seated around the table in $N= 7!$ ways.

Let's say an arrangement of the couples has "Property $i$" if couple $i$ are seated together, for $i=1,2,3,4$. Define $S_j$ to be the total number of arrangements with $j$ of the properties, for $j=1,2,3,4$.

If one couple sits together, the couple can be selected in $\binom{4}{1}$ ways. The members of the couple can be arranged in $2$ ways: man on the left or man on the right. If we consider the couple as one object and all the other people as one object each, then we have $7$ objects to arrange around the table, which can be done in $6!$ ways. So $$S_1 = \binom{4}{1} \cdot 2 \cdot 6!$$

Similarly, $$\begin{align} S_2 &= \binom{4}{2} \cdot 2^2 \cdot 5! \\ S_3 &= \binom{4}{3} \cdot 2^3 \cdot 4! \\ S_4 &= \binom{4}{4} \cdot 2^4 \cdot 3! \\ \end{align}$$ By PIE, the number of arrangements with none of the properties, i.e. the number of arrangements in which no couple sits together, is $$N-S_1+S_2-S_3+S_4 = 1488$$