The Computer Laboratory

Practice Paper 3 Question 20

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\)?

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  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?\)

Hints

  • Hint 1
    How many ways are there to shuffle numbers \(4,5, \ldots, n?\)
  • Hint 2
    How many ways are there to shuffle numbers \(1,2,3?\)
  • Hint 3
    How many ways are there to pick three non-adjacent points to insert \(1,2,3\) into the other numbers?

Solution

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{align} 6 \, \binom{n-2}{3} \, (n-3)! &= \frac{6\, (n-3)! \, (n-2)!}{6\,(n-5)!} \\ &= (n-3)(n-4)(n-2)!. \end{align} \]

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.