How many 7 permutations of $\{1,\ldots,9\}$ are there such that $5$ and $6$ do not appear consecutively

Question

I found this problem in the textbook Introductory Combinatorics, and am very confused by the answer provided by the text. Here is how I tried to solve it:

Define $P_{r,n}$ to be $r$-permutations of a set with $n$ elements.

Then there are, in total, $P_{9,7}$ $7$-permutations of our set. Considering the subset of permutations where $[5,6]$ occurs, in that order, there are $P_{8,7}$ such permutations, since we can treat $[5,6]$ as one element. Similarly for $[6,5]$.

Thus the solution must be $P_{9,7} - 2*P_{8,7} = 100800$. But the textbook instead breaks it down into 4 cases: (i) neither $5,6$ appear, (ii) both $5,6$ appear, $iii, iv$ one of the two appears. They find the answer $186,480$.

What is wrong with my reasoning that I got the solution wrong?

Answer 1

I see that what with your approach and the book's answer, there is confusion worse confounded. I don't see how cases can be avoided, so let's see case by case, calling numbers other than $5,6$ as "ordinary" and $5,6$ as "special"

• $7$ ordinary: $7!$
• $6$ ordinary and $1$ special: $\binom76\binom21 7!$
• $5$ ordinary, $2$ special: $\binom75(7!-2*6!)$
• Add up to get a total of $151200$

Answer 2

You are wrong when counting the number of permutations containing $[5,6]$, and the same mistake for $[6,5]$. You should count the number of permutations that contain both $5$ and $6$, where $5$ and $6$ are consecutive.

Hence, you get the right answer when replacing $P(8,7)$ by $C(7,5)*6!$. The right answer is $151200$, I think. The answer in the textbook is also wrong.

Answer 3

You can use Mathematica to verify your result.

allPermutations = Permutations[Range[9], {7}];
consecutive56Permutations = 
  Select[allPermutations, (SequencePosition[#, {5, 6}] =!= {} || 
      SequencePosition[#, {6, 5}] =!= {}) &];
result = Length[allPermutations] - Length[consecutive56Permutations]

$$ \color{red}{151200} $$