In the mathematics of

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

s, a layered permutation is a permutation that reverses contiguous blocks of elements. Equivalently, it is the

direct sum The direct sum is an operation between structures in abstract algebra, a branch of mathematics. It is defined differently but analogously for different kinds of structures. As an example, the direct sum of two abelian groups A and B is anothe ...

of decreasing permutations. One of the earlier works establishing the significance of layered permutations was , which established the

Stanley–Wilf conjecture The Stanley–Wilf conjecture, formulated independently by Richard P. Stanley and Herbert Wilf in the late 1980s, states that the growth rate of every proper permutation class is Exponential growth, singly exponential. It was proved by and is no l ...

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 :1 2 3 4 :1 2 43 :1 32 4 :1 432 :21 3 4 :21 43 :321 4 :4321

Characterization by forbidden patterns

The layered permutations can also be equivalently described as the permutations that do not contain the

permutation pattern In combinatorial mathematics and theoretical computer science, a (classical) permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of entries representing the result of a ...

s 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

1

n

can be uniquely described by the subset of the numbers from

1

n-1

that are the first element in a reversed block. (The number

n

is always the first element in its reversed block, so it is redundant for this description.) Because there are

2^

subsets of the numbers from

1

n-1

, there are also

2^

layered permutation of length

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^

Superpatterns

The shortest

superpattern In the mathematical study of permutations and permutation patterns, a superpattern or universal permutation is a permutation that contains all of the patterns of a given length. More specifically, a ''k''-superpattern contains all possible patterns ...

of the layered permutations of length

n

is itself a layered permutation. Its length is a

sorting number In mathematics and computer science, the sorting numbers are a sequence of numbers introduced in 1950 by Hugo Steinhaus for the analysis of comparison sort algorithms. These numbers give the worst-case number of comparisons used by both binary ins ...

, the number of comparisons needed for

binary insertion sort Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two values (0 and 1) for each digit * Binary function, a function that takes two arguments * Binary operation, a mathematical op ...

to sort

n+1

elements. For

n=1,2,3,\dots

these numbers are :1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, ... and in general they are given by the formula :

(n+1)\bigl\lceil\log_2 (n+1)\bigr\rceil - 2^ + 1.

Related permutation classes

Every layered permutation is an

involution Involution may refer to: Mathematics * Involution (mathematics), a function that is its own inverse * Involution algebra, a *-algebra: a type of algebraic structure * Involute, a construction in the differential geometry of curves * Exponentiati ...

. 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 permutation In mathematics and computer science, a stack-sortable permutation (also called a tree permutation) is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable ...

s, which forbid the pattern 231 but not the pattern 312. Like the stack-sortable permutations, they are also a subset of the

separable permutation In combinatorics, combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by Direct sum of permutations, direct sums and Skew sum of permutations, skew sums. Separable permutations may ...

s, the permutations formed by recursive combinations of direct and skew sums.

References

{{reflist, refs= {{citation , last1 = Albert , first1 = Michael , author1-link = Michael H. Albert , last2 = Engen , first2 = Michael , last3 = Pantone , first3 = Jay , last4 = Vatter , first4 = Vincent , issue = 3 , journal =

Electronic Journal of Combinatorics The ''Electronic Journal of Combinatorics'' is a peer-reviewed open access scientific journal covering research in combinatorial mathematics. The journal was established in 1994 by Herbert Wilf (University of Pennsylvania) and Neil Calkin (Geor ...

, pages = Article P3.23, 5 pp. , title = Universal layered permutations , volume = 25 , year = 2018 , arxiv = 1710.04240 , doi = 10.37236/7386 , doi-access = free , mr = 3853875 {{citation , last = Bóna , first = Miklós , authorlink = Miklós Bóna , issue = 1 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicati ...

, pages = 96–104 , series = Series A , title = The solution of a conjecture of Stanley and Wilf for all layered patterns , volume = 85 , year = 1999 , doi = 10.1006/jcta.1998.2908 , doi-access = free , mr = 1659444 {{citation , last1 = Egge , first1 = Eric S. , last2 = Mansour , first2 = Toufik , journal = The Australasian Journal of Combinatorics , pages = 75–84 , title = 231-avoiding involutions and Fibonacci numbers , volume = 30 , year = 2004 , arxiv = math/0209255 , mr = 2080455 {{citation , last = Gray , first = Daniel , issue = 4 , journal = Graphs and Combinatorics , pages = 941–952 , title = Bounds on superpatterns containing all layered permutations , volume = 31 , year = 2015 , doi = 10.1007/s00373-014-1429-x , mr = 3357666 {{citation , last = Robertson , first = Aaron , issue = 2–3 , journal = Advances in Applied Mathematics , pages = 548–561 , title = Permutations restricted by two distinct patterns of length three , volume = 27 , year = 2001 , arxiv = math/0012029 , doi = 10.1006/aama.2001.0749 , mr = 1868980 Permutation patterns