Permutation Formulas

Why This Matters

Permutation formulas are the backbone of counting problems where order matters. Recognizing when order matters is half the battle on any combinatorics exam. You're being tested on your ability to identify which formula applies to a given scenario: Is repetition allowed? Are some objects identical? Are there forbidden positions?

Each formula exists because a specific constraint changes how we count. Don't just memorize $P(n,r) = \frac{n!}{(n-r)!}$ and call it a day. You need to understand why we divide, why we subtract, and why circular arrangements behave differently from linear ones. The concepts here (overcounting corrections, symmetry elimination, inclusion-exclusion) appear throughout discrete mathematics and give you a toolkit for tackling any arrangement problem.

---

Linear Arrangements: The Foundation

These formulas handle the most common scenario: arranging objects in a line or sequence where position matters. The key principle is that each successive choice has fewer options available.

Basic Permutation Formula

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

This counts arrangements of $r$ objects selected from $n$ distinct objects where order matters. The factorial structure reflects successive multiplication: you have $n$ choices for the first position, $(n-1)$ for the second, and so on down to $(n-r+1)$ for the last.

Use this when each object can only be used once and every object is distinguishable from the others.

For example, choosing a president, vice president, and treasurer from a club of 10 people gives $P(10,3) = \frac{10!}{7!} = 10 \times 9 \times 8 = 720$.

Permutations with Repetition

$n^r$

This applies when you can reuse objects, giving $n$ independent choices for each of $r$ positions. Your choice for one slot doesn't affect options for another. Classic examples include PIN codes (10 digits, 4 positions = $10^4 = 10{,}000$), license plates, and any scenario where "replacement" is allowed.

---

Correcting for Overcounting

When objects are identical or positions are equivalent, the basic formula overcounts. These formulas divide out the redundant arrangements.

Permutations with Indistinguishable Objects

$\frac{n!}{n_1! \cdot n_2! \cdot \ldots \cdot n_k!}$

This is the multinomial coefficient for arranging $n$ objects when groups of size $n_1, n_2, \ldots, n_k$ are identical. Dividing by the factorials eliminates arrangements that look the same, because swapping identical objects doesn't create a new permutation.

The classic example is counting arrangements of "MISSISSIPPI" (11 letters total). You divide $11!$ by $4!$ for the four S's, $4!$ for the four I's, $2!$ for the two P's, and $1!$ for the single M:

$\frac{11!}{4! \cdot 4! \cdot 2! \cdot 1!} = 34{,}650$

Note that $n_1 + n_2 + \cdots + n_k$ must equal $n$. Every object needs to belong to exactly one group.

Circular Permutations

$(n-1)!$

This counts arrangements of $n$ objects in a circle where rotations are considered identical. The reasoning: fix one object in place to break the rotational symmetry, then arrange the remaining $(n-1)$ objects linearly. For 6 people around a round table, that's $5! = 120$ (not $6! = 720$).

Watch for reflections: if the circle can be flipped (like a bracelet that you can turn over, as opposed to people seated at a fixed table), divide by 2 to get $\frac{(n-1)!}{2}$.

---

Derangements: When Nothing Stays Put

Derangements count permutations where no element remains in its original position. These problems use inclusion-exclusion to subtract out forbidden arrangements.

Derangements (Subfactorial)

$!n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}$

This counts permutations where every object moves from its starting position. The inclusion-exclusion logic works like this:

1. Start with all $n!$ permutations.
2. Subtract permutations where at least one element is fixed: $\binom{n}{1}(n-1)!$
3. Add back permutations where at least two elements are fixed (you subtracted these twice): $\binom{n}{2}(n-2)!$
4. Continue alternating signs until you've accounted for all overlaps.

A quick approximation: $!n \approx \frac{n!}{e}$, rounded to the nearest integer. This becomes increasingly accurate as $n$ grows. For small values: $!1 = 0$, $!2 = 1$, $!3 = 2$, $!4 = 9$, $!5 = 44$.

Partial Derangements

$D(n,k) = \binom{n}{k} \cdot !(n-k)$

