← MA0 1 · Introduction to University Mathematics (Proofs)

Lesson 8

Permutations

Taught 18 Aug 2026

Permutations

A bijection from a set to itself maps the set onto itself and may rearrange its elements. Counting was the first thing we did with finite sets, and the second is this: fix the set and ask in how many ways its points can be rearranged among themselves. The rearranging functions can be composed, and this chapter studies that composition.

Two-Row Notation

Definition 8.1 (Permutation).

Let $A$ be a set. A permutation of $A$ is a bijection $\sigma : A \to A$ .

When $A$ is finite and non-empty a permutation is settled by naming the value it takes at each point, and there are only finitely many points to name. So the whole function fits in a table of two rows: the points along the top, their values underneath.

Definition 8.2 (Blocks and $n$ -sets).

For $n \in \mathbb{N}_0$ write

\langle n \rangle \defeq \{x \in \mathbb{N} \mid x \leqslant n\} = \{1, 2, \ldots, n\},

so that $\langle 0 \rangle = \emptyset$ . A finite set $A$ with cardinality $\#A = n$ is an $n$ -set, and a subset of a set that is itself a $k$ -set is a $k$ -subset of it.

The block $\langle n \rangle$ counts as the cut $L_n$ does: $i \mapsto i + 1$ is a bijection from $L_n$ onto $\langle n \rangle$ , injective by uniqueness of differences and surjective because every positive number is a successor. So $\#\langle n \rangle = n$ , and an $n$ -set is exactly a set equinumerous with $\langle n \rangle$ . We take the block rather than the cut as the standing domain here only because it makes the tables below read as they do everywhere else, starting at one.

Definition 8.3 (Two-row notation).

Let $A$ be an $n$ -set with $n \in \mathbb{N}$ , let $a_1, \ldots, a_n$ be a listing of its elements, and let $\sigma$ be a permutation of $A$ . Write

\sigma = \begin{pmatrix} a_1 & a_2 & \cdots & a_n \\ \sigma(a_1) & \sigma(a_2) & \cdots & \sigma(a_n) \end{pmatrix}

for the permutation sending each $a_i$ to $\sigma(a_i)$ . The columns may be reordered at will: any listing of the domain along the top, with the matching values underneath, denotes the same function.

The last sentence is equality of functions and nothing more. A table names a function by naming its value at each point, and the order in which the points are named is no part of the function.

Example 8.4 (A permutation of four points).

On $A = \{1, 2, 3, 4\}$ the rule $\sigma(1) = 4$ , $\sigma(2) = 1$ , $\sigma(3) = 3$ , $\sigma(4) = 2$ is the permutation

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 3 & 2 \end{pmatrix} = \begin{pmatrix} 3 & 1 & 4 & 2 \\ 3 & 4 & 2 & 1 \end{pmatrix},

the second table being the first with its columns shuffled. A two-row table fails to describe a permutation exactly when its bottom row is not a rearrangement of its top: a repeated value breaks injectivity, and a missing one breaks surjectivity.

Definition 8.5 (The symmetric group).

The set of all permutations of a set $A$ is written $S_A$ and called the symmetric group on $A$ . When $A = \langle n \rangle$ one writes $S_n$ rather than $S_{\langle n \rangle}$ .

The word group is traditional and we use it as a name only. What stands behind it is that $S_A$ carries a multiplication and is closed under composition and inverses: composition sends bijections to bijections, the identity map is a bijection since it is its own inverse, and the inverse of a bijection is a bijection. No abstract definition of a group is needed below; we use only the set $S_A$ and its composition.

Working in $S_n$ rather than in $S_A$ for an arbitrary $n$ -set loses nothing. A listing of $A$ is a bijection $h : \langle n \rangle \to A$ , and $\sigma \mapsto h^{-1} \circ \sigma \circ h$ carries permutations of $A$ to permutations of $\langle n \rangle$ , reversibly. That is what two-row notation already does silently when it writes the points in a row.

Definition 8.6 (Product of permutations).

Let $\sigma, \lambda \in S_A$ . The product $\sigma\lambda$ is the composite $\sigma \circ \lambda$ , so that

(\sigma\lambda)(x) = \sigma\bigl(\lambda(x)\bigr) \qquad \text{for every } x \in A.

One applies $\lambda$ first and $\sigma$ second. The permutations $\sigma$ and $\lambda$ are the factors of the product.

Example 8.7 (Multiplying in $S_4$ ).

Take

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix}, \qquad \lambda = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 3 & 2 \end{pmatrix}

in $S_4$ . To compute $\sigma\lambda$ , follow each point through $\lambda$ and then through $\sigma$ :

\begin{aligned} 1 &\overset{\lambda}{\longmapsto} 4 \overset{\sigma}{\longmapsto} 2, \\ 2 &\overset{\lambda}{\longmapsto} 1 \overset{\sigma}{\longmapsto} 3, \\ 3 &\overset{\lambda}{\longmapsto} 3 \overset{\sigma}{\longmapsto} 4, \\ 4 &\overset{\lambda}{\longmapsto} 2 \overset{\sigma}{\longmapsto} 1, \end{aligned}

so that

\sigma\lambda = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \end{pmatrix}, \qquad \lambda\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{pmatrix},

the second computed the same way in the other order. So $\sigma\lambda \neq \lambda\sigma$ : the multiplication is not commutative, though particular pairs may commute.

Remark (Authors who read left to right).

Some texts write the value of a function to the right of its argument, $(x)\sigma$ in place of $\sigma(x)$ , and then read a product left to right. We keep the order fixed for composition, so $\sigma\lambda$ always means ” $\lambda$ first, then $\sigma$ ”. When reading another source, work one product out by hand before trusting its convention.

The bottom row of a two-row table for an element of $S_n$ is a rearrangement of $1, \ldots, n$ , and conversely each rearrangement of $1, \ldots, n$ is the bottom row of exactly one element of $S_n$ , the one whose top row runs in ascending order. So $S_n$ is matched point for point with the orderings of $\langle n \rangle$ , which is why permutations are so often described as arrangements rather than as functions.

Permutations describe any situation in which $n$ objects trade $n$ places, one object to a place. Number the places $1$ through $n$ ; a process that carries whatever sits in place $i$ to place $j$ is recorded by the permutation $\sigma$ with $\sigma(i) = j$ , and performing two such processes in turn is recorded by the product.

Every set has two permutations we already know. One is the identity, a bijection because it is its own inverse. The other is the transposition $\tau_{a,b}$ of the counting chapter, which exchanges $a$ and $b$ and fixes every other point; it is its own inverse, hence a permutation of whatever set it is defined on. So $S_A$ is never empty, and holds more than one element as soon as $A$ holds two distinct points.

Problem 8.1.

Write out every element of $S_2$ and of $S_3$ in two-row notation, with the top row ascending, and check that you have two and six of them respectively.

Problem 8.2.

With $\sigma$ and $\lambda$ as in the example of multiplication in $S_4$ , compute $\sigma\sigma$ and $\lambda\lambda$ , and decide whether either is the identity. Compute $\tau_{1,2}\,\sigma$ and $\sigma\,\tau_{1,2}$ and observe that they differ.

Problem 8.3.

Let $A$ be a set and let $h : \langle n \rangle \to A$ be a bijection. Show that $\sigma \mapsto h^{-1} \circ \sigma \circ h$ is a bijection from $S_A$ onto $S_n$ , and that it carries products to products.

Counting Permutations

The theorem on cardinality of a product already suggests how many bijections run between two $n$ -sets: $n$ values are available for the first point, then $n - 1$ for the second once the first is used, and so on down. The shorthand for that descending product is the factorial.

Definition 8.8 (Factorial).

Define $n!$ for $n \in \mathbb{N}_0$ by the recursion

0! \defeq 1, \qquad s(n)! \defeq s(n) \cdot n!,

so that $n! = n(n-1)\cdots 2 \cdot 1$ for $n \in \mathbb{N}$ . The number $n!$ is the factorial of $n$ .

That the recursion defines exactly one function is the recursion theorem, applied as it was for addition. The value $0! = 1$ is the empty product, chosen for the same reason the empty sum is $0$ : it starts the recursion, and it spares us a separate case in every count below.

Theorem 8.9 (Number of bijections between $n$ -sets).

Let $A$ and $B$ be $n$ -sets for some $n \in \mathbb{N}_0$ . Then there are exactly $n!$ bijections from $A$ to $B$ . In particular $\#S_n = n!$ , and the empty set has exactly one permutation, in agreement with $0! = 1$ .

Discussion.

The claim is a counting statement about a set we have not yet named: writing $J$ for the set of bijections $A \to B$ , we must show $\#J = n!$ . The factorial was defined by a recursion on $n$ , so the proof is an induction on $n$ whose step must produce the factor $s(n)$ . At $n = 0$ both sets are empty and the empty function is the only function between them, so there is one, which is $0!$ . For the step we split $J$ according to where a chosen point $a$ of $A$ goes: there are $s(n)$ possible values, the pieces of the split are pairwise disjoint and cover $J$ , and each piece is matched with the bijections between two $n$ -sets by restricting to what is left of $A$ . By the inductive hypothesis each piece has $n!$ elements, and the cardinality of a product gives the total $s(n) \cdot n!$ , which is the recursion clause for the factorial.

Proof.

We induct on $n$ . If $n = 0$ then $A = B = \emptyset$ , and the empty function is the only function $\emptyset \to \emptyset$ ; it is a bijection, so there is $1 = 0!$ of them.

Suppose the claim holds for all pairs of $n$ -sets, and let $\#A = \#B = s(n)$ . Fix $a \in A$ and, for each $b \in B$ , let $J_b$ be the set of bijections $\sigma : A \to B$ with $\sigma(a) = b$ . Every bijection $A \to B$ lies in exactly one $J_b$ , namely the one indexed by its value at $a$ , so the $J_b$ are pairwise disjoint and their union is $J$ .

Fix $b$ . Restriction to $A \setminus \{a\}$ carries a member of $J_b$ to a bijection $A \setminus \{a\} \to B \setminus \{b\}$ , by the proposition that bijections remove points; and every such bijection extends to exactly one member of $J_b$ , by sending $a$ to $b$ . So $J_b$ is matched with the set of bijections between two $n$ -sets, which the inductive hypothesis counts as $n!$ , and $\#J_b = n!$ .

The index set $B$ is an $s(n)$ -set, so $J$ is a union of $s(n)$ pairwise disjoint sets each of cardinality $n!$ ; matching it with $B \times \langle n! \rangle$ and applying the cardinality of a product gives

\#J = s(n) \cdot n! = s(n)!,

which is the claim at $s(n)$ . Taking $A = B = \langle n \rangle$ gives $\#S_n = n!$ .

Example 8.10 (The sets $S_1$ , $S_2$ and $S_3$ ).

$S_1$ holds only the identity on $\{1\}$ . $S_2$ holds the two elements

\begin{pmatrix} 1 & 2 \\ 1 & 2 \end{pmatrix}, \qquad \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix},

and $S_3$ holds $3! = 6$ :

\begin{aligned} &\begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix}, &&\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}, &&\begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}, \\[1ex] &\begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix}, &&\begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}, &&\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix}. \end{aligned}

Without the theorem one would need care to be sure such a list is complete; with it, six is enough.

Example 8.11 (Selections and orderings).

A competition offers five water events, six running events, four cycling events and seven self-defence events. One event may be chosen from each category in $5 \cdot 6 \cdot 4 \cdot 7 = 840$ ways, by the cardinality of a product applied three times. If a competitor also fixes the order in which to attempt the four chosen events, each selection admits $4! = 24$ orders, so there are $840 \cdot 24 = 20{,}160$ full programmes.

Example 8.12 (Non-attacking rooks).

Eight rooks stand on a chessboard with no two attacking, which means no two share a row or a column, since a rook commands both. Each row holds at most one rook and there are eight rooks for eight rows, so every row holds exactly one; the same count puts exactly one in each column. Let $\sigma(i)$ be the column of the rook in row $i$ . The column condition says precisely that $\sigma$ is injective, hence a permutation of $\langle 8 \rangle$ by the theorem that injective and bijective agree on a finite set; and conversely each $\sigma \in S_8$ places one rook in each row, in the columns $\sigma(1), \ldots, \sigma(8)$ , no two equal. So the acceptable positions are matched with $S_8$ , and there are $8! = 40{,}320$ of them.

If the rooks are told apart, say by eight colours, choose the squares first in $8!$ ways and then distribute the colours over them in $8!$ ways, for $(8!)^2 = 1{,}625{,}702{,}400$ arrangements.

Example 8.13 (Necklaces).

Seven beads of distinct colours are strung on a cord whose ends are then tied, and two necklaces count as the same when one can be turned or flipped into the other. Before the knot the beads lie in a row, and there are $7! = 5040$ rows. Fix one necklace and ask how many rows display it: choose which bead is to sit at the left end, then which of that bead’s two neighbours follows it, and the rest of the row is forced, so $7 \cdot 2 = 14$ rows, all different because the colours are. Every row displays exactly one necklace, so fourteen times the number of necklaces is $5040$ , and there are $360$ necklaces.

Said the other way, call two rows equivalent when one is a rotation of the other or of its reversal; that is an equivalence relation, its classes are the necklaces, and each class holds fourteen rows.

Problem 8.4.

Show that $s(n)! = n! + n \cdot n!$ for every $n \in \mathbb{N}_0$ , and that $n! \geqslant n$ for every $n$ , with equality only at $n = 1$ and $n = 2$ .

Problem 8.5.

Give a second proof of the theorem on the number of bijections that does not partition $J$ , but instead builds a bijection one value at a time and appeals to the product of cardinalities directly. Which of the two proofs makes the appearance of $n!$ more transparent?

Problem 8.6.

