Permutations

The Idea of a Permutation

When you arrange objects in a specific order, each distinct ordering is called a permutation. The key point is that order matters. The arrangement ROSE is different from REOS, even though both use the same four letters. In the language of the chapter, a permutation is an arrangement of a number of objects taken some or all at a time, where the sequence is important.

Consider the word NUMBER. It has 6 distinct letters. If you want to form 3-letter words (with or without meaning) without repeating any letter, you are essentially selecting and arranging 3 letters out of these 6. The order matters: NUM is different from NMU. How many such arrangements exist? You can think of it as filling three blanks:

• For the first letter, you have 6 choices.
• For the second letter, you have 5 remaining choices.
• For the third letter, you have 4 remaining choices.

By the multiplication principle, the total number of arrangements is $6 \times 5 \times 4 = 120$.

If repetition of letters were allowed, each of the three positions would have 6 choices, giving $6 \times 6 \times 6 = 216$ arrangements. This simple example shows the core idea: permutations count ordered selections without repetition, and the multiplication principle is the tool we use to count them.

Formal Definition

This definition is the foundation. It tells us two things: (1) we are arranging objects, not just selecting them, and (2) we can take either all objects or only a subset.

The Formula for Permutations

We need a compact way to express the number of permutations of $n$ distinct objects taken $r$ at a time, where $0 \le r \le n$. This number is denoted by $^nP_r$ or $P(n, r)$.

From the example with the word NUMBER, we saw that $P(6, 3) = 6 \times 5 \times 4$. In general, for $P(n, r)$, we multiply $n$ by the next $r-1$ descending integers:

This product has exactly $r$ factors. The last factor is $(n - r + 1)$ because when you have chosen $r-1$ items, you have $n - (r-1) = n - r + 1$ items left.

This formula is direct and works for any $r$ from 1 to $n$. For $r = 0$, we define $^nP_0 = 1$ (there is exactly one way to arrange nothing).

Expressing the Formula Using Factorials

Factorial notation makes the formula cleaner. Recall that $n! = n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1$, and $0! = 1$.

Notice that:

The first $r$ factors of $n!$ are exactly the product in $^nP_r$. Therefore:

This is the standard factorial form. It is especially useful for algebraic manipulation and for proving properties.

Properties and Derivations

The textbook derives several important properties of $^nP_r$. Each one follows directly from the factorial definition.

›Proof

Property 1: $^nP_n = n!$

Put $r = n$ in the formula:

$^nP_n = \frac{n!}{(n-n)!} = \frac{n!}{0!} = n!$

This is the number of permutations of all $n$ distinct objects.

›Proof

Property 2: $^nP_0 = 1$

Put $r = 0$:

$^nP_0 = \frac{n!}{(n-0)!} = \frac{n!}{n!} = 1$

There is exactly one way to arrange zero objects (the empty arrangement).

›Proof

Property 3: $^nP_r = n \times ^{n-1}P_{r-1}$

Start with the factorial form:

$^nP_r = \frac{n!}{(n-r)!}$

Write $n! = n \times (n-1)!$:

$^nP_r = \frac{n \times (n-1)!}{(n-r)!}$

Now note that $(n-r)! = [(n-1) - (r-1)]!$. So:

$^nP_r = n \times \frac{(n-1)!}{[(n-1) - (r-1)]!} = n \times ^{n-1}P_{r-1}$

This property says: to arrange $r$ objects from $n$, you can first choose which object goes in the first position ($n$ ways), then arrange the remaining $r-1$ objects from the remaining $n-1$ objects.

›Proof

Property 4: $^nP_r = (n-r+1) \times ^nP_{r-1}$

Again start with the factorial form:

$^nP_r = \frac{n!}{(n-r)!}$

Write $(n-r)! = (n-r+1) \times (n-r+1)!$? No — careful. Actually:

$(n-r)! = \frac{(n-r+1)!}{n-r+1}$

So:

$^nP_r = \frac{n!}{(n-r)!} = \frac{n!}{\frac{(n-r+1)!}{n-r+1}} = (n-r+1) \times \frac{n!}{(n-r+1)!} = (n-r+1) \times ^nP_{r-1}$

This property gives a recursive relation: the number of permutations of $r$ objects from $n$ equals $(n-r+1)$ times the number of permutations of $r-1$ objects from $n$.

›Proof

Property 5: $^nP_r = \frac{^nP_{r-1}}{(n-r+1)}$ — Wait, this is just a rearrangement of Property 4. The textbook actually states:

$^nP_r = \frac{^nP_{r-1}}{(n-r+1)}$? No, that would be incorrect. Let me re-check.

…