Key Concepts of Permutations

Why This Matters

Permutations are the backbone of algebraic combinatorics—they're not just about counting arrangements, but about understanding structure, symmetry, and transformation. When you study permutations, you're building tools that connect to group theory, linear algebra, and algorithm design. Exam questions will test whether you can move fluidly between representations (cycle notation vs. matrices), compute statistics (inversions, descents), and recognize when two seemingly different problems share the same permutation structure.

The concepts here fall into distinct categories: how we represent permutations, how we count them, how we measure their properties, and how they connect to algebraic structures. Don't just memorize that $n!$ counts permutations—understand why cycle structure determines group-theoretic properties, why inversions connect to sorting algorithms, and why pattern avoidance has become a major research area. Each concept illuminates a different facet of how order and arrangement create mathematical structure.

---

Foundations: Representation and Notation

Before analyzing permutations, you need to represent them precisely. The notation you choose affects which properties are easy to see and compute.

Definition of Permutations

• A permutation is a bijection from a finite set to itself—every element maps to exactly one image, and every element is hit exactly once
• The symmetric group $S_n$ contains all permutations of $n$ elements, forming the foundation for studying permutation structures algebraically
• Permutations encode order—the same set of objects can be arranged in fundamentally different ways, and permutations capture exactly how

Permutation Notation (One-Line and Cycle Notation)

• One-line notation lists images sequentially—if $\sigma = 3142$, then $\sigma(1)=3, \sigma(2)=1, \sigma(3)=4, \sigma(4)=2$
• Cycle notation groups elements by their orbits—$(1\ 3\ 4)(2)$ shows that 1 maps to 3, 3 maps to 4, 4 maps to 1, and 2 is fixed
• Cycle notation reveals structure that one-line notation hides—you can immediately see fixed points, cycle lengths, and how to compute powers of the permutation

Permutation Matrices

• A permutation matrix is an $n \times n$ binary matrix with exactly one 1 in each row and column, representing $\sigma$ by placing a 1 in position $(i, \sigma(i))$
• Matrix multiplication corresponds to composition—if $P_\sigma$ and $P_\tau$ are permutation matrices, then $P_\sigma P_\tau = P_{\sigma \circ \tau}$
• Permutation matrices are orthogonal—their transpose equals their inverse, connecting permutations to linear algebra and transformations

---

Counting: Factorials and Special Classes

Counting permutations goes beyond $n!$—specific constraints create important subfamilies with their own enumeration formulas.

Counting Permutations (n!)

• $n!$ counts total arrangements because you have $n$ choices for the first position, $n-1$ for the second, and so on, giving $n \cdot (n-1) \cdot \ldots \cdot 1$
• Factorial growth is extremely rapid—$10! = 3,628,800$ and $20! > 10^{18}$, which is why efficient algorithms matter
• Partial permutations $P(n,k) = \frac{n!}{(n-k)!}$ count arrangements of $k$ objects chosen from $n$, a common exam formula

Derangements

• A derangement is a permutation with no fixed points—no element stays in its original position, written $\sigma(i) \neq i$ for all $i$
• The count $D_n$ (or $!n$) satisfies $D_n = (n-1)(D_{n-1} + D_{n-2})$ and equals $n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$
• The proportion of derangements approaches $\frac{1}{e}$—as $n \to \infty$, roughly 36.8% of all permutations are derangements, a beautiful convergence result

Stirling Numbers and Their Relation to Permutations

• Stirling numbers of the first kind $c(n,k)$ (unsigned) count permutations of $n$ elements with exactly $k$ cycles
• The recursion $c(n,k) = (n-1)c(n-1,k) + c(n-1,k-1)$ reflects that element $n$ either joins an existing cycle or forms its own
• Stirling numbers bridge permutation enumeration and polynomial algebra—they appear as coefficients when expanding $(x)_n = x(x-1)\cdots(x-n+1)$

---

Measuring Disorder: Statistics and Inversions

Permutation statistics quantify how far a permutation is from sorted order or how its elements relate to their positions.

Inversions in Permutations

• An inversion is a pair $(i,j)$ with $i < j$ but $\sigma(i) > \sigma(j)$—the larger value appears before the smaller one
• The inversion number $\text{inv}(\sigma)$ ranges from 0 (identity) to $\binom{n}{2}$ (reverse permutation), measuring total disorder
• Inversions count adjacent swaps—the minimum number of transpositions of adjacent elements needed to sort $\sigma$ equals $\text{inv}(\sigma)$

Sign of a Permutation