This counts arrangements where exactly $k$ objects stay fixed and the rest are deranged. The logic is a two-step process:

1. Choose which $k$ objects remain fixed: $\binom{n}{k}$ ways.
2. Derange the remaining $(n-k)$ objects: $!(n-k)$ ways.

This is the formula you need when a problem asks something like "how many arrangements of $\{1,2,3,4,5\}$ have exactly 2 items in their original positions?"

---

Restricted and Structured Permutations

These concepts handle constraints, ordering systems, and more complex counting scenarios.

Permutations with Forbidden Positions

There's no single clean formula here. Instead, you choose a strategy based on the problem:

• Complementary counting often works best for simple restrictions: calculate total arrangements minus arrangements that violate the restriction. For example, "arrangements of $\{1,2,3,4\}$ where 1 is not first" = $4! - 3! = 18$.
• Inclusion-exclusion handles multiple restrictions by accounting for overlaps between forbidden cases. If elements $a$, $b$, and $c$ each have one forbidden position, you subtract cases where each violates its restriction, add back cases where pairs violate simultaneously, and subtract the triple overlap.
• Rook polynomials provide a systematic approach for complex forbidden-position problems on a grid, where you're placing non-attacking rooks on allowed squares.

Lexicographic Order

Lexicographic order arranges permutations by comparing elements left-to-right, just like alphabetizing words. For $\{1,2,3\}$, the order is: 123, 132, 213, 231, 312, 321.

Finding the $k$th permutation uses factorial decomposition:

1. Determine the first element by computing $\lfloor k / (n-1)! \rfloor$ (adjusting for 0-indexing).
2. Use the remainder to determine the second element by dividing by $(n-2)!$.
3. Continue until all positions are filled.

Counting predecessors tells you a permutation's rank, which is useful for encoding permutations as single integers.

---

Permutation Structure and Properties

Understanding the internal structure of permutations reveals deeper patterns and connects to abstract algebra.

Inversions in Permutations

An inversion is a pair $(i, j)$ where $i < j$ but the element at position $i$ is greater than the element at position $j$. The inversion count measures how "out of order" a permutation is.

• The identity permutation $(1, 2, 3, \ldots, n)$ has 0 inversions.
• The reverse permutation $(n, n-1, \ldots, 1)$ has $\binom{n}{2}$ inversions, the maximum possible.
• Sorting algorithms like bubble sort perform exactly as many adjacent swaps as there are inversions.

For example, the permutation $(3, 1, 2)$ has two inversions: $(3,1)$ and $(3,2)$.

Permutation Groups and Cycle Notation

Cycle notation writes a permutation as disjoint cycles. For instance, $(1\ 3\ 2)(4\ 5)$ means $1 \to 3$, $3 \to 2$, $2 \to 1$, and $4 \to 5$, $5 \to 4$. Elements not appearing in any cycle are fixed points.

Permutation composition combines two permutations by applying them in sequence. The set of all permutations of $n$ elements forms the symmetric group $S_n$, which is a central object in abstract algebra.

The cycle type of a permutation determines key properties. Most importantly, the order of a permutation (the number of times you must apply it to return to the identity) equals the LCM of its cycle lengths. For $(1\ 3\ 2)(4\ 5)$, the cycle lengths are 3 and 2, so the order is $\text{lcm}(3,2) = 6$.

---

Quick Reference Table

---

Self-Check Questions

1. You're arranging 5 people in a line versus around a circular table. Which formula applies to each, and why does the circular case give fewer arrangements?

2. The word "BANANA" has 6 letters. Why can't you just use $6!$ to count its arrangements, and what's the correct formula?

3. Compare $P(10, 3)$ and $10^3$: what real-world scenario would use each formula?

4. If you're asked to count permutations of $\{1, 2, 3, 4, 5\}$ where exactly 2 elements remain in their original positions, which formula do you need and what's your setup?

5. A problem asks: "How many arrangements of $\{1, 2, 3, 4\}$ have the property that 1 is not in position 1 and 2 is not in position 2?" Explain why you'd use inclusion-exclusion rather than a single formula.