Separable permutation
Encyclopedia
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 can also be characterized as the permutations that contain
neither 2413 nor 3142. They are enumerated by the Schröder numbers
.
Separable permutations first arose in the work of , who showed that they are precisely the permutations which can be sorted by an arbitrary number of stacks
in series. showed that the permutation matrix of π fills up under bootstrap percolation if and only if π is separable. The term "separable permutation" was introduced later by .
Separable permutations are the permutation analogues of complement-reducible graphs
and series-parallel partial order
s.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
mathematics, a separable permutation is a permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
that can be obtained from the trivial permutation 1 by direct sums
Direct sum of permutations
In combinatorial mathematics, the direct sum of the permutation π of length m and the permutation σ of length n is the permutation of length m + n defined by...
and skew sums
Skew sum of permutations
In combinatorial mathematics, the skew sum of the permutation π of length m and the permutation σ of length n is the permutation of length m + n defined by...
. Separable permutations can also be characterized as the permutations that contain
Permutation pattern
In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. The permutation π, written as a word in one-line notation , is said to contain the permutation σ if there exists a subsequence of entries of π that has the same...
neither 2413 nor 3142. They are enumerated by the Schröder numbers
Schröder number
In mathematics, a Schröder number describes the number of paths from the southwest corner of an n × n grid to the northeast corner , using only single steps north, northeast, or east, that do not rise above the SW–NE diagonal.The first few Schröder numbers are-Examples:The following...
.
Separable permutations first arose in the work of , who showed that they are precisely the permutations which can be sorted by an arbitrary number of stacks
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
in series. showed that the permutation matrix of π fills up under bootstrap percolation if and only if π is separable. The term "separable permutation" was introduced later by .
Separable permutations are the permutation analogues of complement-reducible graphs
Cograph
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
and series-parallel partial order
Series-parallel partial order
In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations....
s.