The identity preserves the natural order: if \(i {\lt} j\) then \(\operatorname {id}(i) = i {\lt} j = \operatorname {id}(j)\), so no pair \((i,j)\) with \(i {\lt} j\) satisfies \(\operatorname {id}(i) {\gt} \operatorname {id}(j)\).

(a) The set of inversions of \(\sigma \) is a subset of the set of all pairs \((i,j)\) with \(i {\lt} j\), and the latter has cardinality \(\binom {n}{2}\).

(b) If \(\sigma \) has no inversions, then \(\sigma \) is strictly monotone on \([n]\); a strictly monotone permutation on a finite set must be the identity (since if any \(\sigma (i) {\gt} i\), the sum \(\sum _j \sigma (j)\) would strictly exceed \(\sum _j j\), contradicting bijectivity). Conversely, \(\operatorname {id}\) clearly has no inversions.

(c) The longest element \(w_0\) reverses the ordering, so \(w_0(i) = n+1-i\), making every pair \((i,j)\) with \(i{\lt}j\) an inversion. Thus \(\ell (w_0) = \binom {n}{2}\). Conversely, if \(\ell (\sigma ) = \binom {n}{2}\) then \(\operatorname {inv}(\sigma )\) equals the set of all ordered pairs, so \(\sigma \) is strictly antitone. A strictly antitone permutation on \([n]\) must send \(i\) to \(n+1-i\), i.e., \(\sigma = w_0\).

(d) Each simple transposition \(s_i = \operatorname {swap}(i, i+1)\) has exactly one inversion. Conversely, if \(\sigma \) has exactly one inversion \(\{ (a,b)\} \), then \(b = a + 1\) (otherwise an element between \(a\) and \(b\) would create an additional inversion), and \(\sigma = \operatorname {swap}(a, b) = s_a\).

(e) The permutations with exactly 2 inversions are exactly: products \(s_i s_j\) with \(1 \le i {\lt} j {\lt} n\) (non-adjacent transpositions, contributing \(\binom {n-2}{2}\) permutations) and products \(s_i s_{i-1}\) with \(i \in \{ 2, \ldots , n-1\} \) (adjacent 3-cycles, contributing \(n-2\) permutations). These give \(\binom {n-2}{2} + (n-2) = \frac{(n-2)(n+1)}{2}\) in total.

(f) The bijection \(\sigma \mapsto w_0 \sigma \) satisfies \(\ell (w_0\sigma ) = \binom {n}{2} - \ell (\sigma )\), since \(w_0\) swaps inversions and non-inversions.

Direct computation.

Both send \(i\) to \(n - 1 - i\); the equality follows by extensionality.

Since \(w_0(i) = n+1-i\), if \(i {\lt} j\) then \(w_0(i) = n+1-i {\gt} n+1-j = w_0(j)\).

The map \((a,b) \mapsto (\sigma ^{-1}(b), \sigma ^{-1}(a))\) is a bijection between the inversions of \(\sigma ^{-1}\) and the inversions of \(\sigma \).

A pair \((i,j)\) with \(i {\lt} j\) is an inversion of \(w_0 \sigma \) iff \((w_0 \sigma )(i) {\gt} (w_0 \sigma )(j)\) iff \(\sigma (i) {\lt} \sigma (j)\) (since \(w_0\) reverses the order), which is the condition for \((i,j)\) to be a non-inversion of \(\sigma \). The cardinality identity follows since inversions and non-inversions partition the \(\binom {n}{2}\) ordered pairs.

An inversion \((i,j)\) of \(\sigma \tau \) (i.e., \(i {\lt} j\) and \((\sigma \tau )(i) {\gt} (\sigma \tau )(j)\)) is either an inversion of \(\tau \) (if \(\tau (i) {\gt} \tau (j)\)) or corresponds to an inversion of \(\sigma \) at \((\tau (i), \tau (j))\) (if \(\tau (i) {\lt} \tau (j)\)). Thus \(\operatorname {inv}(\sigma \tau ) \subseteq \operatorname {inv}(\tau ) \cup \tau ^{-1}(\operatorname {inv}(\sigma ))\), and the result follows by cardinality.

The inversions of \(\sigma \) are pairs \((i,j)\) with \(i{\lt}j\) and \(\sigma (i){\gt}\sigma (j)\). The Lehmer entry \(\ell _i(\sigma )\) counts the \(j{\gt}i\) with \(\sigma (i){\gt}\sigma (j)\). Hence the sum \(\sum _i \ell _i(\sigma )\) partitions the set of inversions by first coordinate, so equals \(\ell (\sigma )\).

Let \(\sigma \in S_{n}\), \(i\in [n]\). We can rewrite

