Permutations of distinct objects

A permutation is an arrangement of objects in a definite order. If you change the order, you get a different permutation. So $ABCD$ and $BACD$ are different permutations of the four letters $A, B, C, D$.

Definitions

The number of permutations of $n$ distinct objects taken $r$ at a time is denoted $P(n, r)$ (or $^nP_r$, or $P^n_r$). It is the number of distinct sequences of length $r$ whose entries come from a set of $n$ distinct items, with no repetition.

By the multiplication principle: $\boxed{P(n, r) = n \cdot (n - 1) \cdot (n - 2) \cdots (n - r + 1) = \dfrac{n!}{(n - r)!}.}$

Special cases:

• $P(n, 0) = 1$ (the empty sequence).
• $P(n, n) = n!$ (full arrangement of all $n$).
• $P(n, 1) = n$.

Derivation

To form a sequence of length $r$ from $n$ distinct items:

• $1^{\text{st}}$ position: $n$ choices.
• $2^{\text{nd}}$: $n - 1$ choices (one already used).
• $\vdots$
• $r^{\text{th}}$: $n - r + 1$ choices.

Total: $n (n - 1) \cdots (n - r + 1) = \dfrac{n!}{(n - r)!}$. $\qed$

Common applications

• Words / letters / codes. Arrange $r$ letters from $n$.
• Numbers. Form $r$-digit numbers from $n$ distinct digits.
• Queues / seats. Arrange $r$ people in $r$ specific seats from a pool of $n$.

Permutations under constraint

A typical Class-XI problem adds a constraint:

• Two specific objects together. Treat them as a block (Example 4 of subtopic 1).
• Two specific objects apart. Subtract "together" cases from total.
• Specific position. Fix the constrained position first, then arrange the rest.

Worked examples

Example 1. How many $3$-letter sequences can be formed from $A, B, C, D, E, F, G$ if (a) repetition is allowed, (b) not allowed?

(a) Multiplication principle: $7^3 = 343$.

(b) $P(7, 3) = 7 \cdot 6 \cdot 5 = 210$.

Example 2. In how many ways can the letters of the word "PEACE" be arranged in a row? (We will revisit identical letters in the next subtopic; for now treat each letter as distinct, i.e. just count arrangements of $5$ distinct symbols.)

If treated distinct: $5! = 120$. (If $E$'s are identical, $\dfrac{5!}{2!} = 60$.)

Example 3. Find $n$ such that $P(n, 5) = 20 \cdot P(n, 3)$.

$\dfrac{n!}{(n - 5)!} = 20 \cdot \dfrac{n!}{(n - 3)!}$.

Divide both sides by $\dfrac{n!}{(n - 3)!}$ (non-zero): $\frac{(n - 3)!}{(n - 5)!} = 20 \iff (n - 3)(n - 4) = 20.$ So $n^2 - 7n + 12 = 20$, i.e. $n^2 - 7n - 8 = 0$, $n = 8$ (rejecting $n = -1$).

Example 4. How many $4$-digit numbers without repeated digits can be formed from $1, 2, 3, 4, 5, 6, 7$?

$P(7, 4) = 7 \cdot 6 \cdot 5 \cdot 4 = 840$.

Example 5 (harder). How many arrangements of the letters of "BANANA" (with repeats) have the two $N$'s never together?

The word has letters $B, A, N, A, N, A$ , six letters, but three $A$'s and two $N$'s (and one $B$). Total distinct arrangements: $\dfrac{6!}{3! \cdot 2!} = 60$.

Arrangements where the two $N$'s are together: glue them as a block "$NN$". We are arranging $5$ objects: $B, A, A, A, NN$. That gives $\dfrac{5!}{3!} = 20$.

Hence number with $N$'s not together: $60 - 20 = 40$.

Try it yourself

1. Compute $P(10, 3)$, $P(7, 7)$, $P(6, 4)$.
2. How many $5$-digit numbers can be formed from $1, 2, 3, 4, 5, 6, 7, 8$ with no repetition?
3. Find $n$: $P(n, 4) = 12 \cdot P(n, 2)$.
4. In how many ways can $6$ people stand in a row?
5. In how many of these does person $A$ stand first?
6. In how many ways can the letters of "EQUATION" be arranged so that all vowels are together?
7. How many $4$-letter words start with a consonant from the letters $A, B, C, D, E$?
8. How many $5$-digit numbers from $0$ – $9$ without repetition have no leading zero?
9. How many permutations of "MATHEMATICS" treating letters as distinct? (Then divide by repetitions: subtopic 4.)
10. In a class of $25$, in how many ways can a President, Vice-President and Secretary be chosen?
11. How many ways can $4$ red and $3$ blue balls be arranged in a row if all balls are distinguishable?
12. How many three-digit even numbers with no repeated digits can be formed from $1, 2, 3, 4, 5, 6$?

Pitfalls / Tricks

• Permutations are about order. $ABC \ne ACB$ as permutations even though the same letters are used.
• Always check: are objects distinct? Is repetition allowed? Two questions before any formula.
• Constraint-based problems: handle the constraint first, then arrange the rest freely.
• Insight. When two objects must stay together, glue them and multiply by the internal orderings. When two must stay apart, count "all" minus "together".