Let $A$ be an $n$ -set. Show that the permutations of $A$ fixing a chosen point of $A$ number $(n-1)!$ , and that those moving every point of $A$ number fewer than $n!$ as soon as $n \geqslant 1$ .

Symmetries of Regular Polygons

Permutations record how $n$ labelled places trade their occupants. The symmetries of a regular polygon are an example: each rigid motion carrying the polygon onto itself shuffles the corners, and the motion is settled by the shuffle.

Remark (What is borrowed from geometry).

The plane, the length of a segment and the measure of an angle are borrowed here in the same spirit as the rules of school algebra were borrowed earlier: openly, and without being built. Two geometric facts are used and not proved: that a symmetry of a polygon carries corners to corners, and that a symmetry is settled by what it does to the corners. Everything else in this section is a statement about permutations, and is proved.

Definition 8.14 (Symmetry of a figure).

A figure is a subset $F$ of the plane. A symmetry of $F$ is a bijection $s$ of the plane onto itself such that $s(F) = F$ and such that the distance from $s(x)$ to $s(y)$ equals the distance from $x$ to $y$ , for all points $x$ and $y$ . Briefly: a rigid motion of the plane carrying $F$ onto itself.

Definition 8.15 (Polygon).

A polygon with $n$ corners, where $n \geqslant 3$ , is a figure consisting of points $v_1, \ldots, v_n$ , the corners, together with the segments joining $v_i$ to $v_{i+1}$ for $i \in \langle n \rangle$ , where $v_{n+1}$ means $v_1$ ; those segments are the edges. A polygon with $n$ corners is an $n$ -gon, and it is regular if all its edges have the same length and all its interior angles the same measure.

Label the corner positions of an $n$ -gon by $1, \ldots, n$ . A symmetry $s$ then determines a permutation $\sigma \in S_n$ : let $\sigma(i)$ be the label of the position to which $s$ carries the corner that started at position $i$ . Distinct symmetries determine distinct permutations, since a symmetry is settled by what it does to the corners, so the map $s \mapsto \sigma$ is injective and an $n$ -gon has at most $\#S_n = n!$ symmetries. Composing symmetries multiplies the permutations: if $s_1$ and $s_2$ answer to $\sigma_1$ and $\sigma_2$ , then $s_2 \circ s_1$ answers to $\sigma_2\sigma_1$ , because both sides send a corner to the same place. Questions of the form “what happens if these motions are performed in turn?” therefore become products in $S_n$ .

Example 8.16 (Symmetries of an equilateral triangle).

Let $P$ be an equilateral triangle with its corner positions labelled $1, 2, 3$ , and let $\ell_i$ be the line through position $i$ and the midpoint of the opposite edge. Writing $s_1, \ldots, s_6$ for the six symmetries of $P$ and $\sigma_1, \ldots, \sigma_6$ for the permutations they determine, the dictionary is

\begin{aligned} \sigma_1 &= \begin{pmatrix} 1 & 2 & 3 \\ 1 & 2 & 3 \end{pmatrix} && \text{identity}, \\ \sigma_2 &= \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} && \text{reflection in } \ell_1, \\ \sigma_3 &= \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix} && \text{reflection in } \ell_2, \\ \sigma_4 &= \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} && \text{reflection in } \ell_3, \\ \sigma_5 &= \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} && \text{turn by a third}, \\ \sigma_6 &= \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} && \text{turn by two thirds}. \end{aligned}

The six permutations listed are distinct and $\#S_3 = 6$ , so the list is complete in two senses at once: the triangle has no further symmetries, and every element of $S_3$ comes from one.

For the triangle every permutation of the corners comes from a symmetry. For larger polygons this fails. For a square with corners labelled $1, 2, 3, 4$ in order round the boundary, the permutation

\begin{pmatrix} 1 & 2 & 3 & 4 \\ 1 & 3 & 2 & 4 \end{pmatrix}

holds position $1$ still while exchanging the two positions next to it, and no motion preserving distance can do that, since the two exchanged corners are at different distances from the first. For a regular $n$ -gon the count is exactly $2n$ .

Proposition 8.17 (Number of symmetries of a regular $n$ -gon).

A regular $n$ -gon has exactly $2n$ symmetries. Equivalently, the permutations in $S_n$ determined by those symmetries form a $2n$ -subset of $S_n$ .

Discussion.

The claim is a count, and the object counted is the set of symmetries, which we have already matched injectively with a subset of $S_n$ ; so it is enough to count the permutations that arise. A symmetry is settled by what it does to the corners, and in fact by what it does to two neighbouring corners, so the count is a product of two choices in the manner of the cardinality of a product. The first corner may go to any of the $n$ positions, which is the first factor. Its neighbour is one edge away from it, and a motion preserving distance must leave it one edge away from wherever the first corner went, so only the two positions adjacent to that one are available, which is the second factor. That those two choices determine the rest is the geometric fact we have assumed: the remaining corners are reached by stepping round the boundary, and each step is forced once the direction and the starting position are fixed.

Proof.

Label the corner positions $1, \ldots, n$ in order round the boundary and let $\sigma \in S_n$ come from a symmetry $s$ .

There are $n$ possible values for $\sigma(1)$ . The corners at positions $1$ and $2$ are joined by an edge, so $s$ carries them to corners joined by an edge, and hence $\sigma(2)$ is one of the two positions adjacent to $\sigma(1)$ : two possible values. Once $\sigma(1)$ and $\sigma(2)$ are fixed, so is the direction in which $s$ runs round the boundary, and every further corner is reached from the previous one by one edge in that direction; so $\sigma(3), \ldots, \sigma(n)$ are determined.

Each of the $n \cdot 2$ pairs of choices is realised, by a turn when the direction is preserved and by a reflection when it is reversed, and distinct pairs give distinct permutations, hence distinct symmetries. So there are exactly $2n$ symmetries.

Remark.

The same $2n$ can be counted a second way, by kind rather than by choice: there are $n$ turns, through none, one, …, $n-1$ steps round the boundary, and $n$ reflections. When $n$ is odd every reflection has its line through one corner and the midpoint of the opposite edge; when $n$ is even, half of the lines pass through two opposite corners and half through the midpoints of two opposite edges. Either way the total is $2n$ .

Definition 8.18 (Dihedral group).

The set of permutations in $S_n$ determined by the symmetries of a regular $n$ -gon is written $D_n$ and called the dihedral group of degree $n$ . By the proposition, $\#D_n = 2n$ and $D_n \subset S_n$ .

Working with the motions of a regular $n$ -gon is therefore the same as computing inside $D_n$ , since composing motions is multiplying permutations. The triangle gives $D_3 = S_3$ , as the example showed; for $n \geqslant 4$ the inclusion is proper, since $2n < n!$ .

Example 8.19 (A regular nine-gon).

A regular nine-gon has $2 \cdot 9 = 18$ symmetries. With the positions labelled $1$ through $9$ round the boundary, the two symmetries carrying position $1$ to position $5$ are

\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 5 & 6 & 7 & 8 & 9 & 1 & 2 & 3 & 4 \end{pmatrix} \quad \text{and} \quad \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 5 & 4 & 3 & 2 & 1 & 9 & 8 & 7 & 6 \end{pmatrix},

a turn through four steps and a reflection in the line through position $3$ and the centre. The reflection is recognisable from its table without any picture: it fixes $3$ and pairs off the remaining positions, which is what an involution with one fixed point looks like.

Example 8.20 (Composing motions by multiplying).

Take the six symmetries $s_1, \ldots, s_6$ of the equilateral triangle and their permutations $\sigma_1, \ldots, \sigma_6$ as listed above. The composite $s_4 \circ s_6 \circ s_2 \circ s_5 \circ s_3$ answers to the product

\sigma_4 \sigma_6 \sigma_2 \sigma_5 \sigma_3 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 1 & 3 & 2 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 \\ 3 & 2 & 1 \end{pmatrix}.

Following $1$ , $2$ and $3$ through the five factors from the right gives $1 \mapsto 3$ , $2 \mapsto 2$ and $3 \mapsto 1$ , so the product is $\sigma_3$ and the composite motion is the reflection $s_3$ . Once the dictionary between motions and permutations is fixed, the computation needs no picture.

Problem 8.7.

For the square with corners labelled $1, 2, 3, 4$ round the boundary, list the eight elements of $D_4$ in two-row notation, and name an element of $S_4$ that is not one of them.

Problem 8.8.

With the triangle dictionary above, compute $\sigma_5\sigma_5$ and $\sigma_5\sigma_5\sigma_5$ and read the answers as repeated turns.

Problem 8.9.

Show that $D_n$ is closed under products and under inverses. Argue geometrically, from the fact that a composite of rigid motions carrying the polygon onto itself is one, and that the inverse of such a motion is one.

Cycles and Parity

Two-row notation is complete but bulky: it names $n$ values to describe a function that may move only two points. Cycle notation is shorter. It records a permutation by its orbits, and the order and the parity of a permutation can both be read off the same decomposition.

Throughout, $n \in \mathbb{N}$ is fixed unless said otherwise, and $\mathrm{id}$ is the identity permutation of $\langle n \rangle$ .

Inverses, Powers and Order

A permutation is a bijection, so it has an inverse, and that inverse is again a bijection of the same set: $\sigma \in S_n$ gives $\sigma^{-1} \in S_n$ , with $\sigma^{-1}$ sending each $\sigma(i)$ back to $i$ . In two-row notation this is easy: exchange the rows, then reorder the columns so that the top row ascends again.

Example 8.21 (Computing an inverse).

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 3 & 1 & 4 & 2 \end{pmatrix},

then exchanging the rows gives

\begin{pmatrix} 3 & 1 & 4 & 2 \\ 1 & 2 & 3 & 4 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \end{pmatrix} = \sigma^{-1}.

In practice one writes a blank table and, under each $j$ along the top, records the unique $i$ with $\sigma(i) = j$ ; it is unique because $\sigma$ is a bijection.

Definition 8.22 (Powers of a permutation).

Let $\sigma \in S_n$ . Define $\sigma^t$ for $t \in \mathbb{N}_0$ by the recursion

\sigma^0 \defeq \mathrm{id}, \qquad \sigma^{s(t)} \defeq \sigma^t \sigma,

so that $\sigma^1 = \sigma$ and $\sigma^t$ is the $t$ -fold product $\sigma\sigma\cdots\sigma$ . Write also

\sigma^{-t} \defeq (\sigma^{-1})^t

for $t \in \mathbb{N}$ , so that $\sigma^{-1}$ has its usual meaning.

Example 8.23 (Powers both ways).

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 5 & 1 & 2 & 4 \end{pmatrix},

then

\sigma^2 = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 3 & 5 & 2 \end{pmatrix}, \qquad \sigma^{-1} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 1 & 5 & 2 \end{pmatrix}, \qquad \sigma^{-2} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 1 & 5 & 3 & 2 & 4 \end{pmatrix}.

Comparing the first and last tables shows $\sigma^{-2}$ to be the inverse of $\sigma^2$ , which the theorem below predicts.

Theorem 8.24 (Laws of exponents).

Let $\sigma \in S_n$ and let $s, t \in \mathbb{N}_0$ . Then

$\sigma^s \sigma^t = \sigma^{s+t}$ ;
$(\sigma^s)^t = \sigma^{st}$ ;
$(\sigma^s)^{-1} = (\sigma^{-1})^s$ , that is, $(\sigma^s)^{-1} = \sigma^{-s}$ when $s$ is positive.

Discussion.

Three identities between permutations, each of them an equality of functions on $\langle n \rangle$ . The powers were defined by a recursion on the exponent, so each part is an induction on one exponent with the other held fixed, and each inductive step is the recursion clause together with associativity of composition. For the first we fix $s$ and induct on $t$ ; the base is the identity law $\sigma^s \mathrm{id} = \sigma^s$ , and the step moves one factor across the bracket. The second is the same induction on $t$ , now using the first part at each step to add exponents. For the third, to say that a permutation is the inverse of $\sigma^s$ is to say that it composes with $\sigma^s$ to the identity on both sides, and $(\sigma^{-1})^s \sigma^s$ cancels from the inside out. We induct on $s$ for that too.

Proof.

For the first, fix $s$ and induct on $t$ . At $t = 0$ we have $\sigma^s \sigma^0 = \sigma^s \mathrm{id} = \sigma^s = \sigma^{s+0}$ , by the identity laws. Suppose $\sigma^s \sigma^t = \sigma^{s+t}$ . Then

\sigma^s \sigma^{s(t)} = \sigma^s (\sigma^t \sigma) = (\sigma^s \sigma^t) \sigma = \sigma^{s+t} \sigma = \sigma^{s(s+t)} = \sigma^{s + s(t)},

the second step by associativity of composition, the fourth and fifth by the recursion clauses for powers and for addition.

For the second, fix $s$ and induct on $t$ . At $t = 0$ both sides are $\mathrm{id}$ , since $s \cdot 0 = 0$ . Suppose $(\sigma^s)^t = \sigma^{st}$ . Then

(\sigma^s)^{s(t)} = (\sigma^s)^t \sigma^s = \sigma^{st} \sigma^s = \sigma^{st + s} = \sigma^{s \cdot s(t)},

using the first part and the recursion clause for multiplication.

For the third, induct on $s$ . At $s = 0$ both sides are $\mathrm{id}$ . Suppose $(\sigma^{-1})^s \sigma^s = \mathrm{id} = \sigma^s (\sigma^{-1})^s$ . The first part gives $\sigma^{s(s)} = \sigma^{1 + s} = \sigma \sigma^s$ , so

(\sigma^{-1})^{s(s)} \sigma^{s(s)} = \bigl((\sigma^{-1})^s \sigma^{-1}\bigr)\bigl(\sigma \sigma^s\bigr) = (\sigma^{-1})^s \bigl(\sigma^{-1} \sigma\bigr) \sigma^s = (\sigma^{-1})^s \sigma^s = \mathrm{id},

