Permutations — Definition and Formula Derivation

A permutation is an arrangement of a given number of objects taken from a larger collection, where the order in which the objects are placed matters — swapping two objects' positions produces a different permutation, even though the same objects were chosen. This is the key feature that will later distinguish a permutation from a combination (Section 5), where order is irrelevant.

The number of permutations of $r$ objects chosen from $n$ distinct objects (with $0 \le r \le n$, no object repeated) is denoted $^{n}P_{r}$ (also written $P(n, r)$).

Deriving the product form using the Fundamental Principle of Counting

Imagine filling $r$ positions in a row, one at a time, using distinct objects drawn from a pool of $n$:

• The 1st position can be filled in $n$ ways (any of the $n$ objects).
• Once that object is placed, the 2nd position can be filled in $n - 1$ ways (one object has been used up).
• The 3rd position can be filled in $n - 2$ ways, and so on.
• The $r$-th position can be filled in $n - (r-1) = n - r + 1$ ways, since $r - 1$ objects have already been placed.

By the Fundamental Principle of Counting (Section 1), applied $r$ times in succession, the total number of ways to fill all $r$ positions is the product of these $r$ decreasing factors:

Converting the product form to factorial form

This product is correct but inconvenient to manipulate. To write it compactly using factorials, multiply and divide by the product of all the remaining integers from $(n-r)$ down to $1$ — that is, by $(n-r)!$:

The numerator is now the product of every integer from $n$ down to $1$, i.e. $n!$, and the denominator is $(n-r)!$. Hence

Checking the boundary cases …