HOME

TheInfoList



OR:

In the mathematics of
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
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. To see how the direct sum is used in abstract algebra, consider a more ...
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 :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 permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the p ...
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 to n can be uniquely described by the subset of the numbers from 1 to 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 to 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 permutation A Gilbreath shuffle is a way to shuffle a deck of cards, named after mathematician Norman Gilbreath (also known for Gilbreath's conjecture). Gilbreath's principle describes the properties of a deck that are preserved by this type of shuffle, and ...
s 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 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: * Involute, a construction in the differential geometry of curves * '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...
. 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 permutation In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 3 ...
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 (Georgi ...
, pages = P23:1–P23:5 , title = Universal layered permutations , volume = 25 , year = 2018
{{citation , last = Bóna , first = Miklós , authorlink = Miklós Bóna , doi = 10.1006/jcta.1998.2908 , 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 applicat ...
, mr = 1659444 , 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-access = free
{{citation , last1 = Egge , first1 = Eric S. , last2 = Mansour , first2 = Toufik , arxiv = math/0209255 , journal = The Australasian Journal of Combinatorics , mr = 2080455 , pages = 75–84 , title = 231-avoiding involutions and Fibonacci numbers , volume = 30 , year = 2004 {{citation , last = Gray , first = Daniel , doi = 10.1007/s00373-014-1429-x , issue = 4 , journal = Graphs and Combinatorics , mr = 3357666 , pages = 941–952 , title = Bounds on superpatterns containing all layered permutations , volume = 31 , year = 2015 {{citation , last = Robertson , first = Aaron , arxiv = math/0012029 , doi = 10.1006/aama.2001.0749 , issue = 2-3 , journal = Advances in Applied Mathematics , mr = 1868980 , pages = 548–561 , title = Permutations restricted by two distinct patterns of length three , volume = 27 , year = 2001 Permutation patterns