$1, 2, ..., n$
are permuted (or shuffled). How many different permutations exist such that no two of the numbers $1, 2, 3$
are adjacent when $n = 5$
and $n = 6$
? How about for arbitrary $n > 4$
?

 How many distinct orderings of the letters in the string “AAABBB” are there?
 In how many ways can you order the sequence of digits
$1,2,3,4,5$
such that$1$
always comes before$2?$

How many ways are there to shuffle numbers
$4,5, \ldots, n?$

How many ways are there to shuffle numbers
$1,2,3?$

How many ways are there to pick three nonadjacent points to insert
$1,2,3$
into the other numbers?

We start by taking the numbers
$4,5, \ldots, n$
and shuffling them. There are$(n3)!$
ways of doing this. There are$n2$
slots that are separated by the$n3$
shuffled numbers, and if we insert each of$1,2,3$
into a different slot, they cannot be adjacent. There are$\binom{n2}{3}$
ways to do this. Finally, there are$3!$
ways to order the numbers$1,2,3$
. Multiplying these together we get:$$ \begin{aligned} 6 \, \binom{n2}{3} \, (n3)! &= \frac{6\, (n3)! \, (n2)!}{6\,(n5)!} \\ &= (n3)(n4)(n2)!. \end{aligned} $$