Chapter 8: Permutation Structure

What changes when permutations are classified by cycles or descents?

Counting all permutations gives $n!$, but many questions ask how those permutations behave. If labels represent objects and a permutation tells us where each object moves, its cycles describe repeated movement. If the same permutation is read as a list, its descents describe local drops and its inversions measure disorder across pairs.

These are different views of the same finite set. This chapter develops counting recurrences by inserting or removing the largest label, then uses them to compare distributions. Begin with permutations and combinations, the enumeration methods in algorithmic generation, and the distinction between labeled and unlabeled structures in partitions and structure types.

8.1 Cycle decompositions and Stirling numbers of the first kind

Write $[n]=\{1,\ldots,n\}$ and let $S_n$ be the set of bijections $\pi:[n]\to[n]$. The one-line notation $\pi_1\cdots\pi_n$ records $\pi_i=\pi(i)$. To find a cycle, start at an unused label and repeatedly apply $\pi$. Because the map is a bijection on a finite set, this process returns to its starting label. Repeat with unused labels until every label is included.

The notation $(a_1a_2\cdots a_r)$ means $a_1\to a_2\to\cdots\to a_r\to a_1$. Rotating the notation represents the same cycle; changing its orientation generally changes the permutation. Disjoint cycles can be written in any order. Include fixed points as cycles of length one when counting cycles.

Worked example. For $\pi=2413$, the trace is $1\to2\to4\to3\to1$, so its decomposition is $(1243)$. The entry $4$ is an image, not the statement that the fourth position is fixed.

Let $c(n,k)$ count permutations in $S_n$ with exactly $k$ cycles. These are the unsigned Stirling numbers of the first kind. There is one empty permutation with zero cycles, so $c(0,0)=1$; impossible indices have count zero. In particular, $c(n,0)=0$ for $n\ge1$.

Insert the label $n$ into a permutation of $[n-1]$. There are two disjoint possibilities:

1. Make $(n)$ a singleton cycle. The smaller permutation must have $k-1$ cycles.
2. Insert $n$ after an existing label $a$: replace $a\to b$ by $a\to n\to b$. There are $n-1$ choices of $a$, and the number of cycles stays $k$.

Removing $n$ reverses exactly one of these constructions. Thus, for $n\ge1$,

$$ c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k). $$

Starting with $c(0,0)=1$ gives:

For instance, $c(4,2)=c(3,1)+3c(3,2)=2+9=11$. Each row sums to $n!$ because every permutation has exactly one cycle count.

If $t$ is a formal variable, multiplying the recurrence by $t^k$ and summing yields

$$ \sum_{k=0}^{n}c(n,k)t^k=t(t+1)\cdots(t+n-1), $$

with empty product $1$ when $n=0$. This polynomial records the whole cycle distribution. Some texts use signed numbers $s(n,k)=(-1)^{n-k}c(n,k)$. State which convention you use. The Stirling numbers of the second kind from Chapter 7 count set partitions; here each block also has a cyclic order.

Exercise. Find $c(5,4)$ without listing all $120$ permutations. Hint: four cycles on five labels force a single nontrivial cycle. Answer: choose its two labels, giving $\binom52=10$; the recurrence gives $c(4,3)+4c(4,4)=6+4=10$.

8.2 Permutations with restricted cycle structure

A cycle type specifies numbers $m_j$, where $m_j$ is the number of cycles of length $j$. Necessarily

$$ \sum_{j=1}^{n}j m_j=n. $$

For a fixed feasible type, the number of permutations is

$$ \frac{n!}{\displaystyle\prod_{j=1}^{n}j^{m_j}m_j!}. $$

To prove this, fix slots for the cycles, grouped by length. Arrange the labels in a list and cut it into the prescribed slots. There are $n!$ lists. Each length-$j$ cycle can be rotated in $j$ ways without changing it, giving the factor $j^{m_j}$. The $m_j$ cycles of the same length can be exchanged among their slots, giving $m_j!$. All labels are distinct, so these representation choices have exactly the stated multiplicity.

This formula makes restrictions precise. To forbid fixed points, impose $m_1=0$. To allow only cycles of lengths one and two, impose $m_j=0$ for $j\ge3$. Sum the type counts over all feasible vectors satisfying the restriction.

