The numbers $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$?
  1. How many distinct orderings of the letters in the string “AAABBB” are there?
  2. 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 non-adjacent 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 $(n-3)!$ ways of doing this. There are $n-2$ slots that are separated by the $n-3$ shuffled numbers, and if we insert each of $1,2,3$ into a different slot, they cannot be adjacent. There are $\binom{n-2}{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{n-2}{3} \, (n-3)! &= \frac{6\, (n-3)! \, (n-2)!}{6\,(n-5)!} \\ &= (n-3)(n-4)(n-2)!. \end{aligned} $$