algebraic combinatorics Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algeb ...

, a Bender–Knuth involution is an

involution Involution may refer to: * Involute, a construction in the differential geometry of curves * '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...

on the set of semistandard tableaux, introduced by in their study of

plane partition In mathematics and especially in combinatorics, a plane partition is a two-dimensional array of nonnegative integers \pi_ (with positive number, positive integer indices ''i'' and ''j'') that is nonincreasing in both indices. This means that : \pi ...

Definition

The Bender–Knuth involutions σ_''k'' are defined for integers ''k'', and act on the set of semistandard skew Young tableaux of some fixed shape μ/ν, where μ and ν are partitions. It acts by changing some of the elements ''k'' of the tableau to ''k'' + 1, and some of the entries ''k'' + 1 to ''k'', in such a way that the numbers of elements with values ''k'' or ''k'' + 1 are exchanged. Call an entry of the tableau free if it is ''k'' or ''k'' + 1 and there is no other element with value ''k'' or ''k'' + 1 in the same column. For any ''i'', the free entries of row ''i'' are all in consecutive columns, and consist of ''a''_''i'' copies of ''k'' followed by ''b''_''i'' copies of ''k'' + 1, for some ''a''_''i'' and ''b''_''i''. The Bender–Knuth involution σ_''k'' replaces them by ''b''_''i'' copies of ''k'' followed by ''a''_''i'' copies of ''k'' + 1.

Applications

Bender–Knuth involutions can be used to show that the number of semistandard skew tableaux of given shape and weight is unchanged under permutations of the weight. In turn this implies that the Schur function of a partition is a symmetric function. Bender–Knuth involutions were used by to give a short proof of the

Littlewood–Richardson rule In mathematics, the Littlewood–Richardson rule is a combinatorial description of the coefficients that arise when decomposing a product of two Schur functions as a linear combination of other Schur functions. These coefficients are natural number ...

References

* * {{DEFAULTSORT:Bender-Knuth involution Symmetric functions Algebraic combinatorics Combinatorial algorithms Permutations