Worked example. On five labels, the type consisting of one 3-cycle and one 2-cycle has count $5!/(3\cdot2)=20$. Equivalently, choose the three labels in $\binom53=10$ ways, give them one of two cyclic orientations, and use the remaining two labels in their unique 2-cycle.

Exercise. How many permutations of $[5]$ consist of a single cycle? Hint: fix the first displayed label as $1$ to remove rotational ambiguity. Answer: $4!=24$, agreeing with $5!/5$.

8.3 Derangements and involutions

A derangement has no fixed point: $\pi(i)\ne i$ for every label. Its cycles all have length at least two. An involution satisfies $\pi^2=\mathrm{id}$, meaning that applying it twice returns every label to itself. Its cycles have length one or two: a longer cycle does not return a label after two steps.

These conditions can overlap. In the diagram, each arrow represents one application of the permutation. A loop marks a fixed point, and two opposite arrows mark a 2-cycle. The left permutation is a derangement but not an involution; the middle is an involution but not a derangement; the right satisfies both.

Let $D_n$ count derangements. Set $D_0=1$ and $D_1=0$. For $n\ge2$, choose $j=\pi(1)$ in $n-1$ ways. If $1$ and $j$ form a 2-cycle, removing them leaves a derangement on $n-2$ labels. Otherwise, remove $1$ from its longer cycle by joining its predecessor directly to $j$. The result is a derangement on the remaining $n-1$ labels. Conversely, insert $1$ immediately before $j$ in any such derangement. Therefore

$$ D_n=(n-1)(D_{n-1}+D_{n-2}). $$

This gives $D_2=1$, $D_3=2$, and $D_4=9$. As a separate check, inclusion–exclusion on the events “label $i$ is fixed” gives

$$ D_n=\sum_{j=0}^{n}(-1)^j\binom nj(n-j)! =n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}. $$

Here a chosen set of $j$ fixed labels leaves $(n-j)!$ unrestricted permutations, explaining each term.

Let $I_n$ count involutions. Set $I_0=I_1=1$. Label $1$ is either fixed or paired with one of the other $n-1$ labels, so

$$ I_n=I_{n-1}+(n-1)I_{n-2}\qquad(n\ge2). $$

An involution with $j$ transpositions has type $2^j1^{n-2j}$, hence

$$ I_n=\sum_{j=0}^{\lfloor n/2\rfloor}\frac{n!}{2^j j!(n-2j)!}. $$

For $n=4$, this is $1+6+3=10$. Only the three involutions of type $2+2$ are also derangements, agreeing with the previous table.

Exercise. Count fixed-point-free involutions on six labels. Hint: every cycle must have length two. Answer: $6!/(2^3 3!)=15$. On an odd number of labels the count is zero; on $2m$ labels it is $(2m)!/(2^m m!)$.

8.4 Descents, ascents, and Eulerian numbers

For a nonempty permutation, define its descent set and descent number by

$$ \operatorname{Des}(\pi)=\{i:1\le i\lt n,\ \pi_i>\pi_{i+1}\}, \qquad \operatorname{des}(\pi)=|\operatorname{Des}(\pi)|. $$

An ascent satisfies $\pi_i\lt\pi_{i+1}$. Distinct entries guarantee that each of the $n-1$ adjacent comparisons is exactly one of these, so the ascent and descent numbers sum to $n-1$. For $3142$, the descent positions are $1$ and $3$, while position $2$ is an ascent.

The Eulerian number $A(n,k)$ counts permutations with $k$ descents. Use $A(0,0)=1$, $A(1,0)=1$, and zero for impossible indices. For $n\ge2$,

$$ A(n,k)=(k+1)A(n-1,k)+(n-k)A(n-1,k-1). $$

To prove it, insert the largest label $n$ into one of the $n$ gaps of a permutation of length $n-1$. If the old permutation has $d$ descents, inserting into a descent gap replaces one drop by one drop; appending at the end also preserves $d$. These are $d+1$ gaps. Inserting into an ascent gap creates a new descent, as does inserting at the front. These are the other $n-1-d$ gaps.

