Unit 24 · Permutations and Combinations
Count arrangements with ${}^nP_r$ and $n!$, handle conditions such as "together" and "not together", and arrange letters of words with repeated letters.
A permutation is an arrangement of objects in which the order matters. Choosing a president, a secretary and a treasurer from a group is a permutation problem, since "Asha president, Binu secretary" is different from "Binu president, Asha secretary".
How many ways can $r$ positions be filled from $n$ different objects? The first position has $n$ choices, the second $n-1$, and so on: $${}^nP_r = n(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n-r)!}, \qquad 0 \le r \le n,\ r \in \mathbb{Z}.$$ Here ${}^nP_r$ is also written $P(n,r)$. When $r = n$ (arrange all of them), $${}^nP_n = \frac{n!}{0!} = n!.$$
Example: How many $3$-digit numbers with all digits different can be made using the digits $0,1,\dots,9$? The hundreds digit cannot be $0$, so it has $9$ choices. The tens digit can be any of the remaining $9$ digits (including $0$), and the units digit any of the remaining $8$. So $9 \times 9 \times 8 = 648$.
Example: Find $n$ if ${}^nP_2 = 56$. ${}^nP_2 = n(n-1) = 56$, so $n^2 - n - 56 = 0$, that is $(n-8)(n+7) = 0$. Since $n > 0$, $n = 8$.
Together. To keep some objects side by side, glue them into one block. Arrange the blocks and the other objects, then arrange the objects inside the block.
Example: In how many ways can the letters of COMBINE be arranged in a line so that the three vowels $O, I, E$ are together? Glue the vowels into one block. Now there are $4$ consonants and $1$ block, i.e. $5$ items, giving $5!$ arrangements. Inside the block the vowels can be arranged in $3!$ ways. Total $5! \times 3! = 120 \times 6 = 720$.
Not together. Either subtract: (all arrangements) $-$ (arrangements with them together); or place the others first and put the restricted objects in the gaps between them.
Example: Five people are seated in a row. In how many ways are $A$ and $B$ not sitting next to each other? All arrangements: $5! = 120$. With $A$, $B$ together: $4! \times 2! = 48$. So not together: $120 - 48 = 72$.
Gap method. To keep $k$ objects apart from one another, arrange the other $m$ objects first. They create $m+1$ gaps (including both ends). Choose positions for the $k$ objects from those gaps, one per gap: ${}^{m+1}P_k$ ways.
If some objects are identical, swapping them gives the same arrangement, so counting $n!$ counts each arrangement too many times. Suppose $p$ of the $n$ objects are identical. Each arrangement was counted $p!$ times (once for each way to rearrange the identical ones among themselves), so the number of different arrangements of all $n$ objects is $\dfrac{n!}{p!}$. With groups of $p$, $q$ and $r$ identical objects, $$\frac{n!}{p!,q!,r!}.$$
Example: How many different arrangements are there of the letters of MATHEMATICS? There are $11$ letters; $M$, $A$, $T$ each appear twice and $H, E, I, C, S$ once. The number is $\dfrac{11!}{2!,2!,2!} = \dfrac{39916800}{8} = 4989600$.
Example: How many arrangements of the letters of LEVEL begin with $L$? Fix $L$ first. The remaining letters $E, V, E, L$ have $E$ twice, so there are $\dfrac{4!}{2!} = 12$ arrangements.
Exam tip: Write the type of count before calculating: "all different, $n!$", "$r$ at a time, ${}^nP_r$", "identical objects, divide by $p!$". For "not together", examiners expect either the subtraction method or the gap method with a short sentence of reasoning, not just a number. For words, count the letters first and list the repeated ones.