Fun combinatorics: How many numbers with some restrictions I came accross this fun problem today: How many 8-digit numbers are there where:


*

*each digit appears only one

*digits 1-4 appear sequentially (though not necessarily consecutively)

*5 does not appear after 4


I basically counted all possibilities but what would be a nice way to express the solution? Thank you.
 A: Following the suggestion in the hint, we compute the number of ways $1-4$ appear consecutively, and subtract the number of ways $1-5$ appear consecutively.  We split into two cases.
Case 1: The first digit is $1$.  Then, choose the slots for $2,3$, and $4$, and arrange other numbers to fill in.  Here we find:
$$\binom{7}{3}\cdot6\cdot5\cdot4\cdot3=12600$$
ways to do this.  To find how many of these arrangements have $5$ after $4$, choose the $4$ slots for $2,3,4$, and $5$, and arrange other numbers to fill in.  There are
$$\binom{7}{4}\cdot5\cdot4\cdot3=2100$$
ways to do this, so in case 1, we find $10500$ ways total.
Case 2: The first digit is not $1$.  Then, choose the four slots for the numbers $1,2,3,$ and $4$, and fill in the remaining numbers, remembering $0$ can't be the first digit.  There are:
$$\binom{7}{4}\cdot5\cdot5\cdot4\cdot3=10500$$
ways to do this.  To find how many of these arrangements have $5$ after $4$, choose the $5$ slots for $1,2,3,4$, and $5$, and fill in the remaining slots without $0$ in the first slot:
$$\binom{7}{5}\cdot4\cdot4\cdot3=1008$$
So from case 2 we find $9492$ ways as well.
In all, there are $19,992$ such numbers.