To finish with $k$ descents, start either with $k$ and preserve them in $k+1$ ways, or with $k-1$ and increase the count in $n-k$ ways. Deleting $n$ reverses the construction.

Worked example. The row for $n=3$ is $1,4,1$. Therefore

$$ A(4,1)=2\cdot4+3\cdot1=11, \qquad A(4,2)=3\cdot1+2\cdot4=11. $$

The full row is $1,11,11,1$, summing to $24$. Replacing every value $x$ by $n+1-x$ exchanges ascents and descents, proving $A(n,k)=A(n,n-1-k)$ for $n\ge1$.

Exercise. Insert $4$ into $213$. Which insertions preserve its one descent? Hint: inspect the existing descent gap and the end. Answer: $2413$ and $2134$ preserve it; $4213$ and $2143$ have two descents.

8.5 Inversions and permutation statistics

A permutation statistic is a numerical measurement assigned to each permutation. An inversion is a pair of positions $(i,j)$ with $i\lt j$ and $\pi_i>\pi_j$. Define

$$ \operatorname{inv}(\pi)=\#\{(i,j):1\le i\lt j\le n,\ \pi_i>\pi_j\}. $$

Descents compare neighbors; inversions compare all pairs. The major index weights descent positions:

$$ \operatorname{maj}(\pi)=\sum_{i\in\operatorname{Des}(\pi)}i. $$

Worked example. For $3142$, the inversion pairs of positions are $(1,2)$, $(1,4)$, and $(3,4)$, corresponding to value pairs $(3,1)$, $(3,2)$, and $(4,2)$. Thus its inversion number is $3$, descent number is $2$, and major index is $1+3=4$.

The inversion and major-index columns have the same frequency distribution, although their values differ on individual permutations. Section 8.8 proves that this agreement holds for every $S_n$.

The Lehmer digits from Chapter 5 count smaller entries to the right of each position. Their sum is $\operatorname{inv}(\pi)$, since each inversion is counted once by its left position. Exchanging an adjacent inverted pair lowers the inversion count by exactly one: all comparisons with other entries contribute the same total before and after the exchange. Repeatedly exchanging such pairs eventually sorts the list, using exactly $\operatorname{inv}(\pi)$ exchanges. No adjacent exchange changes the count by more than one, so fewer cannot suffice.

If arbitrary pairs of positions may be exchanged, the minimum is instead $n-\operatorname{cyc}(\pi)$, where $\operatorname{cyc}$ denotes the number of cycles. A transposition either joins two cycles or splits one, changing the count by one. Reaching the identity, with $n$ cycles, therefore needs at least this many exchanges. A length-$r$ cycle can be undone in $r-1$ exchanges, attaining the bound after summing over all cycles.

For $321=(13)(2)$, one arbitrary exchange sorts the list, while three adjacent exchanges are necessary. This distinction matters when a rearrangement system permits only neighboring moves.

Exercise. Find the three statistics for $2413$. Hint: list the smaller entries to the right of each position. Answer: its descent set is $\{2\}$, inversion count is $1+2+0+0=3$, and major index is $2$.

8.6 Pattern-avoiding permutations

Optional extension. This section is not required for the chapter foundation. A classical pattern concerns relative order in a subsequence; its selected positions need not be adjacent.

A permutation contains the pattern $132$ if some positions $i\lt j\lt k$ satisfy

$$ \pi_i\lt\pi_k\lt\pi_j. $$

It avoids $132$ if no such triple exists. For example, $2413$ contains it at positions $1,2,4$: the values $2,4,3$ have relative order $1,3,2$. On three labels, only the permutation $132$ contains this pattern, so five permutations avoid it.

Let $C_n$ count $132$-avoiding permutations of $[n]$, with $C_0=1$. Place the largest value $n$ between a left block $L$ and a right block $R$. Every value in $L$ must exceed every value in $R$: otherwise a smaller left value, $n$, and a larger right value form $132$.

If $L$ has length $\ell$, its labels are therefore the largest $\ell$ labels remaining, and $R$ receives the smallest $n-1-\ell$. Standardizing a block means replacing its smallest value by $1$, its next-smallest by $2$, and so on. Both standardized blocks must avoid $132$, giving $C_\ell C_{n-1-\ell}$ choices.