the second step by associativity, the third because $\sigma^{-1}\sigma = \mathrm{id}$ , and the last by the inductive hypothesis. In the other order, the first part applied to $\sigma^{-1}$ gives $(\sigma^{-1})^{s(s)} = \sigma^{-1} (\sigma^{-1})^s$ , and

\sigma^{s(s)} (\sigma^{-1})^{s(s)} = \bigl(\sigma^s \sigma\bigr)\bigl(\sigma^{-1} (\sigma^{-1})^s\bigr) = \sigma^s \bigl(\sigma \sigma^{-1}\bigr) (\sigma^{-1})^s = \sigma^s (\sigma^{-1})^s = \mathrm{id}.

So $(\sigma^{-1})^s$ is a two-sided inverse of $\sigma^s$ , and inverses are unique.

Remark.

With the third part in hand the notation $\sigma^{-t}$ is consistent: it does not matter whether one inverts and then takes the power or takes the power and then inverts. All three laws then hold for exponents of either sign, once the statements are read with the convention $\sigma^{-t} = (\sigma^{-1})^t$ ; we have written them for $\mathbb{N}_0$ because that is where we have arithmetic, and a negative exponent is here an abbreviation rather than a number.

Definition 8.25 (Order of a permutation).

Let $\sigma \in S_n$ . The order of $\sigma$ , written $\mathrm{ord}\,\sigma$ , is the least $k \in \mathbb{N}$ with $\sigma^k = \mathrm{id}$ , if there is one.

Proposition 8.26 (Every permutation has an order).

Let $\sigma \in S_n$ . Then $\sigma^k = \mathrm{id}$ for some $k \in \mathbb{N}$ , so $\mathrm{ord}\,\sigma$ is defined and lies in $\mathbb{N}$ .

Discussion.

The claim is an existence statement, and since all we know is that $S_n$ is finite, we use the pigeonhole principle. We have infinitely many powers $\sigma^0, \sigma^1, \sigma^2, \ldots$ and only $n!$ permutations for them to be, so two of the powers coincide. Cancelling the smaller from the larger (multiplying by an inverse, using the laws of exponents) leaves a positive power equal to the identity. Once the set of positive $k$ with $\sigma^k = \mathrm{id}$ is known to be non-empty, well-ordering supplies its least member, which is what the definition asks for.

Proof.

The map $t \mapsto \sigma^t$ from $\langle s(n!) \rangle$ to $S_n$ has a domain of $s(n!)$ elements and a range inside a set of $n!$ elements, so it is not injective by the pigeonhole principle: there are $i < j$ in that block with $\sigma^i = \sigma^j$ . Write $j = i + d$ with $d \in \mathbb{N}$ . Composing with $(\sigma^{-1})^i$ on the left and using the laws of exponents,

\mathrm{id} = (\sigma^{-1})^i \sigma^i = (\sigma^{-1})^i \sigma^{i + d} = \bigl((\sigma^{-1})^i \sigma^i\bigr)\sigma^d = \sigma^d .

So $K \defeq \{k \in \mathbb{N} \mid \sigma^k = \mathrm{id}\}$ is non-empty, and well-ordering gives it a least member, which is $\mathrm{ord}\,\sigma$ .

Theorem 8.27 (Powers repeat with the order).

Let $\sigma \in S_n$ with $\mathrm{ord}\,\sigma = k$ . Then $\sigma^0, \sigma^1, \ldots, \sigma^{k-1}$ are pairwise distinct, and every power $\sigma^t$ with $t \in \mathbb{N}_0$ is one of them.

Discussion.

Two assertions. The second says that the list exhausts the powers, and the tool is division with remainder: writing $t = qk + r$ with $r < k$ , the laws of exponents split $\sigma^t$ into $(\sigma^k)^q \sigma^r$ , and the first factor is the identity by the definition of the order, leaving $\sigma^r$ with $r$ in range. The first assertion is a uniqueness claim and goes by contradiction: two equal powers among the first $k$ would cancel to give a positive power below $k$ equal to the identity, and the order was chosen least, so no such power exists.

Proof.

Let $t \in \mathbb{N}_0$ . Division with remainder gives $q, r \in \mathbb{N}_0$ with $t = q \cdot k + r$ and $r < k$ , so by the laws of exponents

\sigma^t = \sigma^{qk + r} = (\sigma^k)^q \sigma^r = \mathrm{id}^q \sigma^r = \sigma^r,

and $\sigma^t$ is one of $\sigma^0, \ldots, \sigma^{k-1}$ .

Suppose $\sigma^i = \sigma^j$ with $i < j$ and $j \leqslant k - 1$ . Writing $j = i + d$ with $d \in \mathbb{N}$ and composing with $(\sigma^{-1})^i$ as before gives $\sigma^d = \mathrm{id}$ with $d \leqslant j < k$ , contradicting the leastness of $k$ . So the $k$ powers listed are pairwise distinct.

Problem 8.10.

Let

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 4 & 2 & 1 \end{pmatrix}.

Compute $\sigma^2, \sigma^3, \ldots$ until the identity appears, and state $\mathrm{ord}\,\sigma$ .

Problem 8.11.

Show that if $\sigma^m = \mathrm{id}$ for some $m \in \mathbb{N}$ , then $\mathrm{ord}\,\sigma$ divides $m$ , in the sense that $m = q \cdot \mathrm{ord}\,\sigma$ for some $q$ . Division with remainder is the whole of the argument.

Problem 8.12.

Show that $\mathrm{ord}\,\sigma = \mathrm{ord}\,\sigma^{-1}$ for every $\sigma \in S_n$ , and that $\mathrm{ord}\,\sigma = 1$ exactly when $\sigma = \mathrm{id}$ .

Cycles and Disjoint Decomposition

Draw a point for each $i \in \langle n \rangle$ and an arrow from $i$ to $\sigma(i)$ . Because $\sigma$ is a function, exactly one arrow leaves each point; because it is injective, exactly one arrow arrives at each. A picture of that kind can only be a collection of separate closed loops, some of them loops from a point to itself. The notation that matches the picture is the following.

Definition 8.28 (Cycle).

Let $r \in \mathbb{N}$ with $r \leqslant n$ . A permutation $\sigma \in S_n$ is an $r$ -cycle, or a cycle of length $r$ , if there are distinct $a_1, \ldots, a_r \in \langle n \rangle$ with

\sigma(a_i) = \begin{cases} a_{i+1} & \text{if } i < r, \\ a_1 & \text{if } i = r, \end{cases}

and $\sigma(x) = x$ for every $x \in \langle n \rangle \setminus \{a_1, \ldots, a_r\}$ . The set $\{a_1, \ldots, a_r\}$ is the orbit of the cycle, written $\mathrm{orb}\,\sigma$ , and one writes

\sigma = (a_1 \ a_2 \ \cdots \ a_r)

for this permutation. A point $x$ with $\sigma(x) \neq x$ is said to be moved by $\sigma$ .

A $1$ -cycle $(a_1)$ fixes $a_1$ and fixes everything else, so it is the identity; in a product one leaves such factors out, since they do nothing. For $r \geqslant 2$ the listing inside the brackets may start wherever one likes,

(a_1 \ a_2 \ \cdots \ a_r) = (a_2 \ \cdots \ a_r \ a_1) = \cdots = (a_r \ a_1 \ \cdots \ a_{r-1}),

since all $r$ of those tables send each $a_i$ to the same place; and the inverse of a cycle is the same cycle read backwards,

(a_1 \ a_2 \ \cdots \ a_r)^{-1} = (a_r \ a_{r-1} \ \cdots \ a_1).

Example 8.29 (A five-cycle).

The permutation

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 7 & 3 & 5 & 4 & 1 & 6 & 2 \end{pmatrix}

sends $1 \mapsto 7 \mapsto 2 \mapsto 3 \mapsto 5 \mapsto 1$ and fixes $4$ and $6$ , so $\sigma = (1 \ 7 \ 2 \ 3 \ 5)$ , which is the same cycle as $(7 \ 2 \ 3 \ 5 \ 1)$ .

Definition 8.30 (Disjoint cycles).

A family of cycles in $S_n$ is disjoint if their orbits are pairwise disjoint: no cycle in the family moves a point moved by another.

Example 8.31 (Two disjoint cycles).

In $S_7$ the cycles $\alpha = (2 \ 6 \ 4 \ 5)$ and $\beta = (3 \ 7)$ are disjoint, since $\{2, 6, 4, 5\} \cap \{3, 7\} = \emptyset$ . In two-row notation,

\alpha = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 6 & 3 & 5 & 2 & 4 & 7 \end{pmatrix}, \qquad \beta = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 1 & 2 & 7 & 4 & 5 & 6 & 3 \end{pmatrix}.

Products of permutations do not commute in general, but disjoint cycles do, because each acts inside its own orbit and fixes everything outside it. The argument has nothing to do with cycles, so we state it for arbitrary maps.

Theorem 8.32 (Maps with disjoint supports commute).

Let $A$ and $B$ be sets and let $f, g : A \cup B \to A \cup B$ satisfy

$f(A) \subset A$ , and $f(x) = x$ for every $x \in B$ ;
$g(B) \subset B$ , and $g(x) = x$ for every $x \in A$ .

Then $g \circ f = f \circ g$ .

Discussion.

The claim is an equality of two functions with domain $A \cup B$ , so by equality of functions we compare values at an arbitrary point, and the domain is a union, so the comparison splits into the two cases $x \in A$ and $x \in B$ . Each case is the same short argument run with the hypotheses exchanged: one of the two maps fixes $x$ , so one composite is immediately the other map’s value at $x$ ; and that value stays in the set where the first map fixes everything, so the other composite is the same. Only the two hypotheses are used.

Proof.

Let $x \in A \cup B$ .

If $x \in A$ then $g(x) = x$ by the second hypothesis, so $(f \circ g)(x) = f(x)$ ; and $f(x) \in A$ by the first hypothesis, so $g$ fixes it and $(g \circ f)(x) = g(f(x)) = f(x)$ .

If $x \in B$ then $f(x) = x$ by the first hypothesis, so $(g \circ f)(x) = g(x)$ ; and $g(x) \in B$ by the second, so $f$ fixes it and $(f \circ g)(x) = f(g(x)) = g(x)$ .

In both cases the two composites agree at $x$ , so they are equal.

Corollary 8.33 (Disjoint cycles commute).

If $\alpha$ and $\beta$ are disjoint cycles in $S_n$ , then $\alpha\beta = \beta\alpha$ .

Proof.

Put $A \defeq \mathrm{orb}\,\alpha$ and $B \defeq \langle n \rangle \setminus A$ . Then $\alpha(A) = A$ and $\alpha$ fixes every point of $B$ , by the definition of a cycle. Disjointness puts $\mathrm{orb}\,\beta$ inside $B$ , so $\beta(B) \subset B$ , and $\beta$ fixes every point of $A$ . The theorem applies with $f = \alpha$ and $g = \beta$ .

Example 8.34 (A product of disjoint cycles).

In $S_{10}$ ,

(3 \ 1 \ 5 \ 7 \ 9)(2 \ 8 \ 6) = (2 \ 8 \ 6)(3 \ 1 \ 5 \ 7 \ 9) = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 5 & 8 & 1 & 4 & 7 & 2 & 9 & 6 & 3 & 10 \end{pmatrix}.

Neither $4$ nor $10$ is moved by either factor, and the table records that by fixing them.

Every permutation is such a product.

Theorem 8.35 (Cycle decomposition).

Every permutation in $S_n$ is a product of pairwise disjoint cycles. The identity is the empty product, or equally a product of $1$ -cycles, which one omits from the written expression.

Discussion.

The proof is a construction together with two checks. The construction follows the arrows of the picture: start at a point, apply $\sigma$ repeatedly, and see that the trail must return to its start. That it returns at all is the pigeonhole principle, since $\langle n \rangle$ is finite; that it returns to the start rather than to some later point of the trail uses injectivity, and we get it by taking the first repetition and cancelling. The trail is then the orbit of a cycle on which $\sigma$ agrees with that cycle. The first check is that a second trail, begun at a point not yet used, is disjoint from the first, which is again cancellation. The second is that the product of all the cycles obtained equals $\sigma$ : on each orbit the product acts as the one factor that moves that orbit, by disjointness, and off all of them both sides fix every point. The process stops because each round uses at least one new point of the finite set $\langle n \rangle$ .

Proof.

Let $\sigma \in S_n$ and let $b \in \langle n \rangle$ . Among the $s(n)$ values $\sigma^0(b), \sigma^1(b), \ldots, \sigma^n(b)$ , lying in the $n$ -set $\langle n \rangle$ , two coincide by the pigeonhole principle. Let $t$ be least such that $\sigma^t(b) = \sigma^i(b)$ for some $i < t$ . If $i$ were positive, composing both sides with $(\sigma^{-1})^i$ would give $\sigma^{t - i}(b) = b = \sigma^0(b)$ with $t - i < t$ , contradicting leastness. So $i = 0$ and $\sigma^t(b) = b$ , and the points $b, \sigma(b), \ldots, \sigma^{t-1}(b)$ are pairwise distinct, again by leastness. Write

\gamma_b \defeq \bigl(b \ \ \sigma(b) \ \ \cdots \ \ \sigma^{t-1}(b)\bigr),

a cycle whose orbit is that set and on which $\sigma$ agrees with $\gamma_b$ .

