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
to
can be uniquely described by the subset of the numbers from
to
that are the first element in a reversed block. (The number
is always the first element in its reversed block, so it is redundant for this description.) Because there are
subsets of the numbers from
to
, there are also
layered permutation of length
.
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
.
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
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
elements. For
these numbers are
:1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, ...
and in general they are given by the formula
:
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