Vexillary permutation

In mathematics, a vexillary permutation is a permutation μ of the positive integers containing no subpermutation isomorphic to the permutation (2143); in other words, there do not exist four numbers i < j < k < l with μ(j) < μ(i) < μ(l) < μ(k). They were introduced by Lascoux and Schützenberger (1982, 1985). The word "vexillary" means flag-like, and comes from the fact that vexillary permutations are related to flags of modules.

Guibert, Pergola & Pinzani (2001) showed that vexillary involutions are enumerated by Motzkin numbers.

See also

• Riffle shuffle permutation, a subclass of the vexillary permutations