How many ways to form $7$-digit numbers from $\{1,2,\ldots,9\}$ in which $4$ is not the next of $5$? I have tried in several cases:


*

*the digits don't contain five only, so the number of possible ways is $8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2$

*the digits don't contain four only, so the number of possible ways is $8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2$

*the digits don't contain both four and five, so the number of possible ways is $7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1$

*the digits contain both four and five, but I am stuck on this case.
The result is that I add up the numbers in the four cases.
Is that process true?
 A: The correct results for the first three cases you enumerated are:


*

*The number contains $4$ but not $5$: we obtain $7\cdot\binom{7}{6}\cdot 6!$ different numbers (the $7$ accounts for the position of the $4$, the binomial for choosing $6$ other digits out of the $7$ possible and the $6!$ for ordering them).

*The number contains $5$ but not $4$: we obtain again $7\cdot\binom{7}{6}\cdot 6!$ different numbers.

*The number contains neither $4$ nor $5$: we obtain $\binom{7}{7}\cdot 7! = 7!$ different numbers.


For the fourth case, if the number contains both $4$ and $5$, we must consider different cases. The trick is to consider the placement of $4$ as the first number:


*

*If $4$ is placed as the first or last digit, $5$ can be placed in $5$ different places, this gives us $2\cdot 5\cdot \binom{7}{5}\cdot 5!$ different numbers (the $2$ is for the two positions considered for the $4$, the $5$ for the position of the $5$, the binomial for choosing $5$ other numbers and the $5!$ for ordering them).

*If $4$ is not the first or last digit, $5$ can be placed only in $4$ places, thus we get $5\cdot4\cdot\binom{7}{5}\cdot 5!$ different numbers.

