# 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:

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

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

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

4. 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?

• Is $1111111$ a permissible $7$-digit number? You haven't accounted for numbers with repeated digits. Also, does "4 is not the next of 5" mean we exclude numbers such as 1234567 and 7654321? Sep 22, 2013 at 13:30
• in your calculation for not containing 5, there is a possibility of 4 not being there as well Sep 22, 2013 at 13:31
• sorry, I forget to give additional explanation, all of the formed digits are different. Sep 22, 2013 at 13:33

1. 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).
2. The number contains $5$ but not $4$: we obtain again $7\cdot\binom{7}{6}\cdot 6!$ different numbers.
3. 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.