Now build the decomposition. Put $\gamma_1 \defeq \gamma_{b_1}$ for $b_1 \defeq 1$ . If every point outside $\mathrm{orb}\,\gamma_1$ is fixed by $\sigma$ , then $\sigma = \gamma_1$ and we are done. Otherwise choose a point $b_2$ moved by $\sigma$ and lying outside $\mathrm{orb}\,\gamma_1$ , and form $\gamma_2 \defeq \gamma_{b_2}$ . The two orbits are disjoint: if $\sigma^i(b_1) = \sigma^j(b_2)$ then composing with $(\sigma^{-1})^j$ or $(\sigma^{-1})^i$ , whichever exponent is the smaller, expresses $b_2$ as a power of $\sigma$ applied to $b_1$ , and the theorem on powers repeating puts that power inside $\mathrm{orb}\,\gamma_1$ , contrary to the choice of $b_2$ .

Repeat. Each round adds at least one point to the union of the orbits, and $\langle n \rangle$ is finite, so after finitely many rounds every point moved by $\sigma$ lies in some orbit. Let $\gamma_1, \ldots, \gamma_m$ be the cycles obtained; they are pairwise disjoint by the argument just given, applied to each pair. Their product agrees with $\sigma$ at every point: a point in $\mathrm{orb}\,\gamma_i$ is fixed by every factor but $\gamma_i$ , which sends it where $\sigma$ does, and a point in no orbit is fixed by every factor and by $\sigma$ . So $\sigma = \gamma_1 \cdots \gamma_m$ , and the order of the factors is immaterial by the corollary on disjoint cycles.

Remark (Reading off the decomposition).

The proof is an algorithm, and it is the one used in practice. Given $\sigma$ in two-row form, begin at any point not yet written down, apply $\sigma$ until the starting point returns, close the bracket, and start again elsewhere. Only cycles of length at least two need be written. In the picture of arrows, the cycles are exactly the separate loops.

Remark (Uniqueness).

The decomposition is unique up to the order of the factors and up to where each bracket starts. For suppose $\sigma = \gamma_1 \cdots \gamma_m = \lambda_1 \cdots \lambda_t$ are two products of pairwise disjoint cycles of length at least two, and let $a \in \mathrm{orb}\,\gamma_1$ . Then $\sigma(a) \neq a$ , so $a$ lies in the orbit of exactly one $\lambda_j$ , say $\lambda_1$ after renumbering. Both $\gamma_1$ and $\lambda_1$ agree with $\sigma$ on the orbit they contain $a$ in, so the two orbits are the same set — each is the trail of $a$ under $\sigma$ — and the two cycles agree there and fix everything else, hence $\gamma_1 = \lambda_1$ . Matching the remaining factors the same way shows the two collections coincide.

Example 8.36 (Three decompositions).

$\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 4 & 9 & 2 & 5 & 1 & 7 & 6 & 8 & 3 \end{pmatrix} = (1 \ 4 \ 5)(2 \ 9 \ 3)(6 \ 7).$
$\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 9 & 6 & 8 & 7 & 2 & 5 & 4 & 1 & 3 & 10 & 12 & 11 \end{pmatrix} = (1 \ 9 \ 3 \ 8)(2 \ 6 \ 5)(4 \ 7)(11 \ 12).$
If $\alpha = (1 \ 2 \ 3)$ and $\beta = (2 \ 3 \ 4)$ , the product $\alpha\beta$ is not written as a product of disjoint cycles, since the factors share the points $2$ and $3$ . Following each point through $\beta$ and then $\alpha$ gives $\alpha\beta = (1 \ 2)(3 \ 4)$ , which is.

Problem 8.13.

Show that an $r$ -cycle has order $r$ .

Problem 8.14.

Write each of the following as a product of disjoint cycles and give its order.

$\displaystyle \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 1 & 4 & 5 & 6 & 3 \end{pmatrix}$
$(1 \ 3 \ 5)(2 \ 4 \ 6 \ 1)$ , as an element of $S_6$ .

Problem 8.15.

Let $\sigma$ be a product of pairwise disjoint cycles of lengths $r_1, \ldots, r_m$ . Show that $\sigma^k = \mathrm{id}$ exactly when every $r_i$ divides $k$ , in the sense of the problem on divisibility, and deduce that $\mathrm{ord}\,\sigma$ is the least such $k$ . Say where disjointness is used.

Problem 8.16.

Show that $\sigma \in S_n$ is a transposition if and only if it is a $2$ -cycle, and that $\alpha\gamma\alpha^{-1} = (\alpha(a_1) \ \cdots \ \alpha(a_r))$ for every cycle $\gamma = (a_1 \ \cdots \ a_r)$ and every $\alpha \in S_n$ .

Problem 8.17.

Let $n \geqslant 3$ and let $\sigma \in S_n$ satisfy $\sigma\lambda = \lambda\sigma$ for every $\lambda \in S_n$ . Show that $\sigma = \mathrm{id}$ . Which elements of $S_2$ have the same property?

Transpositions and the Sign

A $2$ -cycle $(a \ b)$ exchanges $a$ and $b$ and fixes every other point of $\langle n \rangle$ , which is exactly the transposition $\tau_{a,b}$ written in cycle notation. In particular $(a \ b)^2 = \mathrm{id}$ and $(a \ b)^{-1} = (a \ b)$ , which is the proposition that a transposition is its own inverse read in the new notation. Transpositions move as few points as a permutation other than the identity can, and every permutation is a product of them.

Theorem 8.37 (Factorisation into transpositions).

Let $n \geqslant 2$ . Then every permutation in $S_n$ is a product of transpositions.

Discussion.

The statement is universally quantified over $S_n$ , and the cycle decomposition has already reduced any such statement to a statement about a single cycle: if each factor of a disjoint decomposition is a product of transpositions then so is the whole, by substitution. So there are two things to do. The identity is not covered by the decomposition, since its decomposition is empty, and it is handled separately by writing it as a transposition composed with itself. A cycle of length at least two is handled by exhibiting the factorisation outright, and the exhibited product is then checked point by point against the cycle.

Proof.

If $\sigma = \mathrm{id}$ then $\sigma = (1 \ 2)(1 \ 2)$ , which is available since $n \geqslant 2$ .

Otherwise the cycle decomposition writes $\sigma$ as a product of cycles of length at least two, so it is enough to factor one such cycle. We claim

(a_1 \ a_2 \ \cdots \ a_r) = (a_1 \ a_r)(a_1 \ a_{r-1}) \cdots (a_1 \ a_3)(a_1 \ a_2).

Evaluate the right-hand side from the right. The point $a_1$ is sent to $a_2$ by the first factor, and $a_2$ is fixed by all the others, so $a_1 \mapsto a_2$ . For $1 < i < r$ , the point $a_i$ is fixed by every factor until $(a_1 \ a_i)$ sends it to $a_1$ , and the next factor $(a_1 \ a_{i+1})$ sends $a_1$ to $a_{i+1}$ , which the remaining factors fix; so $a_i \mapsto a_{i+1}$ . The point $a_r$ is fixed until the last factor $(a_1 \ a_r)$ sends it to $a_1$ , and nothing follows, so $a_r \mapsto a_1$ . Any point outside the orbit is fixed by every factor. So the two sides agree everywhere.

Substituting these factorisations into the decomposition writes $\sigma$ as a product of transpositions.

Remark (Non-uniqueness).

The transposition factors are not disjoint in general, and cannot be: a $3$ -cycle moves three points, while a product of disjoint transpositions moves an even number. The factorisation is not unique either, since $(1 \ 2)(1 \ 2)$ may be inserted anywhere, and the order of non-disjoint factors matters, $(1 \ 3)(1 \ 2)$ and $(1 \ 2)(1 \ 3)$ being different permutations. What is unique is the evenness or oddness of the number of factors, and we prove this next.

To prove it we count, for a given permutation, the pairs of points whose order it reverses.

Definition 8.38 (Reversals, parity and sign).

Let $\sigma \in S_n$ and let $\{i, j\}$ be a $2$ -subset of $\langle n \rangle$ , written so that $i < j$ . Then $\sigma$ reverses $\{i, j\}$ if $\sigma(j) < \sigma(i)$ . Write $r(\sigma)$ for the number of $2$ -subsets of $\langle n \rangle$ reversed by $\sigma$ .

The permutation $\sigma$ is even if $r(\sigma)$ is even and odd if $r(\sigma)$ is odd; that alternative is the parity of $\sigma$ . The sign of $\sigma$ is

\mathrm{sgn}\,\sigma \defeq \begin{cases} 1 & \text{if } \sigma \text{ is even}, \\ -1 & \text{if } \sigma \text{ is odd}. \end{cases}

The count $r(\sigma)$ exists because the $2$ -subsets of $\langle n \rangle$ form a finite set, and each is reversed or not by the trichotomy of the order. The two values $1$ and $-1$ are just labels for the parity, and the only property of the labels we shall use is that multiplying them behaves as adding parities does, with $(-1)(-1) = 1$ recording that two odd numbers add to an even one.

Example 8.39 (Counting reversals).

The identity reverses nothing, so $r(\mathrm{id}) = 0$ and the identity is even. For

\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}

the three $2$ -subsets are $\{1, 2\}$ , with $2 < 3$ , not reversed; $\{1, 3\}$ , with $1 < 2$ , reversed; and $\{2, 3\}$ , with $1 < 3$ , reversed. So $r(\sigma) = 2$ and $\sigma$ is even.

The proof uses two facts about $r$ : multiplying by a transposition of neighbours changes it by exactly one, and every permutation is a product of such transpositions. The second was set as a problem in the chapter on sequences, where it justified the claim that rearranging a sum does not change it; here it is proved, and in the language of $S_n$ rather than of rearrangements.

Proposition 8.40 (A neighbour swap changes one reversal).

Let $\sigma \in S_n$ , let $k \in \langle n \rangle$ with $k < n$ , and put $\tau \defeq (k \ \ k+1)$ . Then exactly one of

r(\sigma\tau) = r(\sigma) + 1, \qquad r(\sigma) = r(\sigma\tau) + 1

holds. In particular $r(\sigma\tau)$ and $r(\sigma)$ have different parities.

Discussion.

Both $r(\sigma)$ and $r(\sigma\tau)$ are counts over the same index set, the $2$ -subsets of $\langle n \rangle$ , so the claim is that the two counts differ by one, and we sort the $2$ -subsets into three kinds and compare the counts kind by kind. The permutation $\sigma\tau$ agrees with $\sigma$ except that its values at $k$ and $k+1$ are exchanged: a $2$ -subset avoiding both $k$ and $k+1$ sees the same two values in the same positions, so its status is unchanged; a $2$ -subset meeting exactly one of them is paired with the $2$ -subset meeting the other, and the two statuses are exchanged between the members of the pair, leaving their total unchanged; and the single $2$ -subset $\{k, k+1\}$ has its status reversed, because the two values are exchanged while the two positions are not. Summing the three kinds, the totals agree except for one, and trichotomy makes the two displayed alternatives exclusive. The last sentence is then the remainder classes at $m = 2$ : a number and its successor never have the same parity.

Proof.

Write $\rho \defeq \sigma\tau$ , so that $\rho(k) = \sigma(k+1)$ , $\rho(k+1) = \sigma(k)$ , and $\rho(i) = \sigma(i)$ for every other $i$ . Sort the $2$ -subsets of $\langle n \rangle$ into three kinds.

Neither point in $\{k, k+1\}$ . Both values are the same for $\rho$ as for $\sigma$ , so the subset is reversed by one exactly when it is reversed by the other.

Exactly one point in $\{k, k+1\}$ . Such subsets come in pairs $\{i, k\}$ and $\{i, k+1\}$ with $i \notin \{k, k+1\}$ . Suppose $i < k$ , so that $i < k < k+1$ and $i$ is the smaller point in both subsets. Then $\rho$ reverses $\{i, k\}$ exactly when $\sigma(k+1) < \sigma(i)$ , which is exactly when $\sigma$ reverses $\{i, k+1\}$ ; and $\rho$ reverses $\{i, k+1\}$ exactly when $\sigma$ reverses $\{i, k\}$ . So the two statuses are exchanged within the pair and the number of reversed subsets among the two is the same for $\rho$ as for $\sigma$ . The case $k + 1 < i$ is the same argument with $i$ the larger point.

The subset $\{k, k+1\}$ . Here $\rho$ reverses it exactly when $\rho(k+1) < \rho(k)$ , that is when $\sigma(k) < \sigma(k+1)$ , which is exactly when $\sigma$ does not reverse it.

Adding the three kinds, the counts agree on the first two and differ by exactly one on the third. So $r(\rho)$ is $r(\sigma)$ increased by one or $r(\sigma)$ is $r(\rho)$ increased by one, and not both, by trichotomy. A number and its successor fall in different remainder classes for the divisor $2$ , so the parities differ.

Proposition 8.41 (Neighbour swaps suffice).

Let $n \geqslant 2$ . Then every permutation in $S_n$ is a product of transpositions of the form $(k \ \ k+1)$ with $k < n$ .

Discussion.

By the theorem on factorisation into transpositions the claim reduces to a single transposition $(a \ b)$ with $a < b$ , since substituting a factorisation of each factor factorises the product. We induct on the gap $d$ between them, where $b = a + d$ . At $d = 1$ the transposition is already a neighbour swap. For the step, conjugating a transposition by a neighbour swap moves one of its two points one place along: $(a \ b)$ is $(b-1 \ \ b)(a \ \ b-1)(b-1 \ \ b)$ , whose middle factor has a smaller gap and whose outer factors are neighbour swaps. Checking that identity is a comparison of values at the three points involved, everything else being fixed by all three factors.

Proof.

By the theorem on factorisation into transpositions it is enough to write a single transposition $(a \ b)$ , with $a < b$ , as a product of neighbour swaps. Write $b = a + d$ with $d \in \mathbb{N}$ and induct on $d$ .

If $d = 1$ then $(a \ b)$ is itself a neighbour swap.

