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$?
-
- 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 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} $$