How many permutations are there of $1, \ldots ,8$ in which none of the patterns 12, 34, 56, 78 appear?

828 Views Asked by At

I had thought this was a fairly simple Inclusion/Exclusion problem, but I noticed that my answer doesn't match the back of the book. Here is my thought process:

Let S denote the set of all permutations of $1,\ldots ,8$. Then $\#S = 8!$.

We want to exclude the following properties:

$P(1)$: 12 occurs

$P(2)$: 34 occurs

$P(3)$: 56 occurs

$P(4)$: 78 occurs

So then $N(i)=7!$, $1 \leq i \leq 4$, $i \in \mathbb{N}$ because we can "combine" the 2-digit numbers into 1 and then find the number of permutations for a length 7 string.

$P(1,2)$: 12 and 34 occur

... and so on (6 times)

So $N(i,j) = 5!$ because we combine 4 of the numbers and treat it as one number in a string of length 5 ([1234] 5 6 7 8 would be an arrangement).

However, I stopped here because my book says that $N(i,j)=6!$, and I cant seem to figure out why. In addition, it says $N(i,j,k) = 5!$, but I would think it would be $3!$. What am I missing?