Mathematics · Ch 5 — Permutations and Combinations

Permutations When All the Objects Are Distinct

5.3.1

Permutations When All the Objects Are Distinct

The Fundamental Counting Problem

When we talk about permutations, we are asking: In how many ways can we arrange a given set of objects? The simplest case — and the one that builds the foundation for everything else — is when every object is different from every other object, and we never use the same object twice.

Suppose you have 5 distinct books on a shelf and you want to arrange 3 of them in a row. The first slot can be any of the 5 books. Once you pick one, the second slot can be any of the remaining 4. The third slot then has 3 choices. So the total number of arrangements is $5 \times 4 \times 3 = 60$ . This is the core idea: each choice reduces the pool by one.

The General Formula: $^nP_r$

The textbook states this as Theorem 1: The number of permutations of $n$ different objects taken $r$ at a time, where $0 < r \le n$ and the objects do not repeat, is

n(n-1)(n-2)\cdots(n-r+1)

and this expression is denoted by $^nP_r$ (read as "n P r").

^nP_r = n(n-1)(n-2)\cdots(n-r+1), \quad 0 < r \le n

Why this product? The proof by filling vacant places

Imagine $r$ empty slots in a row, waiting to be filled with distinct objects chosen from a set of $n$ distinct objects.

First place: You can choose any of the $n$ objects. So there are $n$ ways.
Second place: One object is already used, so $n-1$ objects remain. You have $n-1$ ways.
Third place: Two objects are used, so $n-2$ objects remain. You have $n-2$ ways.
...
$r$ th place: By the time you reach the $r$ th slot, you have already used $r-1$ objects. So the number of objects left is $n - (r-1) = n - r + 1$ . You have $n - r + 1$ ways.

By the multiplication principle (if one task can be done in $m$ ways and a second in $n$ ways, the two together can be done in $m \times n$ ways), the total number of ways to fill all $r$ places in succession is the product:

n \times (n-1) \times (n-2) \times \cdots \times (n - r + 1)

This product has exactly $r$ factors. The last factor is $n - r + 1$ , not $n - r$ . Check: when $r=1$ , the product is just $n$ (which is $n - 1 + 1$ ). When $r=n$ , the product runs from $n$ down to $n - n + 1 = 1$ , giving $n!$ .

Watch out

A common mistake is to think the last factor is $n - r$ . It is $n - r + 1$ . For example, $^5P_3 = 5 \times 4 \times 3$ — the last factor is $5 - 3 + 1 = 3$ , not $2$ .

The Problem of Cumbersome Notation

The expression $n(n-1)(n-2)\cdots(n-r+1)$ is correct but unwieldy, especially when $n$ and $r$ are large. Writing it out factor by factor is tedious. We need a compact notation. This is where the factorial symbol $n!$ comes in.

The symbol $n!$ (read as "n factorial" or "factorial n") is defined for a non-negative integer $n$ as the product of all positive integers from 1 up to $n$ :

n! = 1 \times 2 \times 3 \times \cdots \times n

with the special convention that $0! = 1$ (this makes formulas work consistently later).

Using factorials, we can rewrite the permutation formula in a much shorter form. Notice that:

n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1

and

(n-r)! = (n-r) \times (n-r-1) \times \cdots \times 2 \times 1

If we divide $n!$ by $(n-r)!$ , we get:

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

All the factors from $(n-r)$ downward cancel, leaving exactly the product $n(n-1)\cdots(n-r+1)$ . Therefore:

^nP_r = \frac{n!}{(n-r)!}, \quad 0 \le r \le n

This is the compact, standard form. It works for $r=0$ as well: $^nP_0 = \frac{n!}{n!} = 1$ , which makes sense — there is exactly one way to arrange zero objects (do nothing).

Key Special Cases

Case	Formula	Value	Meaning
$r = 1$	$^nP_1$	$n$	Choosing 1 object from $n$ : $n$ ways
$r = n$	$^nP_n$	$n!$	Arranging all $n$ distinct objects: $n!$ ways
$r = 0$	$^nP_0$	$1$	The empty arrangement

Important

The formula $^nP_r = \frac{n!}{(n-r)!}$ is valid for $0 \le r \le n$ . When $r > n$ , $^nP_r$ is defined as 0 (you cannot arrange more objects than you have).

A Quick Example to Cement the Idea

Problem: How many 3-letter words (with or without meaning) can be formed from the letters of the word "DELHI", without repeating any letter? …

Theorem 1

Theorem 1 — Permutations of Distinct Objects

Statement:

The number of permutations of $n$ different objects taken $r$ at a time, where $0 < r \leq n$ and the objects do not repeat, is

n (n-1) (n-2) \cdots (n - r + 1)

This product is denoted by $^nP_r$ (or $P(n, r)$ ).

Important

The three conditions are non-negotiable:

All $n$ objects are distinct (no two are identical).
$r$ is between $1$ and $n$ inclusive — you cannot take more objects than you have.
No repetition — once an object is used in a position, it cannot be used again.

Why this formula makes sense

Think of arranging $r$ objects out of $n$ as filling $r$ empty slots in a row. Each slot gets exactly one object, and no object can appear twice. The number of ways to fill these slots, one after another, is exactly the product above.

›Proof

Proof of Theorem 1

Consider $r$ vacant places arranged in a line:

$\underbrace{\_\_\_\_\_\_\_\_\_\_\_\_\_\_}_{r \text{ places}}$

Step 1 — First place:

Any of the $n$ distinct objects can occupy the first place.

Number of ways = $n$ .

Step 2 — Second place:

One object has already been used. Only $n-1$ objects remain.

Number of ways = $n-1$ .

Step 3 — Third place:

Two objects have been used. Only $n-2$ objects remain.

Number of ways = $n-2$ .

Continuing this pattern:

For the $k$ -th place ( $1 \leq k \leq r$ ), exactly $k-1$ objects have already been placed. So the number of choices for the $k$ -th place is

$n - (k-1) = n - k + 1$

Step r — Last place:

When we reach the $r$ -th place, $r-1$ objects have been used. The number of remaining objects is

$n - (r-1) = n - r + 1$

Applying the multiplication principle:

The total number of ways to fill all $r$ places in succession is the product of the number of ways for each place:

$n \times (n-1) \times (n-2) \times \cdots \times (n - r + 1)$

This is exactly $^nP_r$ .

The multiplication principle applies because the choice at each step is independent of the specific objects chosen earlier — only the count of remaining objects matters.

∎ …

Start your 14-day free trial to unlock the full solution →

← Previous · 5.3Permutations Next · 5.3.2 →Factorial Notation

Permutations When All the Objects Are Distinct