Permutations

In this lesson you’ll learn what a permutation is, how factorials work, the formula for arranging $r$ items out of $n$, how to handle arrangements with repeated identical items, and how circular arrangements differ.

A permutation is an arrangement of objects in a specific order. Order is the defining feature. ABC and CBA are different permutations of the same three letters.

The number of ways to arrange all $n$ distinct objects in a row is

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

Why? The first position has $n$ candidates, the second has $n-1$ (one is used up), and so on down to 1. Multiplication principle.

$$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$$

By definition,

$$0! = 1$$

That looks arbitrary but it isn’t. There’s exactly one way to arrange nothing: the empty arrangement. Defining $0! = 1$ also makes every formula below work at its boundaries without special-casing.

Factorials get large fast. $10! = 3{,}628{,}800$ and $20!$ is about $2.4 \times 10^{18}$. This is why “just try every ordering” is not an algorithm.

To arrange only $r$ of the $n$ objects:

$$P(n, r) = \frac{n!}{(n-r)!}$$

Also written $_nP_r$ or $P^n_r$.

Where it comes from: you’re filling $r$ positions, with $n$ choices for the first, $n-1$ for the second, down to $n - r + 1$ for the last:

$$P(n,r) = n(n-1)(n-2)\cdots(n-r+1)$$

Dividing $n!$ by $(n-r)!$ cancels off exactly the tail you don’t want.

$$P(8,3) = \frac{8!}{5!} = 8 \times 7 \times 6 = 336$$

Two boundary cases worth noting: $P(n, n) = \frac{n!}{0!} = n!$, and $P(n, 0) = 1$.

In practice, don’t compute the big factorials. Just multiply $r$ descending terms starting at $n$.

If some objects are identical, many “different” arrangements look the same, and you’ve overcounted.

For $n$ objects where $n_1$ are of one identical type, $n_2$ of another, and so on:

$$\frac{n!}{n_1! \, n_2! \cdots n_k!}$$

The reasoning: treat all objects as distinct to get $n!$, then divide out the arrangements you can’t tell apart. The $n_1$ copies of the first type can be shuffled $n_1!$ ways with no visible change, so divide by $n_1!$, and similarly for each type.

Classic example, the word LEVEL: 5 letters with L twice, E twice, V once.

$$\frac{5!}{2! \, 2! \, 1!} = \frac{120}{4} = 30$$

Arranging $n$ people around a round table is different, because a rotation of an arrangement is usually considered the same arrangement. There’s no “first seat.”

$$(n-1)!$$

Why: fix one person anywhere to kill the rotational freedom, then arrange the remaining $n-1$ relative to them. Equivalently, $n!$ linear arrangements divided by the $n$ rotations that produce each circular one.

If reflections also count as identical (a bracelet you can flip over, rather than a table), divide by 2 more:

$$\frac{(n-1)!}{2}$$

Two standard techniques.

• Items must be together - glue them into a single block, arrange the blocks, then multiply by the internal arrangements of the block.
• Items must be separated - count the total and subtract the together case, or place the unrestricted items first and slot the restricted ones into the gaps.

Example 1: Full arrangement.

How many ways can 7 books be arranged on a shelf?

Solution. All 7 distinct, order matters:

$$7! = 5{,}040$$

Example 2: Partial arrangement.

A club of 12 members elects a president, vice president, and treasurer. No person holds two offices. How many outcomes?

Solution. Order matters, because the roles are different.

$$P(12, 3) = 12 \times 11 \times 10 = 1{,}320$$

Compare: if you were just picking a 3-person committee with no roles, order would not matter and the answer would be 220. That’s the next lesson.

Example 3: Repeated letters.

How many distinct arrangements of the letters in MISSISSIPPI?

Solution. 11 letters total: M (1), I (4), S (4), P (2).

$$\frac{11!}{1! \, 4! \, 4! \, 2!} = \frac{39{,}916{,}800}{1 \times 24 \times 24 \times 2} = \frac{39{,}916{,}800}{1{,}152} = 34{,}650$$

Without the correction you’d claim $11! \approx 40$ million arrangements, over a thousand times too many.

Example 4: Circular arrangement.

Eight people sit around a round table. How many distinct seatings if rotations are considered the same?

Solution.

$$(8-1)! = 7! = 5{,}040$$

If instead the seats were numbered (so rotating produces a genuinely different seating), the answer would be $8! = 40{,}320$.

Example 5: Must be together.

In how many ways can 6 people line up if two specific people, Ana and Ben, must stand next to each other?

Solution. Treat Ana-Ben as one block. Now you have 5 units to arrange:

$$5! = 120$$

Within the block, Ana and Ben can be in 2 orders:

$$120 \times 2 = 240$$

Example 6: Must be apart.

Same 6 people. How many ways if Ana and Ben must not be adjacent?

Solution. Complement rule. Total arrangements minus the adjacent ones:

$$6! - 240 = 720 - 240 = 480$$

Example 7: A restriction on position.

How many 5-letter arrangements of the letters in DIGITS start with a vowel?

Solution. DIGITS has 6 letters: D, I, G, I, T, S, with I appearing twice. We’re arranging 5 of the 6, which makes this messier than it looks, so let’s simplify to arranging all 6 letters starting with a vowel.

The only vowel is I, and there are two identical copies. Fix an I in the first position. The remaining 5 letters are D, G, I, T, S, all distinct:

$$5! = 120$$

Because the two I’s are identical, fixing “an I” first counts each distinct word once, so the answer is 120. Watch for the trap of multiplying by 2 for the “two choices of I” - those choices produce identical words.

Any problem of the form “in what order?” is a permutation problem. Scheduling job interviews, ordering tasks in a build pipeline, and seating charts all count this way.

The traveling salesman problem is the famous cautionary tale. Visiting $n$ cities in some order gives $(n-1)!/2$ distinct routes. For 20 cities that’s over $6 \times 10^{16}$. Checking them all at a billion per second takes roughly two years, which is why this problem is attacked with heuristics rather than brute force.

Cryptography and security estimate work factors with permutations. Shuffling a deck of 52 cards yields $52! \approx 8 \times 10^{67}$ orderings, which is a genuinely staggering number and the reason a well-shuffled deck has almost certainly never occurred before in history.

Genomics counts sequence arrangements. Playlist ordering, tournament brackets, DNA fragment assembly, and anagram generators all use this math too.

The repeated-items formula shows up in probability, where it computes the number of distinct outcomes when several results are indistinguishable, like the number of ways to get exactly 3 heads in 10 coin flips.