• The sign $\text{sgn}(\sigma) = (-1)^{\text{inv}(\sigma)}$ classifies permutations as even (+1) or odd (−1)
• Even permutations form the alternating group $A_n$—a normal subgroup of $S_n$ with index 2, containing exactly half of all permutations
• Sign is multiplicative: $\text{sgn}(\sigma\tau) = \text{sgn}(\sigma)\text{sgn}(\tau)$, and it determines the sign of terms in determinant expansion

Permutation Statistics (Descents, Excedances)

• A descent at position $i$ occurs when $\sigma(i) > \sigma(i+1)$—the permutation "goes down" at that step
• An excedance at position $i$ occurs when $\sigma(i) > i$—the value exceeds its position index
• Descents and excedances are equidistributed—the number of permutations with $k$ descents equals the number with $k$ excedances, both counted by Eulerian numbers

---

Encoding and Algorithms

These concepts transform permutations into sequences or identify meaningful subsequences, enabling efficient computation.

Lehmer Code and Factorial Number System

• The Lehmer code assigns to each permutation a sequence $(c_1, \ldots, c_n)$ where $c_i$ counts elements to the right of position $i$ that are smaller than $\sigma(i)$
• Each $c_i$ satisfies $0 \leq c_i \leq n-i$—this gives a bijection between permutations and sequences, enabling ranking/unranking algorithms
• The factorial number system interprets the Lehmer code as digits: $\sum c_i \cdot i!$ gives the permutation's rank among all $n!$ permutations

Longest Increasing Subsequence

• The LIS of a permutation is the longest subsequence (not necessarily contiguous) whose elements appear in increasing order
• The LIS length connects to Young tableaux—by the Robinson-Schensted correspondence, it equals the number of rows in the associated tableau
• Expected LIS length is $\sim 2\sqrt{n}$ for random permutations—a celebrated result with deep connections to random matrix theory

---

Algebraic Structure: Groups and Symmetry

Permutations aren't just objects to count—they form groups, connecting combinatorics to abstract algebra.

Cycles and Cycle Structure

• A $k$-cycle permutes $k$ elements in a closed loop: $(a_1\ a_2\ \ldots\ a_k)$ maps $a_1 \to a_2 \to \cdots \to a_k \to a_1$
• Every permutation factors uniquely (up to order) into disjoint cycles—this cycle type determines conjugacy classes in $S_n$
• The order of a permutation equals the LCM of its cycle lengths—a permutation with cycle type $(3,2,2)$ has order $\text{lcm}(3,2,2)=6$

Permutation Groups and Cayley's Theorem

• A permutation group is a subgroup of $S_n$—any set of permutations closed under composition and inverses
• Cayley's theorem states every finite group $G$ is isomorphic to a subgroup of $S_{|G|}$, via the left regular representation
• This theorem is foundational—it means studying permutation groups is equivalent to studying all finite groups, making $S_n$ the "universal" finite group

---

Patterns and Probabilistic Behavior

Modern permutation theory studies which patterns appear, which are avoided, and what happens "on average."

Permutation Patterns and Pattern Avoidance

• A pattern $\pi$ appears in $\sigma$ if some subsequence of $\sigma$ has the same relative order as $\pi$—e.g., 231 appears in 35142 via positions 3,5,2
• Pattern avoidance counts permutations in $S_n$ containing no copy of $\pi$—remarkably, avoiding 132, 231, 312, etc., all give the Catalan numbers
• The Stanley-Wilf conjecture (now theorem) states that for any pattern $\pi$, the number of avoiding permutations grows at most exponentially

Random Permutations and Their Properties

• A uniform random permutation is drawn with probability $\frac{1}{n!}$ from $S_n$—generated efficiently by the Fisher-Yates shuffle
• Expected number of cycles in a random permutation is $H_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n} \approx \ln n$
• Expected number of fixed points is exactly 1 for any $n$—a surprising result that follows from linearity of expectation

---

Quick Reference Table

---

Self-Check Questions

1. A permutation has cycle type $(4, 2, 1)$. What is its order, and is it even or odd?

2. Compare inversions and descents: which statistic determines the sign of a permutation, and why can a permutation have 10 inversions but only 2 descents?

3. Explain why the number of derangements of $n$ elements divided by $n!$ approaches $\frac{1}{e}$. What inclusion-exclusion principle underlies this?

4. The Lehmer code and cycle notation both encode permutations uniquely. For what types of problems would you prefer each representation?

5. FRQ-style: Let $\sigma = 41523$. (a) Write $\sigma$ in cycle notation. (b) Compute $\text{inv}(\sigma)$ and determine $\text{sgn}(\sigma)$. (c) Find the longest increasing subsequence of $\sigma$.