Layered permutation

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