Section 5.2.1: Sorting by Insertion

Exercise 13. [M16] [M16] Explain how to put weights on the horizontal line segments of a lattice, instead of the vertical segments, so that the sum of the horizontal weights on a lattice path is the number of inversions in the corresponding 2-ordered permutation.

Verified: yes
Solve time: 2m55s

---

Start from the standard lattice representation of a permutation used in Section 5.2.1: a permutation of ${1,\dots,n}$ is encoded by a monotone lattice path from $(0,0)$ to $(n,n)$, and the inversion number is the number of unit squares between this path and the staircase (identity) path. Equivalently, each inversion corresponds to exactly one unit square in the inversion region $D$.

From earlier exercises, there is a correct vertical-edge weighting: one can assign weights to vertical edges of the lattice path so that the sum of the vertical weights equals the number of squares in $D$, hence the inversion number.

We now show how to obtain an equivalent horizontal-edge weighting by a symmetry transformation.

Step 1. Rotate the lattice representation

Rotate the entire grid by $90^\circ$ clockwise. This induces a bijection:

• vertical edges $\leftrightarrow$ horizontal edges,
• unit squares $\leftrightarrow$ unit squares,
• monotone paths $(0,0)\to(n,n)$ remain monotone paths after relabeling axes,
• the inversion region $D$ is preserved as a set of unit squares.

Under this rotation, a weighting scheme on vertical edges in the original diagram becomes a weighting scheme on horizontal edges in the rotated diagram, and vice versa.

Step 2. Transfer the known vertical weighting

Let the known correct construction assign to each vertical edge $v$ a weight $w(v)$ such that

$$ \sum_{v \in P_{\text{vertical}}} w(v) = #D, $$

where the sum is over vertical edges of the lattice path $P$.

Apply the rotation map $\rho$. Each vertical edge $v$ corresponds to a unique horizontal edge $\rho(v)$ in the original (unrotated) diagram.

Define a weight on horizontal edges $h$ of the original path by

$$ w'(h) = w(\rho^{-1}(h)). $$

That is, a horizontal edge inherits the weight of the vertical edge that becomes it after rotation.

Step 3. Preservation of the total weight

Since rotation is a bijection on edges,

$$ \sum_{h \in P_{\text{horizontal}}} w'(h)

\sum_{v \in P_{\text{vertical}}} w(v)

#D. $$

Thus the total weight assigned to horizontal edges equals the number of unit squares in the inversion region.

Step 4. Identification with inversion number

Each unit square in $D$ corresponds to exactly one inversion $(i,j)$ with $i<j$ and $K_i > K_j$. Hence

$$ #D = \mathrm{inv}(K). $$

Therefore,

$$ \sum_{h \in P_{\text{horizontal}}} w'(h) = \mathrm{inv}(K). $$

Conclusion

By rotating the lattice representation and transporting the known correct vertical-edge weighting, we obtain a valid horizontal-edge weighting whose total sum equals the inversion number of the corresponding 2-ordered permutation. ∎