Conversely, assemble any two avoiding blocks with these label sets around $n$. A pattern entirely within a block is excluded. A triple meeting both blocks but excluding $n$ cannot be $132$, since its first entry belongs to the larger-valued left block and is not the smallest. A triple involving $n$ would need $n$ in its middle position and a left value smaller than a right value, which is also excluded. This proves the converse and the recurrence

$$ C_n=\sum_{\ell=0}^{n-1}C_\ell C_{n-1-\ell}\qquad(n\ge1). $$

These are the Catalan numbers, beginning $1,1,2,5,14,42,132$ for $n=0$ through $6$. The recurrence has the same shape as splitting an ordered binary tree at its root into left and right subtrees.

Worked example. For $n=4$, split by the number of entries left of $4$. The contributions are $1\cdot5$, $1\cdot2$, $2\cdot1$, and $5\cdot1$, totaling $14$. For $\ell=2$, the left labels are $\{2,3\}$ and the right label is $1$; the possibilities are $2341$ and $3241$.

Exercise. Explain why $2143$ fails to avoid $132$. Hint: the triple need not use consecutive positions. Answer: positions $1,3,4$ give $2,4,3$. Merely scanning neighboring triples would miss this occurrence.

8.7 Permutation posets and weak/Bruhat orders

Optional graduate extension. A partial order is a relation that is reflexive, antisymmetric, and transitive. A cover $u\lessdot v$ means $u\lt v$ with no element strictly between them. Hasse diagrams draw covers upward. The planned sections 17.1 on partial orders and 30.8 on Coxeter groups and Bruhat order provide fuller background; find them in the series roadmap. The definitions here require only permutations and inversion counts.

We use right weak order: its upward covers swap adjacent positions of a permutation when the inversion count increases by one. Strong Bruhat order allows any two positions to be swapped, provided the inversion count increases by exactly one. These conventions agree with the cover definitions in Stanley and Postnikov's Bruhat-order notes. math.mit.edu

In each case, define $u\le v$ when $u=v$ or an upward sequence of covers leads from $u$ to $v$. Reachability is transitive, and strictly increasing inversion counts prevent directed cycles, proving antisymmetry. Every cover raises the rank $\operatorname{inv}$ by one. This rank measures height in the order, rather than the lexicographic rank used in enumeration algorithms.

For $S_3$, all right weak covers lie on these two chains:

$$ 123\lessdot213\lessdot231\lessdot321, \qquad 123\lessdot132\lessdot312\lessdot321. $$

Strong Bruhat order has two additional covers, $213\lessdot312$ and $132\lessdot231$, each obtained by exchanging positions $1$ and $3$. Thus $213$ and $312$ are comparable in strong Bruhat order but incomparable in right weak order.

Here is a practical test for a strong cover. Suppose $i\lt j$ and the entries are $a=\pi_i\lt b=\pi_j$. Swapping them changes the inversion number by

$$ 1+2\#\{k:i\lt k\lt j,\ a\lt\pi_k\lt b\}. $$

The pair $(i,j)$ contributes one new inversion. Each intervening entry strictly between $a$ and $b$ contributes two more; other intervening entries have unchanged total contribution. Entries outside the interval also have unchanged total contribution. Consequently, the swap is a cover precisely when no intervening value lies strictly between $a$ and $b$.

Worked example. In $213$, swapping the first and third entries exchanges $2$ and $3$. The intervening value $1$ lies outside that value interval, so the inversion count rises from $1$ to $2$: this is the strong cover to $312$. In contrast, swapping the endpoints of $123$ raises the count from $0$ to $3$, so it is not a cover.

Exercise. Find the strong upward covers of $132$ and identify the right weak ones. Hint: test all three pairs of positions. Answer: the strong successors are $312$ and $231$; only $312$ is a right weak successor. The swap to $123$ goes downward. Equal inversion counts alone never establish comparability between distinct permutations.

8.8 Mahonian statistics and q-enumeration

