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.^[1]

One of the earlier works establishing the significance of layered permutations was Bóna (1999), which established the Stanley–Wilf conjecture for classes of permutations forbidding a layered permutation, before the conjecture was proven more generally.^[2]

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 {\displaystyle 1} to n {\displaystyle n} can be uniquely described by the subset of the numbers from 1 {\displaystyle 1} to n − 1 {\displaystyle n-1} that are the first element in a reversed block. (The number n {\displaystyle n} is always the first element in its reversed block, so it is redundant for this description.) Because there are 2 n − 1 {\displaystyle 2^{n-1}} subsets of the numbers from 1 {\displaystyle 1} to n − 1 {\displaystyle n-1} , there are also 2 n − 1 {\displaystyle 2^{n-1}} layered permutation of length n {\displaystyle 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 2 n − 1 {\displaystyle 2^{n-1}} .^[3]

The shortest superpattern of the layered permutations of length n {\displaystyle n} is itself a layered permutation. Its length is a sorting number, the number of comparisons needed for binary insertion sort to sort n + 1 {\displaystyle n+1} elements.^[1][4] For n = 1 , 2 , 3 , … {\displaystyle n=1,2,3,\dots } these numbers are

1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, ... (sequence A001855 in the OEIS)

and in general they are given by the formula

( n + 1 ) ⌈ log 2 ⁡ ( n + 1 ) ⌉ − 2 ⌈ log 2 ⁡ ( n + 1 ) ⌉ + 1. {\displaystyle (n+1){\bigl \lceil }\log _{2}(n+1){\bigr \rceil }-2^{\left\lceil \log _{2}(n+1)\right\rceil }+1.} ^[1]

Every layered permutation is an involution. They are exactly the 231-avoiding involutions, and they are also exactly the 312-avoiding involutions.^[5]

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.