Permutation Formulas

Why This Matters

Permutation formulas are the backbone of counting problems where order matters—and 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. Master these formulas, and you'll have a toolkit for tackling any arrangement problem thrown at you.

---

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)!}$—counts arrangements of $r$ objects selected from $n$ distinct objects where order matters
• Factorial notation represents successive multiplication: you have $n$ choices for the first position, $(n-1)$ for the second, 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

Permutations with Repetition

• $n^r$—applies when you can reuse objects, giving $n$ independent choices for each of $r$ positions
• Each position is independent, meaning your choice for one slot doesn't affect options for another
• Classic examples include PIN codes, 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!}$—the multinomial coefficient for arranging $n$ objects when groups of size $n_1, n_2, \ldots, n_k$ are identical
• Dividing by 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"—you divide by $4!$ for the S's, $4!$ for the I's, and $2!$ for the P's

Circular Permutations

• $(n-1)!$—counts arrangements of $n$ objects in a circle where rotations are considered identical
• Fixing one object breaks the rotational symmetry, reducing the problem to arranging $(n-1)$ remaining objects linearly
• Watch for reflections: if the circle can be flipped (like a bracelet vs. 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!}$—counts permutations where every object moves from its starting position
• Inclusion-exclusion alternates between adding and subtracting: start with all permutations, remove those with at least one fixed point, add back those with at least two, and so on
• Quick approximation: $!n \approx \frac{n!}{e}$, which becomes increasingly accurate as $n$ grows

Partial Derangements

• $D(n,k) = \binom{n}{k} \cdot !(n-k)$—counts arrangements where exactly $k$ objects stay fixed and the rest are deranged
• Two-step process: first choose which $k$ objects remain fixed ($\binom{n}{k}$), then derange the remaining $(n-k)$ objects
• Useful for problems asking "how many arrangements have exactly 2 items in their original positions?"

---

Restricted and Structured Permutations

These concepts handle constraints, ordering systems, and algebraic properties of permutations.

Permutations with Forbidden Positions

• Complementary counting often works best: calculate total arrangements minus arrangements that violate the restriction
• Inclusion-exclusion handles multiple restrictions by accounting for overlaps between forbidden cases
• Rook polynomials provide a systematic approach for complex forbidden-position problems on a grid

Lexicographic Order

• Dictionary ordering arranges permutations by comparing elements left-to-right, just like alphabetizing words
• Finding the $k$th permutation uses factorial decomposition: determine each position by dividing $k$ by $(n-1)!$, $(n-2)!$, etc.
• Counting predecessors tells you a permutation's rank—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$
• Inversion count measures how "out of order" a permutation is—the identity permutation has 0 inversions; the reverse has $\binom{n}{2}$
• Sorting algorithms like bubble sort perform exactly as many swaps as there are inversions

Permutation Groups and Cycle Notation

• Cycle notation writes a permutation as disjoint cycles: $(1\ 3\ 2)(4\ 5)$ means $1 \to 3 \to 2 \to 1$ and $4 \to 5 \to 4$
• Permutation composition combines two permutations by applying them in sequence, forming a group structure
• Cycle type determines key properties: the order of a permutation equals the LCM of its cycle lengths

---

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.