The Bender–Knuth involution is a combinatorial involution defined on the set of semi-standard Young tableaux (or equivalently, on matrices with non-negative integer entries). It was introduced by Edward A. Bender and Donald E. Knuth in their 1972 paper "The enumeration of plane partitions" as a tool to prove the symmetry of Schur functions.
For a fixed integer $i \geq 1$, the involution $\tau_i$ acts on a semi-standard Young tableau $T$ by modifying the entries equal to $i$ and $i+1$ in each row independently. Within a given row, suppose there are $a$ entries equal to $i$ and $b$ entries equal to $i+1$. The involution replaces these with $b$ entries equal to $i$ and $a$ entries equal to $i+1$, preserving the semi-standard property (weakly increasing rows, strictly increasing columns). The positions of the other entries remain unchanged.
The map $\tau_i$ is an involution ($\tau_i^2 = \text{id}$) and preserves the shape of the tableau. It changes the weight (content) of the tableau by swapping the number of $i$'s and $(i+1)$'s. The group generated by the $\tau_i$ is isomorphic to the symmetric group, providing a combinatorial proof that the Schur polynomial $s_\lambda(x_1, x_2, \dots)$ is symmetric in its variables.
The involution is a fundamental component in the combinatorial theory of the Robinson–Schensted–Knuth (RSK) correspondence and the theory of crystal bases for quantum groups, where it corresponds to the Kashiwara operators (or the action of simple reflections in the Weyl group).