Suppose the claim holds for $d$ , and let $b = a + s(d)$ , so that $b - 1 = a + d$ and $a < b - 1 < b$ . Put $\pi \defeq (b-1 \ \ b)$ . We claim $(a \ b) = \pi (a \ \ b-1) \pi$ . Evaluating the right-hand side from the right: $a$ is fixed by $\pi$ , sent to $b-1$ by the middle factor, and sent to $b$ by the last, so $a \mapsto b$ . The point $b$ is sent to $b-1$ by the first factor, then to $a$ by the middle, and $a$ is fixed by the last, so $b \mapsto a$ . The point $b-1$ is sent to $b$ by the first factor, fixed by the middle, and returned to $b-1$ by the last, so $b - 1 \mapsto b-1$ . Every other point is fixed by all three factors. So the two sides agree everywhere.

The middle factor $(a \ \ b-1)$ has gap $d$ and is a product of neighbour swaps by the inductive hypothesis, and $\pi$ is a neighbour swap, so $(a \ b)$ is a product of neighbour swaps.

Theorem 8.42 (Properties of the sign).

Let $\sigma, \lambda \in S_n$ with $n \geqslant 2$ .

$\mathrm{sgn}(\sigma\lambda) = (\mathrm{sgn}\,\sigma)(\mathrm{sgn}\,\lambda)$ .
Every transposition is odd.
If $\sigma$ is a product of $m$ transpositions, then $\mathrm{sgn}\,\sigma = 1$ when $m$ is even and $\mathrm{sgn}\,\sigma = -1$ when $m$ is odd.

Discussion.

Three claims about the parity of $r$ . The first says that the parity of $r(\sigma\lambda)$ is settled by the parities of $r(\sigma)$ and $r(\lambda)$ , and we use the proposition on neighbour swaps together with the proposition that neighbour swaps suffice: writing $\lambda$ as a product of $m$ neighbour swaps and multiplying them onto $\sigma$ one at a time flips the parity $m$ times, so the parity of $r(\sigma\lambda)$ is that of $r(\sigma)$ shifted by $m$ ; taking $\sigma$ to be the identity, whose count is $0$ , identifies the parity of $m$ with the parity of $\lambda$ , and the two statements together are the claim. The second is a direct count of reversals for $(a \ b)$ , sorting the $2$ -subsets by whether they meet $\{a, b\}$ and where their other point lies; the answer is one more than an even number. The third is then an induction on $m$ using the first two.

Proof.

For the first, write $\lambda = \pi_1 \pi_2 \cdots \pi_m$ as a product of neighbour swaps. Then

\sigma\lambda = \bigl(\cdots((\sigma\pi_1)\pi_2)\cdots\bigr)\pi_m,

by associativity, and each of the $m$ steps changes the parity of the reversal count, by the proposition on neighbour swaps. So $r(\sigma\lambda)$ has the parity of $r(\sigma)$ when $m$ is even and the opposite parity when $m$ is odd. Taking $\sigma = \mathrm{id}$ , where $r(\mathrm{id}) = 0$ is even, shows that $\lambda$ is even exactly when $m$ is even. Combining the two: $\sigma\lambda$ has the parity of $\sigma$ when $\lambda$ is even and the opposite when $\lambda$ is odd, which in the sign notation is the stated product rule.

For the second, let $\tau = (a \ b)$ with $a < b$ , and sort the $2$ -subsets of $\langle n \rangle$ . One meeting neither $a$ nor $b$ is not reversed, since $\tau$ fixes both its points. The subset $\{a, b\}$ is reversed, since $\tau(b) = a < b = \tau(a)$ . A subset $\{c, a\}$ or $\{c, b\}$ with $c \notin \{a, b\}$ is reversed exactly when $c$ lies strictly between $a$ and $b$ : if $c < a$ or $b < c$ then $c$ keeps its position relative to both, and if $a < c < b$ then $\{a, c\}$ is reversed because $\tau(c) = c$ while $\tau(a) = b > c$ , and $\{c, b\}$ is reversed because $\tau(b) = a < c$ . So each such $c$ contributes two reversals and nothing else contributes, giving

r(\tau) = 1 + 2 \cdot \#\{c \in \langle n \rangle \mid a < c < b\},

which is odd.

For the third, induct on $m$ . At $m = 1$ the claim is the second part. Suppose it holds for $m$ and let $\sigma = \tau_1 \cdots \tau_{s(m)}$ . Then $\sigma = (\tau_1 \cdots \tau_m)\tau_{s(m)}$ , so by the first two parts

\mathrm{sgn}\,\sigma = \mathrm{sgn}(\tau_1 \cdots \tau_m) \cdot (-1),

which changes the value from $1$ to $-1$ or from $-1$ to $1$ exactly as the parity of $m$ changes to the parity of $s(m)$ .

Corollary 8.43 (The number of transposition factors has a fixed parity).

If $\sigma = \tau_1 \cdots \tau_m = \tau'_1 \cdots \tau'_{m'}$ are two factorisations of the same $\sigma \in S_n$ into transpositions, then $m$ and $m'$ are both even or both odd.

Proof.

The third part of the theorem computes $\mathrm{sgn}\,\sigma$ from each factorisation, giving $1$ when the number of factors is even and $-1$ when it is odd. Since $\mathrm{sgn}\,\sigma$ is one value, $m$ and $m'$ cannot have different parities.

An $r$ -cycle is a product of $r - 1$ transpositions, by the factorisation exhibited above, so

\mathrm{sgn}\,(a_1 \ \cdots \ a_r) = 1 \text{ if } r \text{ is odd}, \qquad \mathrm{sgn}\,(a_1 \ \cdots \ a_r) = -1 \text{ if } r \text{ is even}.

A cycle of odd length is even and a cycle of even length is odd, which reads perversely until one remembers that the length counts points and the sign counts swaps. For a product of cycles of lengths $r_1, \ldots, r_t$ , disjoint or not, the first part of the theorem multiplies the signs together, so the product is even exactly when an even number of the $r_i$ are even.

Example 8.44 (Computing the sign).

For

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 5 & 2 & 4 \end{pmatrix} = (1 \ 3 \ 5 \ 4 \ 2),

a single cycle of length five, the sign is $1$ and $\sigma$ is even. For

\lambda = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 3 & 1 & 9 & 7 & 8 & 4 & 6 & 5 & 2 & 12 & 11 & 10 \end{pmatrix} = (1 \ 3 \ 9 \ 2)(4 \ 7 \ 6)(5 \ 8)(10 \ 12),

three of the four lengths are even, namely $4$ , $2$ and $2$ , so three of the four factors are odd and $\mathrm{sgn}\,\lambda = -1$ .

Remark (Parity as an obstruction).

Any sequence of exchanges of two of $n$ labelled objects is a product of transpositions in $S_n$ . If the rearrangement one is aiming at is odd, then no even number of exchanges reaches it, and if it is even, no odd number does. So parity rules out many proposed sequences of exchanges without examining the intermediate states: one only computes the sign of the target rearrangement.

Problem 8.18.

Write

\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 6 & 7 & 10 & 5 & 8 & 2 & 1 & 4 & 3 & 9 \end{pmatrix}

as a product of disjoint cycles and then as a product of transpositions, and compute $\mathrm{sgn}\,\sigma$ in both ways.

Problem 8.19.

Show that the even permutations in $S_n$ are closed under products and under inverses, and that the odd ones are closed under neither.

Problem 8.20.

Let $n \geqslant 2$ . Show that the even permutations in $S_n$ and the odd ones are equinumerous, by fixing a transposition $\tau$ and considering the map $\sigma \mapsto \tau\sigma$ . Conclude that $\#S_n$ is twice the number of even permutations.

Problem 8.21.

Let $\sigma \in S_n$ . Show that $\sigma$ is a product of $r(\sigma)$ transpositions of the form $(k \ \ k+1)$ with $k < n$ , and that no product of fewer such transpositions equals $\sigma$ .

Problem 8.22.

Let $n \geqslant 2$ . Show that every permutation in $S_n$ is a product of transpositions of the form $(1 \ k)$ with $1 < k \leqslant n$ , and that every permutation in $S_n$ is a product of factors each equal to $(1 \ 2)$ or to $(1 \ 2 \ \cdots \ n)$ .

Problem 8.23.

Fifteen tiles numbered $1$ to $15$ lie in a $4 \times 4$ frame with one cell empty, and a move slides into the empty cell a tile from a cell sharing an edge with it. Decide whether a sequence of moves carries the first arrangement below to the second, and prove your answer.

\begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \\ \hline 5 & 6 & 7 & 8 \\ \hline 9 & 10 & 11 & 12 \\ \hline 13 & 14 & 15 & \phantom{00} \\ \hline \end{array} \qquad\qquad \begin{array}{|c|c|c|c|} \hline 15 & 14 & 13 & 12 \\ \hline 11 & 10 & 9 & 8 \\ \hline 7 & 6 & 5 & 4 \\ \hline 3 & 2 & 1 & \phantom{00} \\ \hline \end{array}

Binomial Coefficients

Counting the permutations of an $n$ -set asked in how many ways its points can be arranged. The remaining question of the chapter asks in how many ways they can be chosen: not how a set may be reordered, but how many subsets of a given size it has. The two questions are linked, because choosing $k$ points and then arranging them is the same as arranging $k$ of the $n$ points, and this gives the count of subsets as a quotient of factorials.

Counting Subsets

Definition 8.45 (Binomial coefficient).

Let $n, k \in \mathbb{N}_0$ and let $S$ be an $n$ -set. The binomial coefficient $\dbinom{n}{k}$ , read ” $n$ choose $k$ ”, is the number of $k$ -subsets of $S$ :

\binom{n}{k} \defeq \#\{A \subset S \mid \#A = k\}.

The definition names a set $S$ and the notation does not, so the first thing to check is that the count does not depend on which $n$ -set was taken. It does not: two $n$ -sets are equinumerous, and a bijection $f : S \to S'$ carries $k$ -subsets to $k$ -subsets in both directions, since the image of a $k$ -subset under an injection is a $k$ -subset and $f^{-1}$ undoes it. The count is also finite, since the $k$ -subsets form a subset of the finite set $\mathcal{P}(S)$ .

Theorem 8.46 (Basic properties of binomial coefficients).

Let $n, k \in \mathbb{N}_0$ . Then

$\dbinom{n}{0} = 1$ and $\dbinom{n}{n} = 1$ ;
$\dbinom{n}{k} = 0$ whenever $n < k$ ;
$\dbinom{n}{k} = \dbinom{n}{n - k}$ whenever $k \leqslant n$ ;
$\dbinom{n}{1} = n$ , and $\dbinom{n}{n-1} = n$ when $n \geqslant 1$ ;
$\displaystyle\sum_{k=0}^{n} \binom{n}{k} = 2^n$ .

Discussion.

The first four parts follow from the definition, by naming the subsets counted. For the first, the empty set is the one $0$ -subset of anything and $S$ is the one $n$ -subset of itself, both by cardinality classifying finite sets. The second is the theorem on subsets of a finite set, which forbids a subset larger than the whole. The third is an equality of two counts, so it asks for a bijection between the two collections, and complementation is one, being its own inverse. The fourth counts singletons and then applies the third. The fifth is different: it is a statement about a sum, so we partition $\mathcal{P}(S)$ by cardinality — the classes are pairwise disjoint and cover it, since every subset of a finite set is finite with exactly one cardinality — and add the pieces up with the cardinality of a disjoint union, the total being $2^n$ by the problem on power sets.

Proof.

Fix an $n$ -set $S$ .

For the first, a $0$ -subset is equinumerous with $\emptyset$ and hence empty, so $\emptyset$ is the only one; an $n$ -subset $A \subset S$ has $\#A = \#S$ , so $A = S$ by the theorem on subsets of a finite set, which makes a proper subset strictly smaller.

For the second, a $k$ -subset $A \subset S$ would give $k = \#A \leqslant \#S = n$ by that theorem, contradicting $n < k$ ; so there are none.

For the third, $A \mapsto S \setminus A$ sends $k$ -subsets to $(n-k)$ -subsets, by the cardinality of a disjoint union applied to $S = A \cup (S \setminus A)$ , and it is its own inverse, hence a bijection between the two collections. Equinumerous finite sets have equal cardinality.

For the fourth, $x \mapsto \{x\}$ is a bijection from $S$ onto the collection of $1$ -subsets, so $\dbinom{n}{1} = n$ ; the third part then gives $\dbinom{n}{n-1} = n$ .

For the fifth, every subset of $S$ is finite with exactly one cardinality, and that cardinality is at most $n$ by the theorem on subsets of a finite set, so the collections of $k$ -subsets for $k = 0, 1, \ldots, n$ are pairwise disjoint and their union is $\mathcal{P}(S)$ . Adding their cardinalities gives

\sum_{k=0}^{n} \binom{n}{k} = \#\mathcal{P}(S) = 2^n,

the last equality being the problem on the cardinality of a power set.

The link between choosing and arranging is made by counting the injections between two finite sets, so we count them first.

Proposition 8.47 (Counting injections).

Let $A$ be a $k$ -set and $B$ an $n$ -set with $k \leqslant n$ . Then the number of injections $A \to B$ is

n(n-1)\cdots(n-k+1),

the product of the $k$ numbers running down from $n$ .

Discussion.

A count again. An injection is built by choosing values one point at a time, and each choice removes one candidate from the target, so we induct on $k$ , with $n$ fixed and $B$ fixed. At $k = 0$ the domain is empty, the empty function is the only function and it is injective, and the empty product is $1$ . For the step we split the injections from a $s(k)$ -set according to the value taken at a chosen point $a$ : the pieces are pairwise disjoint and cover, there are $n$ of them, and each is matched by restriction with the injections from a $k$ -set into a set with one point removed, which the inductive hypothesis counts. Adding $n$ equal pieces is the cardinality of a product, and the arithmetic gives the next factor down because the removed point shrinks the target from $n$ to $n - 1$ and shifts every factor.

Proof.

Induct on $k$ , the claim being taken for all $n \geqslant k$ and all $n$ -sets $B$ at once.

If $k = 0$ then $A = \emptyset$ , the empty function is the unique function $A \to B$ and is injective, and the empty product is $1$ .

Suppose the claim holds for $k$ and let $\#A = s(k) \leqslant n$ . Fix $a \in A$ and, for $b \in B$ , let $I_b$ be the set of injections $f : A \to B$ with $f(a) = b$ . Every injection lies in exactly one $I_b$ . Restriction to $A \setminus \{a\}$ matches $I_b$ with the injections from that $k$ -set into $B \setminus \{b\}$ , an $(n-1)$ -set: an injection cannot take the value $b$ anywhere else, so the restriction lands there, and every injection $A \setminus \{a\} \to B \setminus \{b\}$ extends to exactly one member of $I_b$ . By the inductive hypothesis,

\#I_b = (n-1)(n-2)\cdots(n-1-k+1) = (n-1)\cdots(n-k).

Summing over the $n$ values of $b$ , the number of injections $A \to B$ is

n \cdot (n-1)\cdots(n-k) = n(n-1)\cdots\bigl(n - s(k) + 1\bigr),

which is the claim at $s(k)$ .

Theorem 8.48 (Factorial formula for binomial coefficients).

Let $n, k \in \mathbb{N}_0$ with $k \leqslant n$ . Then

\binom{n}{k} \cdot k! \cdot (n-k)! = n!.

Discussion.

The claim is an identity between products of natural numbers, and the method is to count one set in two ways and equate the answers. The set is the collection of injections from a $k$ -set $D$ into an $n$ -set $S$ . Counted directly, the previous proposition gives the descending product. Counted by what an injection is made of, an injection is an image together with a bijection onto it: the image is a $k$ -subset of $S$ , of which there are $\dbinom{n}{k}$ , and the bijections from $D$ onto a fixed $k$ -subset number $k!$ by the theorem on the number of bijections. Equating the two answers gives $\dbinom{n}{k}\, k!$ equal to the descending product, and multiplying by $(n-k)!$ completes the descending product to $n!$ , which is the displayed identity.

Proof.

Fix an $n$ -set $S$ and a $k$ -set $D$ , and let $I$ be the set of injections $D \to S$ . By the proposition on counting injections,

\#I = n(n-1)\cdots(n-k+1).

Count $I$ a second way. Each $f \in I$ determines its image $f(D)$ , a $k$ -subset of $S$ , and is a bijection from $D$ onto that image, by an injection onto its range. Conversely a $k$ -subset $B \subset S$ together with a bijection $D \to B$ determines an $f \in I$ , and different pairs give different injections. There are $\dbinom{n}{k}$ choices of $B$ and, for each, exactly $k!$ bijections $D \to B$ by the theorem on the number of bijections. So

\#I = \binom{n}{k} \cdot k!.

Equating and multiplying both sides by $(n-k)!$ ,

\binom{n}{k} \cdot k! \cdot (n-k)! = n(n-1)\cdots(n-k+1) \cdot (n-k)! = n!,

the last step because the descending product and $(n-k)!$ between them use each of the factors $n, n-1, \ldots, 1$ exactly once. When $k = 0$ both sides are $n!$ , so the identity holds there too.

Remark.

The identity is normally written as a quotient,

\binom{n}{k} = \frac{n!}{k!\,(n-k)!},

and we shall write it that way below. The division is exact by the theorem, and we allow it on the same terms as subtraction: whenever the answer lies in $\mathbb{N}_0$ . For computing a single coefficient by hand the descending product is faster,

\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!},

