Table of Contents
In combinatorics, a permutation is an arrangement of objects in a specific order. The key idea is that order matters: changing the order produces a different permutation.
In this chapter we will focus on:
- Counting permutations in basic settings.
- Distinguishing situations where order matters from those where it does not (the latter belong to combinations, treated in another chapter).
- Handling special cases: permutations of some of the objects, and permutations with repeated objects.
Basic idea: order matters
Suppose you have three distinct letters: $A$, $B$, and $C$. How many different ordered arrangements can you make using all three?
You can list them:
- $ABC$
- $ACB$
- $BAC$
- $BCA$
- $CAB$
- $CBA$
There are $6$ permutations. Notice that $ABC$ and $ACB$ are regarded as different because the order of letters is different.
If you try to build each permutation step by step:
- First position: you can choose any of $3$ letters.
- Second position: you can choose any of the remaining $2$ letters.
- Third position: you must use the remaining $1$ letter.
Total arrangements:
$$
3 \times 2 \times 1 = 6.
$$
This reasoning generalizes to $n$ distinct objects.
Factorials and permutations of $n$ distinct objects
To count permutations of $n$ distinct objects, we use the product:
$$
n \times (n-1) \times (n-2) \times \dots \times 2 \times 1.
$$
This product is called $n$ factorial and is written $n!$.
For $n$ distinct objects, the number of permutations using all of them is:
$$
n!.
$$
Examples:
- $4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$.
- $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$.
So:
- $4$ distinct books on a shelf can be arranged in $4! = 24$ different orders.
- $5$ students can line up in $5! = 120$ different ways.
By convention, we define:
$$
0! = 1.
$$
This is consistent with counting (there is exactly one way to arrange “nothing”) and with formulas that will appear later.
Permutations of $r$ objects chosen from $n$ distinct objects
Sometimes you do not use all the objects, only some of them. You might, for example, want to know: in how many ways can I choose and arrange $r$ objects from $n$ distinct ones?
Again, order matters: choosing $A$ then $B$ is different from choosing $B$ then $A$.
Think step by step:
- First position: $n$ choices.
- Second position: $n-1$ choices (one is used).
- Third position: $n-2$ choices.
- Continue until you have filled $r$ positions.
The product stops after $r$ factors:
$$
n \times (n-1) \times (n-2) \times \dots \times (n-r+1).
$$
This number is called the number of permutations of $n$ objects taken $r$ at a time. It is often written as $P(n, r)$ or $_nP_r$:
$$
P(n, r) = n (n-1) (n-2) \dots (n-r+1).
$$
Using factorials, this can be written more compactly:
$$
P(n, r) = \frac{n!}{(n-r)!}.
$$
To see why: $n! = n (n-1) \dots (n-r+1)\cdot (n-r)\cdot (n-r-1)\dots 1$, so dividing by $(n-r)!$ cancels the extra factors, leaving just the first $r$ factors.
Examples
- How many 3-letter “codes” can be formed from 5 distinct letters if no letter is repeated and order matters?
Here $n=5$, $r=3$:
$$
P(5,3) = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{120}{2} = 60.
$$
- In how many ways can a president, vice president, and secretary be chosen from 10 people, if one person can hold at most one office?
The roles are distinct (order matters: who gets which role), so:
$$
P(10,3) = \frac{10!}{7!} = 10 \cdot 9 \cdot 8 = 720.
$$
- How many different 2-digit numbers can be formed using the digits $1,2,3,4,5$ without repetition?
Positions: tens and ones, order matters.
$$
P(5,2) = \frac{5!}{3!} = 5 \cdot 4 = 20.
$$
Permutations vs. combinations (conceptual distinction)
This course separately treats combinations, but it is important here to clearly distinguish them from permutations.
- In permutations, order matters.
- In combinations, order does not matter.
As a mental test: if swapping two chosen objects gives a “new” outcome in the situation you care about, then you are in a permutations setting; if not, it is a combinations setting.
Examples of where permutations are appropriate:
- Arranging books on a shelf.
- Assigning ordered roles (first place, second place, third place).
- Creating sequences or codes where position is important.
Examples that do not use permutations (but combinations, discussed separately):
- Choosing a committee where members have no distinct roles.
- Selecting a set of toppings for a pizza (ignoring placement).
In this chapter, we only count situations where the order of selected items matters.
Permutations with repetition allowed
Sometimes, objects can be reused. For example, forming a password where the same character can appear more than once. In that case, once you choose an object for one position, it is still available for other positions.
Assume you have $n$ possible symbols and you want to build a code of length $r$, allowing repetition and with order important.
For each position:
- First position: $n$ choices.
- Second position: again $n$ choices (repetition allowed).
- Each of the $r$ positions has $n$ choices.
Total permutations:
$$
n^r.
$$
Examples:
- How many 4-digit PIN codes can be made using digits $0$–$9$, if digits can repeat?
There are $n = 10$ digits, and $r=4$ positions:
$$
10^4 = 10\,000.
$$
- How many 3-letter “strings” can be formed from the letters $A,B,C$ if repetition is allowed?
Here $n=3$, $r=3$:
$$
3^3 = 27.
$$
Each of the 27 strings is a permutation with repetition allowed (for example: $AAA$, $ABC$, $CCA$, etc.).
Permutations of multiset elements (with identical objects)
Up to now, we have assumed all objects are distinct. But what if some objects are identical?
Example: consider the letters in the word “TOO”. If you treated each letter as different, you might think there are $3! = 6$ permutations. But the two $O$’s are indistinguishable, so many of those arrangements look the same:
- Distinct-label view: $T O_1 O_2$, $T O_2 O_1$, $O_1 T O_2$, $O_2 T O_1$, $O_1 O_2 T$, $O_2 O_1 T$.
- When $O_1$ and $O_2$ are just “O”, the first two are the same visible arrangement “TOO”, the next two are both “OTO”, and the last two are both “OOT”.
So there are really only $3$ distinct arrangements: “TOO”, “OTO”, “OOT”.
To count permutations of a multiset (a set with repeated elements), you start with $n!$ permutations as though all items were distinct, then divide by the factorial of each repeated count to correct for over-counting.
If you have $n$ total objects, where:
- $n_1$ are identical of type 1,
- $n_2$ are identical of type 2,
- …
- $n_k$ are identical of type $k$,
with $n_1 + n_2 + \dots + n_k = n$, then the number of distinct permutations is:
$$
\frac{n!}{n_1!\, n_2! \dots n_k!}.
$$
Examples
- Word “TOO”:
- Total letters: $n = 3$.
- $T$: appears once ($n_1 = 1$).
- $O$: appears twice ($n_2 = 2$).
Number of distinct permutations:
$$
\frac{3!}{1!\, 2!} = \frac{6}{2} = 3.
$$
- Word “LEVEL”:
Letters: $L, E, V, E, L$.
- Total letters: $n = 5$.
- $L$: 2 copies.
- $E$: 2 copies.
- $V$: 1 copy.
Number of distinct permutations:
$$
\frac{5!}{2!\, 2!\, 1!} = \frac{120}{4} = 30.
$$
- Word “MISSISSIPPI”:
Count letters:
- $M$: 1
- $I$: 4
- $S$: 4
- $P$: 2
Total letters: $n = 1 + 4 + 4 + 2 = 11$.
Number of distinct permutations:
$$
\frac{11!}{1! \, 4! \, 4! \, 2!}.
$$
The exact numerical value is large, but the formula is what matters.
Using permutations in simple counting problems
Here are some typical ways permutations appear in problems.
Arranging objects in a line
If you have $n$ distinct objects to place in a row, the number of ways is $n!$.
If you want only $r$ positions filled from $n$ objects (no repetition), the number is $P(n,r)$.
Example: 7 people want to stand in a row of 4 positions for a photo; each arrangement is a different photo. There are:
$$
P(7,4) = \frac{7!}{3!} = 7\cdot 6 \cdot 5 \cdot 4
$$
possible photos.
Assigning distinct roles
When you assign different positions or titles to people, you are arranging them into roles, so permutations apply.
Example: You need to choose a captain, co-captain, and treasurer from 8 players, with no person holding more than one role. This is:
$$
P(8,3) = \frac{8!}{5!} = 8\cdot 7 \cdot 6.
$$
Forming ordered sequences or codes
Whenever a problem involves forming a sequence (PINs, codes, passwords, license plates) and the order matters, permutations are used, with or without repetition depending on the rules.
- Without repetition: use $P(n,r)$.
- With repetition allowed: use $n^r$.
Example: How many ways to create a 3-character code from 5 distinct symbols if symbols cannot repeat?
Answer:
$$
P(5,3) = \frac{5!}{2!} = 60.
$$
If repetition is allowed, the count would be:
$$
5^3 = 125.
$$
Summary
- A permutation is an ordered arrangement of objects.
- Permutations of $n$ distinct objects using all of them: $n!$.
- Permutations of $n$ distinct objects taken $r$ at a time (no repetition):
$$
P(n,r) = \frac{n!}{(n-r)!}.
$$ - Permutations with repetition allowed from $n$ symbols in $r$ positions: $n^r$.
- Permutations of $n$ objects with repeated groups of identical objects:
$$
\frac{n!}{n_1!\, n_2! \dots n_k!},
$$
where $n_i$ counts the copies of each identical type. - Permutations are used whenever order matters: arranging, ranking, assigning distinct roles, or forming ordered codes or sequences.