Therefore,

This allows recovering \(\sigma (i)\) from \(\ell _i(\sigma )\) and \(\sigma (1),\ldots ,\sigma (i-1)\) by induction on \(i\), proving that \(L\) is injective.

Conversely, given any \(\mathbf{j} = (j_1,\ldots ,j_n) \in H_n\), define \(M(\mathbf{j})\) to be the map \(\sigma :[n]\to [n]\) whose values are determined by

This is well-defined (since \(j_i \le n - i\)) and gives a permutation (since \(\sigma (i) \notin \{ \sigma (1),\ldots ,\sigma (i-1)\} \)). The maps \(L\) and \(M\) are mutually inverse, so \(L\) is bijective.

The elements \(j {\gt} i\) with \(\sigma (j) {\lt} \sigma (i)\) are in bijection (via \(j \mapsto \sigma (j)\)) with elements \(v {\lt} \sigma (i)\) not in the image \(\sigma (\{ 1,\ldots ,i-1\} )\), since these are precisely \([n] \setminus \{ \sigma (1),\ldots ,\sigma (i)\} \) intersected with \(\{ v : v {\lt} \sigma (i)\} \).

The set \(\{ j : j {\gt} i \text{ and } \sigma (j) {\lt} \sigma (i)\} \) is a subset of \(\{ j : j {\gt} i\} \), which has cardinality \(n - 1 - i {\lt} n - i\).

Since \(\mathbf{a} \neq \mathbf{b}\), there exists some index where they differ. By well-founded induction on \(\operatorname {Fin} n\), let \(k\) be the minimal such index. Then \(a_i = b_i\) for all \(i {\lt} k\), and \(a_k \neq b_k\). If \(a_k {\lt} b_k\) then \(\mathbf{a} {\lt}_{\operatorname {lex}} \mathbf{b}\); otherwise \(b_k {\lt} a_k\) and \(\mathbf{b} {\lt}_{\operatorname {lex}} \mathbf{a}\).

The assumption says there exists a smallest \(k \in [n]\) with \(\sigma (k) \neq \tau (k)\) and \(\sigma (k) {\lt} \tau (k)\). For \(i {\lt} k\): \(\sigma (i) = \tau (i)\), so the images \(\sigma (\{ 1,\ldots ,i-1\} )\) and \(\tau (\{ 1,\ldots ,i-1\} )\) agree. Since \(\sigma (i) = \tau (i)\) as well, we get \(\ell _i(\sigma ) = \ell _i(\tau )\).

Let \(Z = [n] \setminus \{ \sigma (1),\ldots ,\sigma (k-1)\} = [n] \setminus \{ \tau (1),\ldots ,\tau (k-1)\} \). Then \(\ell _k(\sigma )\) counts elements of \(Z\) smaller than \(\sigma (k)\), and \(\ell _k(\tau )\) counts elements of \(Z\) smaller than \(\tau (k)\). Since \(\sigma (k) {\lt} \tau (k)\) and \(\sigma (k) \in Z\), every element of \(Z\) smaller than \(\sigma (k)\) is also smaller than \(\tau (k)\), and \(\sigma (k)\) itself is smaller than \(\tau (k)\) but not smaller than \(\sigma (k)\). Thus \(\ell _k(\sigma ) {\lt} \ell _k(\tau )\).

Combining, we get \(L(\sigma ) {\lt}_{\operatorname {lex}} L(\tau )\).

We first show that \(L\) is injective. Let \(\sigma \) and \(\tau \) be two distinct permutations in \(S_n\). Their OLNs are distinct, so by Proposition 3.51 we have either OLN\((\sigma ) {\lt}_{\operatorname {lex}}\) OLN\((\tau )\) or vice versa. In either case, Proposition 3.52 gives \(L(\sigma ) {\lt}_{\operatorname {lex}} L(\tau )\) or \(L(\tau ) {\lt}_{\operatorname {lex}} L(\sigma )\). In particular \(L(\sigma ) \neq L(\tau )\), so \(L\) is injective. Since \(|S_n| = n! = |H_n|\) and \(L\) is injective between finite sets of equal size, the Pigeonhole Principle shows \(L\) is bijective.

Each \(\sigma \in S_{n}\) satisfies

by Proposition 3.46, whence \(x^{\ell (\sigma )} = \prod _{i=1}^{n} x^{\ell _i(\sigma )}\). Therefore

where we substituted \((j_1,\ldots ,j_n)\) for \(L(\sigma )\), which is valid since \(L: S_n \to H_n\) is a bijection (Theorem 3.47). Since \(H_{n} = [n-1]_0 \times [n-2]_0 \times \cdots \times [0]_0\), the product rule gives