Permutations

May 2026 · 18 min read

A permutation is an ordered arrangement of a set of objects. Whenever order matters — books on a shelf, runners crossing a finish line, characters in a string — you are counting permutations. This post derives every permutation formula from scratch using the basic principle of counting from Part 2.

Arrangements of $n$ Distinct Objects: $n!$

Suppose we have $n$ distinct objects and want to put them in a row. By the multiplication rule:

• Position 1: any of the $n$ objects ($n$ choices).
• Position 2: any of the remaining $n-1$ objects ($n-1$ choices).
• Position 3: any of the remaining $n-2$ ($n-2$ choices).
• $\dots$
• Position $n$: only 1 object remains.

The factorial $n!$ is read “n factorial”. By convention $0! = 1$, which is the right value because there is exactly one way to arrange the empty set: the empty arrangement.

Factorials grow alarmingly fast. $10! = 3{,}628{,}800$ and $20! \approx 2.4 \times 10^{18}$, which is already too large for a 64-bit integer when you reach $21!$. In probability calculations factorials usually cancel; in algorithms you precompute them modulo a prime.

Choosing $r$ from $n$: $P(n,r)$

What if we only fill $r$ slots out of $n$ available items? The same logic applies, but we stop after $r$ stages:

$P(n,r) = n \cdot (n-1) \cdots (n - r + 1) = \dfrac{n!}{(n - r)!}.$

The denominator $(n-r)!$ "cancels" the factors we never used.

Worked: Olympic podium

Eight runners compete in a 100m final. How many ways are the gold, silver, and bronze medals awarded?

Order matters: gold–silver–bronze is different from silver–gold–bronze. With $n = 8$ and $r = 3$:

$P(8, 3) = \dfrac{8!}{5!} = 8 \cdot 7 \cdot 6 = 336.$

Worked: 4-digit PIN with no repeated digits

How many 4-digit PINs use digits 0–9 with no digit repeated?

$P(10, 4) = 10 \cdot 9 \cdot 8 \cdot 7 = 5040.$ Note that this is order-sensitive: PIN 1234 differs from 4321.

Permutations of Indistinguishable Objects

What if some of the objects are identical? Counting all $n!$ orderings now overcounts, because swapping two identical objects produces the same arrangement.

Why divide by $n_1! n_2! \cdots n_k!$?

Pretend, for a moment, that all $n$ objects are distinct (label the identical As as $A_1, A_2, \dots$; do the same for each repeated letter). There are $n!$ ordered arrangements of these labeled objects.

Now, group two arrangements together if they look the same once we erase the labels. How many labeled arrangements correspond to one unlabeled arrangement? We could permute the $n_1$ labels among the type-1 positions in $n_1!$ ways, the $n_2$ labels among the type-2 positions in $n_2!$ ways, and so on. So each unlabeled arrangement maps to $n_1! n_2! \cdots n_k!$ labeled ones. Dividing $n!$ by that count gives the unlabeled total.

Ross 1.3a — PEPPER

How many distinct ordered arrangements of the letters in the word PEPPER are there?

The word has $n = 6$ letters: P, P, P, E, E, R. So $n_1 = 3$ Ps, $n_2 = 2$ Es, $n_3 = 1$ R, summing to 6. The count is

$\dfrac{6!}{3!\,2!\,1!} = \dfrac{720}{6 \cdot 2 \cdot 1} = 60.$

Ross 1.3b — MISSISSIPPI

How many distinct arrangements are there of the letters in MISSISSIPPI?

$n = 11$ with $n_1 = 1$ M, $n_2 = 4$ Is, $n_3 = 4$ Ss, $n_4 = 2$ Ps. So

$\dfrac{11!}{1! \cdot 4! \cdot 4! \cdot 2!} = \dfrac{39{,}916{,}800}{1 \cdot 24 \cdot 24 \cdot 2} = 34{,}650.$

Circular Permutations

Suppose we seat $n$ people around a round table. Two seatings that are rotations of each other are considered the same — what matters is who sits next to whom, not the absolute orientation of the table.

If we naively used $n!$, we would overcount each arrangement $n$ times, once per rotation. So:

An equivalent and often cleaner argument: fix one person at a designated seat. The remaining $n - 1$ people can be arranged in the other $n - 1$ seats in $(n-1)!$ ways.

Worked: round table

How many distinct seatings are there for 6 people around a round table?

$(6 - 1)! = 5! = 120.$

Why It Works (And When It Breaks)

Every permutation formula in this post is the same idea: count too much, then divide by the symmetry you do not care about.

This pattern — overcount, then divide — is the workhorse of all of combinatorics. We will reuse it in Part 4 to derive $\binom{n}{r}$ from $P(n,r)$.

A Note on Computing Permutations

For probability problems you usually leave permutations symbolic. For algorithms, you almost always need them modulo a large prime. The trick is to precompute factorials and inverse factorials once:

// O(N) precomputation, O(1) per query.
const int MAXN = 1'000'001;
const long long MOD = 1'000'000'007;
long long fact[MAXN], invFact[MAXN];

long long modpow(long long b, long long e, long long m) {
    long long r = 1;
    b %= m;
    while (e) {
        if (e & 1) r = r * b % m;
        b = b * b % m;
        e >>= 1;
    }
    return r;
}

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
    invFact[MAXN-1] = modpow(fact[MAXN-1], MOD - 2, MOD);
    for (int i = MAXN-2; i >= 0; i--) invFact[i] = invFact[i+1] * (i+1) % MOD;
}

long long P(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[n-r] % MOD;
}

Common Mistakes

• Using $n!$ when objects are not all distinct. Always check whether some objects look identical.
• Treating circular and linear seatings the same. Round tables divide by $n$.
• Forgetting the “ordered” part of $P(n,r)$. If order does not matter, you want combinations, not permutations.
• Off-by-one inside factorials. $P(n,r) = n!/(n-r)!$ has $r$ factors $n, n-1, \dots, n-r+1$, not $n - r$ factors.
• Computing factorials directly in code. Use modular precomputation to avoid overflow.

Summary

• $n$ distinct objects in a row: $n!$.
• $r$ chosen from $n$, order matters: $P(n, r) = n!/(n-r)!$.
• $n$ objects with groups of $n_1, n_2, \dots, n_k$ identicals: $n!/(n_1! \cdots n_k!)$.
• $n$ objects around a circle: $(n-1)!$, halved further if reflections count too.

Practice Problems

• Ross 1.10. In how many ways can 8 people be seated in a row if (a) there are no restrictions, (b) persons A and B must sit next to each other, (c) there are 4 men and 4 women and no two men or two women can sit next to each other?
• Ross 1.13. Consider a group of 20 people. If everyone shakes hands with everyone else, how many handshakes take place? preview of combinations
• Ross 1.16. Determine the number of vectors $(x_1, \dots, x_n)$ such that each $x_i$ is a positive integer and $\sum x_i = k$ where $k \ge n$. preview of stars and bars
• Practice — anagrams. How many distinct anagrams of the word PROBABILITY exist?
• Practice — round table with constraint. Eight friends sit at a round table. Two of them refuse to sit next to each other. How many seatings are valid?
• LeetCode 31 — Next Permutation. Generate the next lexicographic permutation in-place. A useful exercise in why the lexicographic order on permutations exists.
• LeetCode 60 — Permutation Sequence. Find the $k$-th permutation directly using factorial-base reasoning.