Tricky seating arrangements

It's probably easiest to count the complement first, i.e., the number of arrangements where at least one couple sits together, and then subtract this from the total number of arrangements, namely $10!.$ To do this we will need to do some inclusion/exclusion counting.

If we were to count the number of arrangements that have at least one couple side by side, we would end up over-counting those arrangements where more than one couple sits side by side. In fact, we end up counting those arrangements that have precisely $n$ couples sitting side by side $n$ times for $1 \le n \le 5.$

If we were to count the number of arrangements that have at least two couples sitting side by side, we would end up counting the number of arrangements with precisely $n$ couples sitting side by side $\binom{n}{2}$ times for $2 \le n \le 5.$

In general, if we were to count the number of arrangements that have at least $k$ couples sitting side by side for $1 \le k \le 5,$ we end up counting the number of arrangements with precisely $n$ couples sitting side by side $\binom{n}{k}$ times for $k \le n \le 5.$

Now let $\alpha_{k}$ represent the number of arrangements that have at least $k$ specific couples sitting side by side. Now in general $\alpha_{k} = 2^{k}(10 - k)!,$ since we can order each of these $k$ couples in two ways, and then arrange these $k$ couples and $10 - 2k$ remaining individuals in $(k + (10 - 2k))! = (10 - k)!$ ways.

Then, by the applicable inclusion-exclusion formula , (refer to the first special case), we see that the desired solution is

$\displaystyle\sum_{k=0}^{5} (-1)^{k}\dbinom{5}{k}\alpha_{k} = \sum_{k=0}^{5} (-2)^{k}\dbinom{5}{k}(10 - k)! = \boxed{1263360}.$

As a general result, with $M$ couples, the number of arrangements in which none of the couples sit side by side is given by

$P_{M} = \displaystyle\sum_{k=0}^{M} (-2)^{k} \dbinom{M}{k}(2M - k)!.$

It would appear that $\lim_{M \rightarrow \infty} \dfrac{P_{M}}{M!} = \dfrac{1}{e},$ just as in a derangement, but I don't have a proof for this yet.

Let $S_{m,n}$ be the number of ways to seat $m$ individuals and $n$ couples (that is $m+2n$ people).