while the two-factorial form is the better one to manipulate.

Theorem 8.49 (Pascal's identity).

Let $n, k \in \mathbb{N}$ with $k \leqslant n$ . Then

\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}.

Discussion.

The claim is that one count equals a sum of two counts, and a sum of counts comes from a partition of the set being counted. So we fix an $n$ -set $S$ , single out a point $x$ of it, and sort the $k$ -subsets of $S$ by whether they contain $x$ : two collections, disjoint and exhaustive. Those avoiding $x$ are exactly the $k$ -subsets of the $(n-1)$ -set $S \setminus \{x\}$ , which is the first term. Those containing $x$ are matched with the $(k-1)$ -subsets of $S \setminus \{x\}$ by removing $x$ , a map undone by putting it back, which is the second. The cardinality of a disjoint union adds them.

Proof.

Let $S$ be an $n$ -set, fix $x \in S$ and put $S_0 \defeq S \setminus \{x\}$ , an $(n-1)$ -set.

A $k$ -subset of $S$ either contains $x$ or does not, and not both. Those that do not are precisely the $k$ -subsets of $S_0$ , and there are $\dbinom{n-1}{k}$ of them.

Those that do are precisely the sets $A \cup \{x\}$ with $A$ a $(k-1)$ -subset of $S_0$ : removing $x$ from such a subset leaves a subset of $S_0$ of cardinality $k - 1$ , by the corollary on removing a point, and adjoining $x$ to a $(k-1)$ -subset of $S_0$ returns it. So there are $\dbinom{n-1}{k-1}$ of them.

The two collections are disjoint and their union is the collection of all $k$ -subsets of $S$ , so their cardinalities add to $\dbinom{n}{k}$ .

Pascal’s identity together with the boundary values $\dbinom{n}{0} = \dbinom{n}{n} = 1$ determines every binomial coefficient without any factorials at all, each from two earlier ones. Setting the values out in rows indexed by $n$ , with $k$ running left to right, gives Pascal’s triangle:

\begin{array}{cccccccc} 1 & & & & & & & \\ 1 & 1 & & & & & & \\ 1 & 2 & 1 & & & & & \\ 1 & 3 & 3 & 1 & & & & \\ 1 & 4 & 6 & 4 & 1 & & & \\ 1 & 5 & 10 & 10 & 5 & 1 & & \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 & \\ 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 \end{array}

Each interior entry is the sum of the two entries above it, one directly above and one to the left of that, which is Pascal’s identity. The rows add to $1, 2, 4, 8, \ldots$ , which is the fifth part of the theorem on basic properties, and each row is a palindrome, which is the third.

Example 8.50 (Two small counts).

The number of $2$ -subsets of a $10$ -set is

\binom{10}{2} = \frac{10 \cdot 9}{2} = 45,

and the number of $3$ -subsets is

\binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{6} = 120.

Example 8.51 (Shortest routes).

On a grid of streets $m$ blocks tall and $n$ blocks wide, a shortest walk from the bottom left corner to the top right uses $m + n$ blocks, of which $m$ are walked upwards and $n$ across. Such a walk is settled by saying which $n$ of its $m + n$ steps are the ones across, so there are $\dbinom{m+n}{n}$ shortest routes. On a square grid $n$ blocks each way there are $\dbinom{2n}{n}$ .

Problem 8.24.

Compute $\dbinom{12}{3}$ , $\dbinom{12}{9}$ and $\dbinom{12}{0}$ from the factorial formula, and check the first two against the symmetry $\dbinom{n}{k} = \dbinom{n}{n-k}$ .

Problem 8.25.

Prove the factorial formula a second time, by induction on $n$ with Pascal’s identity as the inductive step, treating $k = 0$ and $k = n$ separately.

Problem 8.26.

How many $5$ -subsets does a $52$ -set have? If the $52$ -set is partitioned into four $13$ -sets, how many of those $5$ -subsets lie inside a single part?

Identities and the Binomial Theorem

Theorem 8.52 (Absorption).

Let $n, k \in \mathbb{N}$ with $k \leqslant n$ . Then

k \binom{n}{k} = n \binom{n-1}{k-1}.

Discussion.

An identity between two products, so again we count one set in two ways. The set is the collection of pairs $(x, B)$ in which $B$ is a $k$ -subset of an $n$ -set $S$ and $x$ is a point of $B$ — a committee together with its chair, if one likes. Choosing the committee first and then the chair from within it gives $\dbinom{n}{k}$ followed by $k$ , which is the left-hand side; choosing the chair first from all of $S$ and then the rest of the committee from what remains gives $n$ followed by $\dbinom{n-1}{k-1}$ , which is the right. Each count is an application of the cardinality of a product to a partition of the same collection, sorted the two different ways. The factorial formula gives a second proof by cancellation, and we record that as well.

Proof.

Let $S$ be an $n$ -set and let $P$ be the set of pairs $(x, B)$ with $B$ a $k$ -subset of $S$ and $x \in B$ .

Sorting $P$ by its second coordinate, each of the $\dbinom{n}{k}$ possible $B$ occurs in exactly $k$ pairs, one for each of its points, so $\#P = \dbinom{n}{k} \cdot k$ .

Sorting $P$ by its first coordinate, each of the $n$ possible $x$ occurs in one pair for each $k$ -subset containing $x$ ; those are the sets $A \cup \{x\}$ with $A$ a $(k-1)$ -subset of $S \setminus \{x\}$ , as in the proof of Pascal’s identity, so there are $\dbinom{n-1}{k-1}$ of them. Hence $\#P = n \cdot \dbinom{n-1}{k-1}$ .

Equating the two gives the identity. Alternatively, from the factorial formula,

k \binom{n}{k} = \frac{k \cdot n!}{k!\,(n-k)!} = \frac{n \cdot (n-1)!}{(k-1)!\,(n-k)!} = n\binom{n-1}{k-1}.

Theorem 8.53 (The hockey-stick identity).

Let $m, n \in \mathbb{N}_0$ . Then

\sum_{k=0}^{n} \binom{m+k}{k} = \binom{m+n+1}{n}.

Discussion.

The left-hand side is a sum whose number of terms depends on $n$ , so the proof is an induction on $n$ with $m$ held fixed. At $n = 0$ both sides are $1$ , by the first part of the theorem on basic properties. The step adds one term to the sum: the inductive hypothesis replaces everything before it by a single coefficient, and what is left is a sum of two coefficients to which Pascal’s identity applies. So the whole argument is one application of the inductive hypothesis followed by one application of Pascal, and the only care needed is in matching the indices.

Proof.

Fix $m$ and induct on $n$ . At $n = 0$ the sum has the single term $\dbinom{m}{0} = 1$ , and the right-hand side is $\dbinom{m+1}{0} = 1$ .

Suppose the identity holds at $n$ . Then

\begin{aligned} \sum_{k=0}^{n+1} \binom{m+k}{k} &= \left(\sum_{k=0}^{n} \binom{m+k}{k}\right) + \binom{m+n+1}{n+1} \\ &= \binom{m+n+1}{n} + \binom{m+n+1}{n+1} \\ &= \binom{m+n+2}{n+1}, \end{aligned}

the second line by the inductive hypothesis and the third by Pascal’s identity, applied with upper index $m+n+2$ and lower index $n+1$ .

Remark.

The name records the shape the summed entries make in Pascal’s triangle: they run down one diagonal and the answer sits one place off the end, like the blade at the foot of a stick.

A binomial is a sum of two terms, and expanding a power of one produces the binomial coefficients as the coefficients of the resulting terms. That is where the name comes from.

Theorem 8.54 (The binomial theorem).

Let $a, b \in \mathbb{N}_0$ and let $n \in \mathbb{N}_0$ . Then

(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}.

Discussion.

Behind the statement is a count: multiplying out $n$ copies of $a + b$ produces one term for each way of taking $a$ from some of the copies and $b$ from the rest, so $a^k b^{n-k}$ appears once for each $k$ -subset of the copies, which is $\dbinom{n}{k}$ times. That is the reason the theorem is true, but it is not yet a proof, because “multiplying out” is not among our operations. What we have is the recursion defining powers, so the proof is an induction on $n$ : multiply the inductive hypothesis by $a + b$ , distribute, and reassemble. Pascal’s identity appears in the reassembly: after shifting the index of one of the two sums so that both run over the same power of $a$ , the two coefficients standing in front of each term are $\dbinom{n}{k-1}$ and $\dbinom{n}{k}$ , which Pascal’s identity adds to the coefficient wanted at $n+1$ .

Proof.

Induct on $n$ . At $n = 0$ both sides are $1$ , the left because $x^0 = 1$ and the right because the only term is $\dbinom{0}{0}a^0b^0$ .

Suppose the identity holds at $n$ . Then, distributing,

(a+b)^{n+1} = (a + b)\sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k} = \sum_{k=0}^{n} \binom{n}{k} a^{k+1} b^{n-k} + \sum_{k=0}^{n} \binom{n}{k} a^{k} b^{n-k+1}.

In the first sum put $j \defeq k + 1$ , so that $j$ runs from $1$ to $n+1$ :

\sum_{k=0}^{n} \binom{n}{k} a^{k+1} b^{n-k} = \sum_{j=1}^{n+1} \binom{n}{j-1} a^{j} b^{n+1-j}.

Renaming $j$ as $k$ and separating the terms $a^{n+1}$ and $b^{n+1}$ , which occur in only one of the two sums each,

\begin{aligned} (a+b)^{n+1} &= a^{n+1} + \sum_{k=1}^{n}\left(\binom{n}{k-1} + \binom{n}{k}\right) a^k b^{n+1-k} + b^{n+1} \\ &= a^{n+1} + \sum_{k=1}^{n} \binom{n+1}{k} a^k b^{n+1-k} + b^{n+1} \\ &= \sum_{k=0}^{n+1} \binom{n+1}{k} a^k b^{n+1-k}, \end{aligned}

by Pascal’s identity, and the two separated terms are the cases $k = n+1$ and $k = 0$ since $\dbinom{n+1}{n+1} = \dbinom{n+1}{0} = 1$ .

Remark (Where the theorem applies).

The proof uses nothing about $a$ and $b$ beyond the commutative, associative and distributive laws and the recursion defining powers. So it holds verbatim wherever those laws hold — for the real numbers of school algebra, and for expressions in an unknown — and that is how it is used in practice. We have stated it in $\mathbb{N}_0$ because that is the arithmetic built so far.

