Redundancy of Inclusion/Exclusion in a group of four pairs

Question

I have been presented with a fairly basic counting problem with forbidden positions as follows:

A carousel has eight seats, each representing a different animal. Eight boys are seated on the carousel but facing inward, so that each boy faces another (each boy looks at another boy’s front). In how many ways can the boys change seats so that each faces a different boy?

The first three steps I've worked out and are fairly basic, accomplished by treating the boys as four pairs {a1, a2}, {b1, b2}, {c1, c2}, and {d1, d2}.

• Total possibilities = 8! (seats are distinct, so no rotationally equivalent permutations exist)
• Forbidden possibilities with at least one pair = $C(4, 1) * P(4, 1) * 2 * 6!$ (choose the pair to stay facing, choose an opposing pair of seats, permute the pair across the two seats, and permute the remaining 6 boys)
• Forbidden possibilities with at least two pairs = $C(4, 2) * P(4, 2) * 2^2 * 4!$ (choose two facing pairs, permute across four pairs of seats, permute each pair, and permute the remaining 4 boys)

Clearly, the answer (with minor simplification) begins with $8! - 32 * 6! + 288 * 4!$ and to this point the provided solution agrees.

At this point, however, the solution strikes me as strange because it goes on to count the number of solutions with three pairs as well as the solutions with four pairs, and adds those terms into the Inclusion/Exclusion equation. This seems incorrect because the permutations with at least three matching sets should be exactly the same as the permutations with exactly four matching sets - if you place each of pairs a, b, and c in facing seats, the only seats left available for pair d are facing as well. In effect, the expected $C(4, 3)$ term to select the three opposing pairs ought to be left out entirely; since any selection of three pairs to be opposing automatically makes the fourth pair opposing, all of these selections are identical for practical purposes.

Therefore, while the provided solution has the final equation $$8! - 32*6! + 288*4! - 768*2! + 384$$ the solution I worked out is $$8! - 32*6! + 288*4! - 384$$

Can someone please explain the flaw in my reasoning? Thanks.

Answer 1

Here is some additional information which might be helpful to clarify the situation. First of all two aspects.

• ... the permutations with at least three matching sets should be exactly the same as the permutations with exactly four matching sets ...

This statement is correct and in fact here is no problem at all. The interesting part is earlier in the text, namely

• ...Forbidden possibilities with at least one pair ... Forbidden possibilities with at least two pairs ...

The wording at least contains the crucial information. When calculating all forbidden possibilities with at least one pair we count also configurations with two and more pairs.

So, already in these steps forbidden possibilities with three pairs and four pairs are somehow considered, typically overcounted resp. undercounted and this fact has to be respected in the further steps.

Let's look at the example from @bof with respect to over- and undercounting of subsets.

We consider a finite set $E$ with subsets $A,B,C,D\subset E$. We want to count all elements in $E$ which are not in one of the subsets, i.e. we calculate \begin{align*} |E\setminus&(A\cup B\cup C\cup D)|=|E|-|A|-|B|-|C|-|D|\tag{1}\\ &+|AB|+|AC|+|AD|+|BC|+|BD|+|CD|\tag{2}\\ &-|ABC|-|ABD|-|ACD|-|BCD|\tag{3}\\ &+|ABCD|\tag{4} \end{align*}

We analyse the situation with respect to overcounting and undercounting elements when performing the steps (1) to (4) step by step. We partition the set according to these steps, take a representative from the single subsets, from the intersection of two subsets, etc. and mark in each step how often the representatives are counted.

In the table below we list the representatives in the leftmost column and obtain

\begin{array}{l|rrrr} \qquad&1\quad&2\quad&3\quad&4\\ \hline |A\setminus(B\cup C\cup D)|\quad&\color{blue}{-1}\quad\\ |AB\setminus(C\cup D)|\quad&-2\quad&\color{blue}{-1}\quad\\ |ABC\setminus D|\quad&-3\quad&0\quad&\color{blue}{-1}\quad\\ |ABCD|\quad&-4\quad&2\quad&-2\quad&\color{blue}{-1}\quad \end{array}