If $m$ or $n$ is negative, $S_{m,n}=0$ . $S_{0,0}=1$ . (More over, $S_{m,0}=m!$ , but we won't need that.)

Let's find a recurrence relationship for $S_{m,n}$ .

• If at first you seat someone in couple, you have $2n$ ways to choose that person, and then you have $S_{m+1,n-1}$ ways to seat the others, of which you have to remove $S_{m,n-1}$ ways where you just seated the significant other of the first person right after. That makes $2n·(S_{m+1,n-1}-S_{m,n-1})$ .
• If at first you seat someone not in couple, you have $m$ ways to choose that person, and then you have $S_{m-1,n}$ ways to seat the others, which are all valid ways. That makes $m·S_{m-1,n}$ .

So, we have:

$\boxed{S_{m,n}\,\,=\,\,2n\,·\,(S_{m+1,n-1}\,-\,S_{m,n-1})\,\,+\,\,m\,·\,S_{m-1,n}}$

The answer is then $S_{0,5}=1'263'360$ , which you get by computing all $S_{m,n}$ where $m+n≤5$ .

1
2
3
4
5
6

def S(n,m):
  if n<0 or m<0: return 0
  if n==0 and m==0: return 1
  return 2*n * (S(n-1,m+1) - S(n-1,m))  +  m * S(n,m-1)

print S(0,5)

A007060

Coded this problem to help me solve it.

Count the number of arrangements with all five couples sitting together. This is just $\binom{5}{5}*2^5*5!$

Then for any number of couples $x$ sitting next to each other ( $x$ from 1 to 5) we have the number of arrangements with $x$ couples sitting next to each other is

$\displaystyle tgt(x)=\binom{5}{x}*\left[2^x*(10-x)!-\sum_{i=x+1}^5 tgt(i)*\binom{i}{x}\div \binom{5}{x}\right]$

The idea is to choose $x$ couples from the 5, and stick them together. Then the number of ways to order the 10 people are $2^x*(10-x)!$ , however we must discount scenarios where there are actually more than $x$ couples sitting together.

For any specific choice of $x$ couples, only a portion of $tgt(i)$ arrangements include those $x$ couples, and that is precisely $\binom{i}{x}\div\binom{5}{x}$ .

Now just choose your favorite programming language to solve for $tgt(0)$

1
2
3
4
5
6
7

def tgt(x):
  sub=0
  for i in range(x+1,6):
    sub+=tgt(i)*choose(i,x)/choose(5,x)
  return choose(5,x)*((2**x)*fact(10-x)-sub)

print tgt(0)

This was hard, but fun - third try, no less. My approach is similar to Brian Charlesworth's, but I use linear algebra in the end.

For simplicity, let $M=5$ be the number of couples going to the cinema, and $n=2M$ the number of persons. They have $n!$ possibilities to choose seats, but that includes all permutations where one (or more) couples sit next to each other: $\begin{aligned} x_i&=\text{number of permutations with exactly }i\text{ couples sitting next to each other}\\ n!&=x_0+\ldots+x_M \end{aligned}$

Our goal is $x_0$ , the number of permutations without any couple sitting next to each other.

Perhaps it's easier to calculate $x_1$ instead, the number of permutations where exactly one couple sits next to each other. We have $M$ ways to choose one of the couples and 2 ways to order it. Now imagine that we treat the couple as a single entity, to get $(n-1)!$ permutations of the remaining "persons". In total, we get: $\binom{M}{1}\cdot 2\cdot (n-1)!$

There is just a slight problem: With the last step, we also counted all permutations with two or more couples! Even worse, we counted them multiple times - each permutation with exactly $i$ couples we count precisely $i$ times: $2\binom{M}{1}(n-1)!=x_1+2x_2+\ldots+Mx_M=\sum_{i=1}^M\binom{i}{1}x_i$

However, we can generalize the approach. If we try to calculate $x_k$ , we choose $k$ of $M$ couples and have $2^k$ ways to order the significant others. Again, we treat these couples as single entities, to get $(n-k)!$ permutations of the remaining "persons". Similarly to before, we count all permutations with exactly $i$ couples precisely $\binom{i}{k}$ times: $\begin{aligned} 0&\leq k \leq M:&&&2^k\binom{M}{k}(n-k)!&=x_k+\binom{k+1}{k}x_{k+1}+\ldots+\binom{M}{k}x_M=\sum_{i=k}^M\binom{i}{k}x_i \end{aligned}$

On to the linear algebra part. We have $M+1$ equations and $M+1$ variables - let's put them together into one system: $\begin{aligned} A&:=\left(\binom{i}{k}\right)_{k,i}&&&\vec{b}&:=\left(2^k\binom{M}{k}(n-k)!\right)_k&&&\vec{x}&:=(x_i)_i&&&\Rightarrow &&&& A\vec{x}&=\vec{b} \end{aligned}$

Luckily, $A$ has a simple general inverse and we get $x_0$ , the number of permutations without any couple sitting next to each other: $\begin{aligned} A^{-1}&=\left( (-1)^{k+i}\binom{i}{k} \right)_{k,i}&&&\Rightarrow&&&&x_0&=\sum_{i=0}^M(-1)^i\cancel{\binom{i}{0}}\cdot 2^i\binom{M}{i}(n-i)!=\sum_{i=0}^5(-2)^i\binom{5}{i}(10-i)!=\boxed{1263360} \end{aligned}$

Rem.: The approach via inverse has an added benefit - we get any $x_k$ we want: $x_k=(-1)^k\sum_{i=k}^M(-2)^{i}\binom{i}{k}\binom{M}{i}(n-i)!$

is the number of permutations with exactly $k$ of $M$ couples sitting next to each other!

My solution:

========================================================

permute AABBCCDDEE > combos

grep -v AA combos | grep -v BB | grep -v CC | grep -v DD |grep -v EE > combos.no_spouses

wc combos.no_spouses

1263360 1263360 13896960 combos.no_spouses

========================================================

(I couldn't think of an elegant mathematical way to solve it to I resorted to brute force and compute power! ;^) )