Corollary 8.55 (Sum of the binomial coefficients, again).

For every $n \in \mathbb{N}_0$ ,

\sum_{k=0}^{n} \binom{n}{k} = 2^n.

Proof.

Put $a = b = 1$ in the binomial theorem: every term $a^k b^{n-k}$ is $1$ , and the left-hand side is $2^n$ .

That is the fifth part of the theorem on basic properties, proved a second time and by quite a different route: the first proof partitioned the power set, and this one multiplies out a product. The first proof and the corollary together give a proof that $\#\mathcal{P}(S) = 2^n$ , running in the opposite direction to the one the problem asked for.

Example 8.56 (A single coefficient).

Working in school algebra, where the theorem applies by the remark above, the coefficient of $x^6$ in $(x - 3)^{11}$ is the coefficient of $x^6$ in

\sum_{k=0}^{11} \binom{11}{k} x^k (-3)^{11-k},

namely $\dbinom{11}{6}(-3)^5 = 462 \cdot (-243) = -112{,}266$ . Only one term of twelve is needed.

Problem 8.27.

Show that for every $n \in \mathbb{N}$ the binomial coefficients with even lower index add to the same total as those with odd lower index, and that each total is $2^{n-1}$ .

Problem 8.28.

Expand $(1+x)^n(1+x)^m$ in two ways and compare the coefficients of $x^r$ to obtain Vandermonde’s identity

\binom{n+m}{r} = \sum_{k=0}^{r} \binom{n}{k}\binom{m}{r-k},

for $n, m \in \mathbb{N}_0$ and $r \leqslant n + m$ , reading $\dbinom{a}{b}$ as $0$ when $a < b$ . Then prove the same identity by counting the $r$ -subsets of a set split into an $n$ -set and an $m$ -set.

Problem 8.29.

Show that $\dbinom{n}{k} < \dbinom{n}{k+1}$ exactly when $2k + 1 < n$ , and read off from that where a row of Pascal’s triangle attains its largest entry, treating $n = 2m$ and $n = 2m+1$ separately. The absorption identity compares consecutive entries of a row.

Problem 8.30.

Show that

n\binom{2n-1}{n-1} = \sum_{k=1}^{n} k\binom{n}{k}^2

for every $n \in \mathbb{N}$ .

Multinomial Coefficients

A binomial coefficient counts the ways of cutting an $n$ -set into two labelled pieces of prescribed sizes: a $k$ -subset and everything else. The same works with more than two pieces.

Definition 8.57 (Multinomial coefficient).

Let $n \in \mathbb{N}_0$ , let $t \in \mathbb{N}$ , and let $r_1, \ldots, r_t \in \mathbb{N}_0$ with $r_1 + \cdots + r_t = n$ . Let $S$ be an $n$ -set. The multinomial coefficient

\binom{n}{r_1, r_2, \ldots, r_t}

is the number of $t$ -tuples $(S_1, \ldots, S_t)$ of pairwise disjoint subsets of $S$ with $S_1 \cup \cdots \cup S_t = S$ and $\#S_i = r_i$ for each $i$ . Empty pieces are allowed, when some $r_i$ is $0$ .

The pieces are labelled by their position in the tuple, so two tuples listing the same pieces in a different order are different objects; the same convention was already in force for binomial coefficients, where the $k$ -subset was distinguished from its complement. Equivalently, such a tuple assigns each point of $S$ to one of $t$ labelled bins, with bin $i$ receiving $r_i$ points.

At $t = 2$ the definition returns the binomial coefficient, since a pair $(S_1, S_2)$ of the required kind is settled by $S_1$ alone:

\binom{n}{k, \, n-k} = \binom{n}{k}.

Theorem 8.58 (Factorial formula for multinomial coefficients).

Let $r_1 + \cdots + r_t = n$ with each $r_i \in \mathbb{N}_0$ . Then

\binom{n}{r_1, r_2, \ldots, r_t} \cdot r_1!\, r_2! \cdots r_t! = n!.

Discussion.

Once more we count one set two ways, and the set is the collection of listings of an $n$ -set $S$ — that is, of bijections $\langle n \rangle \to S$ . Counted directly there are $n!$ of them, by the theorem on the number of bijections. Counted by construction, a listing is assembled from a tuple of the kind the coefficient counts, together with an ordering inside each piece: read the first $r_1$ entries of the listing as the first piece in order, the next $r_2$ as the second, and so on. That correspondence is reversible, so the number of listings is the number of tuples multiplied by $r_1!$ through $r_t!$ , one factor for each piece by the theorem on the number of bijections again. Equating the two counts is the identity.

Proof.

Let $S$ be an $n$ -set. The listings of $S$ , meaning the bijections $\langle n \rangle \to S$ , number $n!$ .

Given a listing $h$ , cut $\langle n \rangle$ into the consecutive blocks of lengths $r_1, \ldots, r_t$ and let $S_i$ be the image of the $i$ -th block. The blocks are pairwise disjoint and cover $\langle n \rangle$ , so the $S_i$ are pairwise disjoint and cover $S$ , and $\#S_i = r_i$ since $h$ is injective. The listing also determines an ordering of each $S_i$ , namely the order in which its points appear.

Conversely a tuple $(S_1, \ldots, S_t)$ of the required kind, together with an ordering of each $S_i$ , reassembles into exactly one listing, by writing the pieces out one after another. So the listings correspond to such data, and there are $\dbinom{n}{r_1, \ldots, r_t}$ tuples with $r_i!$ orderings of the $i$ -th piece for each. Hence

n! = \binom{n}{r_1, \ldots, r_t} \cdot r_1! \cdots r_t!,

where a piece with $r_i = 0$ contributes the factor $0! = 1$ .

Remark.

As before we write the identity as a quotient,

\binom{n}{r_1, \ldots, r_t} = \frac{n!}{r_1!\,r_2! \cdots r_t!},

the division being exact by the theorem. The multinomial coefficient can also be built from binomial ones by choosing the pieces in turn, which is the content of a problem below.

Example 8.59 (Assigning students to projects).

Nine students are to be assigned to three named projects needing four, two and three students. The assignments number

\binom{9}{4, 2, 3} = \frac{9!}{4!\,2!\,3!} = 1260.

Had the projects been unnamed and only their sizes fixed, the count would be different, since the pieces would no longer be distinguished by position.

Example 8.60 (A bag of shopping).

A bag is packed with four bananas, five tins of tuna, two boxes of cereal, four lemons, three bottles of cola and six light bulbs, twenty-four items in all, alike within each kind and distinguishable between kinds. The orders in which the bag can be packed number

\binom{24}{4, 5, 2, 4, 3, 6} = \frac{24!}{4!\,5!\,2!\,4!\,3!\,6!},

since an order is settled by saying which of the twenty-four positions each kind occupies.

Theorem 8.61 (The multinomial theorem).

Let $x_1, \ldots, x_t \in \mathbb{N}_0$ and let $n \in \mathbb{N}_0$ . Then

(x_1 + \cdots + x_t)^n = \sum \binom{n}{r_1, \ldots, r_t}\, x_1^{r_1} \cdots x_t^{r_t},

the sum running over all $t$ -tuples $(r_1, \ldots, r_t)$ in $\mathbb{N}_0$ with $r_1 + \cdots + r_t = n$ .

Discussion.

The statement generalises the binomial theorem from two summands to $t$ , and it is proved the same way, by induction on $n$ with the recursion for powers supplying the step. The bookkeeping is heavier because the terms are indexed by tuples rather than by a single number, so we describe the step first: multiplying by $x_1 + \cdots + x_t$ and distributing turns each term indexed by a tuple summing to $n$ into $t$ terms, one for each coordinate raised by one, and every tuple summing to $n+1$ arises this way from exactly the tuples obtained by lowering one of its positive coordinates. Collecting like terms, the coefficient wanted at $n+1$ is the sum of the coefficients at $n$ over those predecessors, and that sum identity is Pascal’s identity in its multinomial form, which the factorial formula supplies directly.

Proof.

Write $\mathcal{R}_n$ for the set of $t$ -tuples in $\mathbb{N}_0$ summing to $n$ . We first record the identity, for $(r_1, \ldots, r_t) \in \mathcal{R}_{n+1}$ ,

\binom{n+1}{r_1, \ldots, r_t} = \sum_{i \,:\, r_i \geqslant 1} \binom{n}{r_1, \ldots, r_i - 1, \ldots, r_t},

which follows from the factorial formula: the $i$ -th summand is $\dbinom{n+1}{r_1, \ldots, r_t}$ multiplied by $r_i$ and divided by $n+1$ , so the whole sum is $\dbinom{n+1}{r_1, \ldots, r_t}$ multiplied by $r_1 + \cdots + r_t = n+1$ and divided by $n+1$ .

Now induct on $n$ . At $n = 0$ the only tuple is $(0, \ldots, 0)$ and both sides are $1$ .

Suppose the identity holds at $n$ . Multiplying by $x_1 + \cdots + x_t$ and distributing,

(x_1 + \cdots + x_t)^{n+1} = \sum_{(r_1, \ldots, r_t) \in \mathcal{R}_n} \binom{n}{r_1, \ldots, r_t} \sum_{i=1}^{t} x_i \, x_1^{r_1} \cdots x_t^{r_t}.

Each inner term is $x_1^{q_1} \cdots x_t^{q_t}$ for the tuple $(q_1, \ldots, q_t) \in \mathcal{R}_{n+1}$ got from $(r_1, \ldots, r_t)$ by raising the $i$ -th coordinate by one; and conversely each tuple in $\mathcal{R}_{n+1}$ arises exactly once from each tuple got by lowering one of its positive coordinates. Collecting the terms belonging to a fixed $(q_1, \ldots, q_t)$ , its coefficient is

\sum_{i \,:\, q_i \geqslant 1} \binom{n}{q_1, \ldots, q_i - 1, \ldots, q_t} = \binom{n+1}{q_1, \ldots, q_t}

by the recorded identity, which is the claim at $n+1$ .

Remark.

At $t = 2$ the theorem is the binomial theorem and the recorded identity is Pascal’s, since a tuple $(k, n-k)$ has two coordinates to lower. The remark about where the binomial theorem applies carries over unchanged: the proof uses only the commutative, associative and distributive laws.

Example 8.62 (A term with no unknown in it).

Working in school algebra, a term of the expansion of

\left(x + y + z + \frac{1}{xyz}\right)^{n}

has the form

x^{r_1} y^{r_2} z^{r_3} \left(\frac{1}{xyz}\right)^{r_4} = x^{r_1 - r_4} y^{r_2 - r_4} z^{r_3 - r_4}

with $r_1 + r_2 + r_3 + r_4 = n$ . All three exponents vanish exactly when $r_1 = r_2 = r_3 = r_4$ , which forces $n = 4k$ and each $r_i = k$ . So the constant term is $\dbinom{4k}{k, k, k, k}$ when $n$ is four times $k$ , and $0$ otherwise.

Problem 8.31.

Show that

\binom{n}{r_1, \ldots, r_t} = \binom{n}{r_1}\binom{n - r_1}{r_2} \cdots \binom{n - r_1 - \cdots - r_{t-1}}{r_t}

whenever $r_1 + \cdots + r_t = n$ , by choosing the pieces one after another. Then check the identity a second time from the factorial formulas.

Problem 8.32.

How many distinct arrangements are there of the eleven letters of $\mathrm{MISSISSIPPI}$ ? State the count as a multinomial coefficient before evaluating it.

Problem 8.33.

Expand $(x + y + z)^3$ by the multinomial theorem, and check the answer by multiplying the three factors out directly. How many terms does the expansion of $(x_1 + \cdots + x_t)^n$ have, before like terms are collected, and how many after?

Problem 8.34.

Let $n \in \mathbb{N}$ . By counting the partitions of a $2n$ -set into $2$ -subsets, show that $(n+1)(n+2)\cdots(2n)$ is divisible by $2^n$ and not by $2^{n+1}$ .

Exercises

Answers are checked in your browser, as often as you like. Nothing is sent anywhere and nothing is kept but your own work. A formula may be written with the symbols themselves or with ~ & | -> <-> ^, and \and, \or, \to expand as you type.

Exercises in Lean

The proofs below are checked in your browser. Nothing is sent anywhere, and nothing is stored but your own work. Type \to for →, \and for ∧, \< and \> for ⟨ ⟩.

This chapter asks four new things of the checker: the factorial and the binomial coefficient on $\mathbb{N}_0$ , the powers of a map, a name for a permutation, and the transposition as a map in its own right. The arithmetic comes first, written the way the Peano sheet wrote addition.

Factorials and binomial coefficients

The factorial of Definition 8.8 is written n !, with a space, since n! is a single name to Lean. Like addition, it is not computed, and its two clauses are equations to rewrite with:

Nat.factorial_zero   0 ! = succ 0
Nat.factorial_succ   (succ n) ! = succ n * n !

The binomial coefficient choose n k of Definition 8.45 is a count of subsets, and the checker has no counts, so it takes instead what Theorem 8.46 and Theorem 8.49 proved about that count:

Nat.choose_zero_right     choose n 0 = succ 0
Nat.choose_eq_zero_of_lt  n < k → choose n k = 0
Nat.choose_succ_succ      choose (succ n) (succ k) = choose n k + choose n (succ k)

The last is Pascal’s identity with both indices moved up by one, so that no subtraction appears.

Example.

$1! = 1$ , from the two clauses and the arithmetic of the Peano sheet.

Example.

A $1$ -subset of the empty set would be larger than the set it sits in.

Exercise 8.6.

The first part of Problem 8.4 .

Exercise 8.7.

The second half of the first part of Theorem 8.46 , this time from Pascal’s identity rather than by naming the one $n$ -subset.

