Layered permutation

In the mathematics of permutations, a layered permutation is a permutation that reverses contiguous blocks of elements. Equivalently, it is the direct sum of decreasing permutations.
One of the earlier works establishing the significance of layered permutations was , which established the Stanley–Wilf conjecture for classes of permutations forbidding a layered permutation, before the conjecture was proven more generally.
Example.
For instance, the layered permutations of length four, with the reversed blocks separated by spaces, are the eight permutations
Characterization by forbidden patterns.
The layered permutations can also be equivalently described as the permutations that do not contain the permutation patterns 231 or 312. That is, no three elements in the permutation (regardless of whether they are consecutive) have the same ordering as either of these forbidden triples.
Enumeration.
A layered permutation on the numbers from formula_1 to formula_2 can be uniquely described by the subset of the numbers from formula_1 to formula_4 that are the first element in a reversed block. (The number formula_2 is always the first element in its reversed block, so it is redundant for this description.) Because there are formula_6 subsets of the numbers from formula_1 to formula_4, there are also formula_6 layered permutation of length formula_2.
The layered permutations are Wilf equivalent to other permutation classes, meaning that the numbers of permutations of each length are the same. For instance, the Gilbreath permutations are counted by the same function formula_6.
Superpatterns.
The shortest superpattern of the layered permutations of length formula_2 is itself a layered permutation. Its length is a sorting number, the number of comparisons needed for binary insertion sort to sort formula_13 elements. For formula_14 these numbers are
and in general they are given by the formula
Related permutation classes.
Every layered permutation is an involution. They are exactly the 231-avoiding involutions, and they are also exactly the 312-avoiding involutions.
The layered permutations are a subset of the stack-sortable permutations, which forbid the pattern 231 but not the pattern 312.
Like the stack-sortable permutations, they are also a subset of the separable permutations, the permutations formed by recursive combinations of direct and skew sums.