Optional advanced extension. Here $q$ is a formal variable: its exponent records a statistic, rather than a numerical probability. Section 6.7 of binomial coefficients and identities introduces related q-analogues. The planned Section 10.1 develops generating functions; consult the series roadmap. The polynomial argument below is self-contained.

Define the q-integer $[r]_q=1+q+\cdots+q^{r-1}$ for $r\ge1$. The inversion enumerator is

$$ F_n(q)=\sum_{\pi\in S_n}q^{\operatorname{inv}(\pi)}. $$

Insert the largest label $n$ into each gap of a permutation of length $n-1$. Its new inversions are exactly the entries to its right, giving each increment $0,1,\ldots,n-1$ once. Removing $n$ is the inverse operation. Therefore

$$ F_n(q)=[n]_qF_{n-1}(q)=\prod_{r=1}^{n}[r]_q, \qquad F_0(q)=1. $$

For example, $F_3(q)=(1+q)(1+q+q^2)=1+2q+2q^2+q^3$, agreeing with the table in Section 8.5. If $M(n,s)$ is the coefficient of $q^s$, then

$$ M(n,s)=\sum_{j=0}^{n-1}M(n-1,s-j), $$

with $M(0,0)=1$ and zero for negative or impossible indices. At $q=1$ the polynomial becomes $n!$; its degree $\binom n2$ is the maximum inversion count.

A statistic is called Mahonian when it has this distribution on every $S_n$. The major index is Mahonian:

$$ \sum_{\pi\in S_n}q^{\operatorname{maj}(\pi)} =\sum_{\pi\in S_n}q^{\operatorname{inv}(\pi)}. $$

The largest-label insertion approach also appears in MIT's algebraic-combinatorics solutions. ocw.mit.edu

For completeness, take a permutation of length $m\ge1$ with $d$ descents and insert $m+1$. Appending changes the major index by zero. In a descent gap at position $i$, the descent shifts from $i$ to $i+1$, and later descents also shift; the increase equals the number of descents at or after $i$. Reading these gaps from right to left gives increments $1,\ldots,d$.

At the front, the increase is $d+1$. In an ascent gap at position $i$, it is $i+1$ plus the number of later descents. If this is the $a$th ascent gap from the left, that number is $d-i+a$, so the increase is $d+a+1$. Thus the front and ascent gaps give $d+1,\ldots,m$. All gaps together give $0,\ldots,m$ exactly once. Induction, starting with the empty permutation, proves the same q-factorial recurrence.

Worked example. The major index of $213$ is $1$. Inserting $4$ at the front, after the first entry, after the second, or at the end produces $4213,2413,2143,2134$. Their major indices are $3,2,4,1$, so the increments are $2,1,3,0$.

Exercise. Does equidistribution survive restricting to $132$-avoiding permutations? Hint: remove $132$ from the table for $S_3$. Answer: the remaining inversion enumerator is $1+q+2q^2+q^3$, while the major-index enumerator is $1+2q+q^2+q^3$. They differ. A theorem for all permutations cannot automatically be transferred to a restricted family.

Compare permutation statistics and discover a pattern-avoidance recurrence

Cycle counting and q-enumeration use the same principle: assign a weight to each permutation, then follow how a reversible insertion changes that weight. The cycle weight $t^{\operatorname{cyc}(\pi)}$ leads to the rising product $t(t+1)\cdots(t+n-1)$. The inversion weight $q^{\operatorname{inv}(\pi)}$ leads to the q-factorial $\prod_{r=1}^n[r]_q$. These products summarize different distributions on the same $n!$ objects.

To study both simultaneously, define

$$ H_n(t,q)=\sum_{\pi\in S_n}t^{\operatorname{cyc}(\pi)}q^{\operatorname{inv}(\pi)}. $$

Setting $q=1$ recovers the cycle polynomial; setting $t=1$ recovers the inversion polynomial. These marginal distributions do not assert independence. For instance, in $S_3$ the unique permutation with three cycles has zero inversions.

In data rearrangement, a permutation describes a desired arrangement of distinct records. Its cycle count determines the minimum number of unrestricted exchanges, while its inversion count determines the minimum number of neighboring exchanges. Specifying the allowed operation is therefore essential before using a count as a measure of work.