Exercise 8.8.

The first half of its fourth part.

Powers

The power $\sigma^t$ of Definition 8.22 is written σ^[t], which is Lean’s own notation for a map composed with itself $t$ times. The recursion is not computed either, and its clauses are

Function.iterate_zero_apply   σ^[0] x = x
Function.iterate_succ_apply   σ^[succ t] x = σ^[t] (σ x)

the second being $\sigma^{s(t)} = \sigma^t \sigma$ read at a point. The checker cannot form an inverse, so the laws set below are the ones that need none.

Example.

The first part of Theorem 8.24 , by induction on $t$ . The point $x$ is left under the quantifier so that the inductive hypothesis can be used at $\sigma x$ . The result is listed below as Function.iterate_add_apply.

lean worked

1example (σ : Obj → Obj) (s t : ℕ) : ∀ x : Obj, σ^[s] (σ^[t] x) = σ^[s + t] x := by

2  induction t with k ih3  · intro x4    rw [Function.iterate_zero_apply, Nat.add_zero]5  · intro x6    rw [Function.iterate_succ_apply, ih (σ x), Nat.add_succ, Function.iterate_succ_apply]

verified

goalGoals accomplished.

Exercise 8.9.

The second part.

Exercise 8.10.

The first half of Theorem 8.27 , with the division already made: $k$ is any exponent at which $\sigma$ is the identity.

Permutations and transpositions

Definition 8.1 is the last sheet’s BijOn with the two sets equal, and it is written

Perm σ A   is   BijOn σ A A

so obtain ⟨hm, hi, hs⟩ takes a permutation apart and refine ⟨?_, ?_, ?_⟩ builds one. An equation between two maps on a set is read at each point of the set, as equality of functions reads it.

The transposition $(a \ b)$ is written swap a b. Its value at $x$ depends on whether $x$ is $a$ , $b$ or neither, and the checker cannot decide an equation between two objects, so its definition comes as three equations:

swap_apply_left          swap a b a = b
swap_apply_right         swap a b b = a
swap_apply_of_ne_of_ne   x ≠ a → x ≠ b → swap a b x = x

An argument about swap a b x for an unknown x goes by cases, and excluded middle supplies them: rcases Classical.em (x = a) with h | h leaves one goal with h : x = a and one with h : ¬x = a.

Example.

A transposition is its own inverse. It is listed below as swap_swap.

lean worked

1example (a b x : Obj) : swap a b (swap a b x) = x := by

2  rcases Classical.em (x = a) with h | h3  · rw [h, swap_apply_left, swap_apply_right]4  · rcases Classical.em (x = b) with h' | h'5    · rw [h', swap_apply_right, swap_apply_left]6    · rw [swap_apply_of_ne_of_ne h h', swap_apply_of_ne_of_ne h h']

verified

goalGoals accomplished.

Exercise 8.11.

Theorem 8.32 , read at each point of $A \cup B$ .

lean proof

1example (f g : Obj → Obj) (A B : Obj) (hf : MapsTo f A A) (hfB : ∀ x : Obj, x ∈ B → f x = x)2    (hg : MapsTo g B B) (hgA : ∀ x : Obj, x ∈ A → g x = x) :3    ∀ x : Obj, x ∈ A ∪ B → (g ∘ f) x = (f ∘ g) x := by

4  sorry

goalf g : Obj → Obj A B : Obj hf : MapsTo f A A hfB : ∀ (x : Obj), x ∈ B → f x = x hg : MapsTo g B B hgA : ∀ (x : Obj), x ∈ A → g x = x ⊢ ∀ (x : Obj), x ∈ A ∪ B → (g ∘ f) x = (f ∘ g) x

Exercise 8.12.

A transposition is a permutation of any set that holds its two points.

Exercise 8.13.

The second part of Problem 8.16 for a cycle of length two, with $\beta$ in the place of $\alpha^{-1}$ .

Exercise 8.14.

The identity $(a \ b) = \pi \, (a \ \ b-1) \, \pi$ from the proof of Proposition 8.41 , with $c$ in the place of $b - 1$ .

Exercise 8.15.

Part of Problem 8.3 : $h^{-1} \circ \sigma \circ h$ is a permutation of the domain of $h$ . The checker cannot invert a bijection, so $h^{-1}$ arrives as $k$ , together with the two equations that make it the inverse.

What the checker understands

Tactics

intro h	assume the hypothesis of an implication, naming it h
exact e	give the proof outright
apply f	reduce the goal to the hypotheses of f
assumption	close the goal with a hypothesis already present
trivial	close the goal True
exfalso	replace the goal with False
by_contra h	assume the negation of the goal
constructor	split ∧ into both halves, or ↔ into both directions
left / right	choose which half of a ∨ to prove
rcases h with a \| b	argue by cases on a disjunction
obtain ⟨a, b⟩ := h	take a conjunction or an existential apart
cases h	as above, keeping the name
refine e	give the proof with holes left in it
have h : p := …	record an intermediate result
show p	restate the goal in an equal form
use w	give a witness for ∃
specialize h a	instantiate a ∀ hypothesis
rw [h]	rewrite with an equation, ← to go backwards
rfl	both sides compute to the same thing
decide / norm_num	settle a closed computation
tauto	close a goal that is true by pure logic
induction n with k ih	the fifth Peano condition: prove the goal at 0, then at succ k from ih

Results you may cite

Classical.em	∀ (a : Prop), a ∨ ¬a — the law of excluded middle
Classical.byContradiction	∀ {a : Prop}, (¬a → False) → a — proof by contradiction; the tactic by_contra does this for you
Classical.byCases	∀ {a b : Prop}, (a → b) → (¬a → b) → b — split on whether a holds
not_not	∀ {a : Prop}, ¬¬a ↔ a — double negation
not_and_or	∀ {a b : Prop}, ¬(a ∧ b) ↔ ¬a ∨ ¬b — De Morgan
not_or	∀ {a b : Prop}, ¬(a ∨ b) ↔ ¬a ∧ ¬b — De Morgan
not_imp	∀ {a b : Prop}, ¬(a → b) ↔ a ∧ ¬b
and_comm	∀ {a b : Prop}, a ∧ b ↔ b ∧ a
or_comm	∀ {a b : Prop}, a ∨ b ↔ b ∨ a
Set.ext	∀ {A B : Obj}, (∀ x : Obj, x ∈ A ↔ x ∈ B) → A = B — extensionality: sets with the same elements are equal
Set.ext_iff	∀ {A B : Obj}, A = B ↔ (∀ x : Obj, x ∈ A ↔ x ∈ B) — extensionality and substitution, in one biconditional
Set.subset_antisymm	∀ {A B : Obj}, A ⊆ B → B ⊆ A → A = B — mutual inclusion is equality
Set.empty_subset	∀ {A : Obj}, ∅ ⊆ A — the empty set is a subset of every set
Set.pair_eq	∀ {a b c d : Obj}, ((a, b) = (c, d)) ↔ (a = c ∧ b = d) — two ordered pairs are equal exactly when their coordinates are
Nat.succ_inj	∀ {m n : ℕ}, succ m = succ n → m = n — the third Peano condition: the successor is injective
Nat.succ_ne_zero	∀ (n : ℕ), succ n ≠ 0 — the fourth: zero is nobody's successor
Nat.pred	∀ {n : ℕ}, n ≠ 0 → ∃ m : ℕ, n = succ m — predecessors: everything but zero is a successor
Nat.add_zero	∀ (m : ℕ), m + 0 = m — the first clause of addition
Nat.add_succ	∀ (m n : ℕ), m + succ n = succ (m + n) — the second clause of addition
Nat.zero_add	∀ (n : ℕ), 0 + n = n — addition from the left
Nat.succ_add	∀ (m n : ℕ), succ m + n = succ (m + n) — addition from the left, at a successor
Nat.add_assoc	∀ (m n p : ℕ), (m + n) + p = m + (n + p) — addition is associative
Nat.add_comm	∀ (m n : ℕ), m + n = n + m — addition is commutative
Nat.add_ne_zero	∀ {a : ℕ} (b : ℕ), a ≠ 0 → a + b ≠ 0 — positivity is absorbing
Nat.mul_zero	∀ (m : ℕ), m * 0 = 0 — the first clause of multiplication
Nat.mul_succ	∀ (m n : ℕ), m * succ n = m * n + m — the second clause of multiplication
Nat.zero_mul	∀ (m : ℕ), 0 * m = 0 — multiplication from the left
Nat.succ_mul	∀ (m n : ℕ), succ m * n = m * n + n — multiplication from the left, at a successor
Nat.add_right_cancel	∀ {m n k : ℕ}, m + k = n + k → m = n — cancellation, from the last sheet
Nat.add_eq_zero	∀ {m n : ℕ}, m + n = 0 → m = 0 ∧ n = 0 — a sum is zero only when both parts are, from the last sheet
Nat.mul_comm	∀ (m n : ℕ), m * n = n * m — multiplication is commutative, from the last sheet
Nat.mul_add	∀ (m n p : ℕ), m * (n + p) = m * n + m * p — multiplication distributes over addition, from the last sheet
Nat.mul_assoc	∀ (m n p : ℕ), (m * n) * p = m * (n * p) — multiplication associates, from the problems of the last chapter
Nat.add_mul	∀ (m n p : ℕ), (m + n) * p = m * p + n * p — distributivity on the other side
Nat.add_left_cancel	∀ {a m n : ℕ}, a + m = a + n → m = n — uniqueness of differences
Nat.lt_trichotomy	∀ (m n : ℕ), m < n ∨ m = n ∨ n < m — trichotomy, from the theorem that ℕ is strictly ordered
Nat.lt_irrefl	∀ (n : ℕ), ¬(n < n) — anti-reflexivity, from the last sheet
Nat.lt_trans	∀ {m n p : ℕ}, m < n → n < p → m < p — transitivity of the strict order, from the last sheet
Nat.lt_succ_self	∀ (n : ℕ), n < succ n — every number is below its successor, from the last sheet
Nat.not_lt_zero	∀ {n : ℕ}, ¬(n < 0) — nothing lies below zero
Nat.lt_succ_iff	∀ {m n : ℕ}, m < succ n ↔ m < n ∨ m = n — nothing lies strictly between n and succ n
Num.inj	∀ {m n : ℕ}, ↑m = ↑n → m = n — distinct numbers name distinct objects of ω
swap_apply_left	∀ (a b : Obj), swap a b a = b — the transposition sends a to b
swap_apply_right	∀ (a b : Obj), swap a b b = a — and b to a
swap_apply_of_ne_of_ne	∀ {a b x : Obj}, x ≠ a → x ≠ b → swap a b x = x — and fixes every other point
swap_swap	∀ (a b x : Obj), swap a b (swap a b x) = x — a transposition is its own inverse
Function.iterate_zero_apply	∀ (f : Obj → Obj) (x : Obj), f^[0] x = x — the first clause of the powers of a map
Function.iterate_succ_apply	∀ (f : Obj → Obj) (n : ℕ) (x : Obj), f^[succ n] x = f^[n] (f x) — the second clause: f^[succ n] is f^[n] ∘ f
Function.iterate_add_apply	∀ (f : Obj → Obj) (m n : ℕ) (x : Obj), f^[m + n] x = f^[m] (f^[n] x) — the first law of exponents
Nat.factorial_zero	0 ! = succ 0 — the first clause of the factorial
Nat.factorial_succ	∀ (n : ℕ), (succ n) ! = succ n * n ! — the second clause of the factorial
Nat.choose_zero_right	∀ (n : ℕ), choose n 0 = succ 0 — the empty set is the one 0-subset
Nat.choose_eq_zero_of_lt	∀ {n k : ℕ}, n < k → choose n k = 0 — no subset is larger than the whole
Nat.choose_succ_succ	∀ (n k : ℕ), choose (succ n) (succ k) = choose n k + choose n (succ k) — Pascal's identity

From the logical core

And.intro	∀ {a b : Prop}, a → b → a ∧ b
And.left	∀ {a b : Prop}, a ∧ b → a
And.right	∀ {a b : Prop}, a ∧ b → b
And.symm	∀ {a b : Prop}, a ∧ b → b ∧ a
Or.inl	∀ {a b : Prop}, a → a ∨ b
Or.inr	∀ {a b : Prop}, b → a ∨ b
Or.elim	∀ {a b c : Prop}, a ∨ b → (a → c) → (b → c) → c
Or.symm	∀ {a b : Prop}, a ∨ b → b ∨ a
Iff.intro	∀ {a b : Prop}, (a → b) → (b → a) → (a ↔ b)
Iff.mp	∀ {a b : Prop}, (a ↔ b) → a → b
Iff.mpr	∀ {a b : Prop}, (a ↔ b) → b → a
Iff.symm	∀ {a b : Prop}, (a ↔ b) → (b ↔ a)
Iff.rfl	∀ {a : Prop}, a ↔ a
Iff.trans	∀ {a b c : Prop}, (a ↔ b) → (b ↔ c) → (a ↔ c)
True.intro	True
False.elim	∀ {a : Prop}, False → a
absurd	∀ {a b : Prop}, a → ¬a → b
id	∀ {a : Prop}, a → a
mt	∀ {a b : Prop}, (a → b) → ¬b → ¬a
Eq.refl	∀ {α : Type} (a : α), a = a
Eq.symm	∀ {α : Type} {a b : α}, a = b → b = a
Eq.trans	∀ {α : Type} {a b c : α}, a = b → b = c → a = c
congrArg	∀ {α : Type} {β : Type} {a b : α} (f : α → β), a = b → f a = f b
Exists.intro	∀ {α : Type} {p : α → Prop} (w : α), p w → ∃ x : α, p x
Exists.elim	∀ {α : Type} {p : α → Prop} {b : Prop}, (∃ x : α, p x) → (∀ y : α, p y → b) → b