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.
For instance, the layered permutations of length four, with the reversed blocks separated by spaces, are the eight permutations
1 2 3 4
1 2 43
1 32 4
1 432
21 3 4
21 43
321 4
4321
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.
A layered permutation on the numbers from
1
n
1
n-1
n
2n-1
1
n-1
2n-1
n
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
2n-1
The shortest superpattern of the layered permutations of length
n
n+1
n=1,2,3,...
1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, ... and in general they are given by the formula
(n+1)l\lceillog2(n+1)r\rceil-
\left\lceillog2(n+1)\right\rceil | |
2 |
+1.
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.