Recall we want to subtract each element from $A,B,C$ and $D$ precisely once from $E$, so that each of these elements should have finally count $\color{blue}{-1}$.

• Column 1 Situation after step (1): $$|E|-|A|-|B|-|C|-|D|$$

  • Elements which are in $A$ but not in any other subset are subtracted exactly once, indicated by $-1$ in the first row. Here we can stop. Nothing more to do with these elements.

  • Elements which are in $A\cap B$ but not in any other subset are subtracted twice, since they are subtracted by $|A|$ and also by $|B|$, indicated by $-2$ in the second row. So, these elements are undercounted by one.

  • Elements which are in $A\cap B\cap C$ but not in $D$ are subtracted three times, namely in $|A|, |B|$ and $|C|$. These elements are undercounted by two, indicated by $-3$ in the third row.

  • Elements which are in $A\cap B\cap C \cap D$ are subtrated four times, namely in $|A|, |B|, |C|$ and $|D|$. These elements are undercounted by three, indicated by $-4$ in the fourth row.

• Column 2 Situation after step (2): \begin{align*} &|E|-|A|-|B|-|C|-|D|\\ &\qquad+|AB|+|AC|+|AD|+|BC|+|BD|+|CD| \end{align*}

  • Elements which are in $A\cap B$ but not in any other subset are added exactly once and the compensation for (1) is done.

  • Elements which are in $A\cap B\cap C$ but not in $D$ are added three times, namely in $|AB|, |AC|$ and $|BC|$. These elements are now overcounted by one, indicated by $0$.

  • Elements which are in $A\cap B\cap C \cap D$ are added six times, namely in $|AB|, |AC|, |AD|, |BC|, |BD|$ and $|CD|$. These elements are overcounted by three, indicated by $+2$.

• Column 3 Situation after step (3):
  \begin{align*} &|E|-|A|-|B|-|C|-|D|\\ &\qquad+|AB|+|AC|+|AD|+|BC|+|BD|+|CD|\\ &\qquad-|ABC|-|ABD|-|ACD|-|BCD| \end{align*}

  • Elements which are in $A\cap B\cap C$ but not in $D$ are subtracted exactly once and the compensation for (2) is done.

  • Elements which are in $A\cap B\cap C \cap D$ are subtracted four times, namely in $|ABC|, |ABD|, |ACD|$ and $|BCD|$. These elements are undercounted by one, indicated by $-2$.

• Column 4 Situation after step (4):
  \begin{align*} &|E|-|A|-|B|-|C|-|D|\\ &\qquad+|AB|+|AC|+|AD|+|BC|+|BD|+|CD|\\ &\qquad-|ABC|-|ABD|-|ACD|-|BCD|\\ &\qquad+|ABCD| \end{align*}

  • Elements which are in $A\cap B\cap C\cap D$ are added exactly once and the compensation for (3) is done.

Conclusion: We observe we need all steps to compensate for over- and undercounting which started right at the beginning.

$$ $$

Finally I'd like to write down the calculation of OPs problem. We obtain \begin{align*} \binom{4}{0}^2&0!2^08!-\binom{4}{1}^21!2^16!+\binom{4}{2}^22!2^24! -\binom{4}{3}^23!2^32!+\binom{4}{4}^24!2^40!\\ &=8!-32\cdot6!+288\cdot 4!-768\cdot 2!+384\\ &=23040 \end{align*}

• For example the fourth summand, starting with $\binom{4}{3}$ has the interpretation:

  $\binom{4}{3}$ possibilities to select $3$ out of $4$ pairs of boys

  $\binom{4}{3}$ possibilities to select $3$ out of $4$ pairs of seats

  $3!$ possibilities to permute the pairs of boys accross the selected pairs of seats

  $2^3$ possibilities to place paired boys within their pair of seats.

  $2!$ possibilities to place the remaining two boys.