# Separable permutation > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Separable_permutation > Markdown URL: https://mediated.wiki/source/Separable_permutation.md > Source: https://en.wikipedia.org/wiki/Separable_permutation > Source revision: 1292331527 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{multiple image | direction = vertical | image1 = Separable Permutation qtl1.svg | image2 = Separable permutation qtl2.svg | caption2 = Block structuring of the (transposed) permutation matrix of the separable permutation (4,5,2,1,3,8,6,7) and corresponding labeled binary tree; colors indicate depth in the tree }} In [combinatorial](/source/combinatorics) mathematics, a '''separable permutation''' is a [permutation](/source/permutation) that can be obtained from the trivial permutation 1 by [direct sums](/source/Direct_sum_of_permutations) and [skew sums](/source/Skew_sum_of_permutations).{{harvtxt|Kitaev|2011}}, p. 57. Separable permutations may be characterized by the forbidden [permutation pattern](/source/permutation_pattern)s 2413 and 3142;{{harvtxt|Bose|Buss|Lubiw|1998}}; {{harvtxt|Kitaev|2011}}, Theorem 2.2.36, p. p.58. they are also the permutations whose [permutation graph](/source/permutation_graph)s are [cograph](/source/cograph)s and the permutations that [realize](/source/Order_dimension) the [series-parallel partial order](/source/series-parallel_partial_order)s. It is possible to test in [polynomial time](/source/polynomial_time) whether a given separable permutation is a pattern in a larger permutation, or to find the longest common subpattern of two separable permutations. ==Definition and characterization== thumb|A large typical separable permutation {{harvtxt|Bose|Buss|Lubiw|1998}} define a separable permutation to be a permutation that has a ''separating tree'': a rooted [binary tree](/source/binary_tree) in which the elements of the permutation appear (in permutation order) at the leaves of the tree, and in which the descendants of each tree node form a contiguous subset of these elements. Each interior node of the tree is either a positive node in which all descendants of the left child are smaller than all descendants of the right node, or a negative node in which all descendants of the left node are greater than all descendants of the right node. There may be more than one tree for a given permutation: if two nodes that are adjacent in the same tree have the same sign, then they may be replaced by a different pair of nodes using a [tree rotation](/source/tree_rotation) operation. Each subtree of a separating tree may be interpreted as itself representing a smaller separable permutation, whose element values are determined by the shape and sign pattern of the subtree. A one-node tree represents the trivial permutation, a tree whose root node is positive represents the [direct sum of permutations](/source/direct_sum_of_permutations) given by its two child subtrees, and a tree whose root node is negative represents the [skew sum](/source/Skew_sum_of_permutations) of the permutations given by its two child subtrees. In this way, a separating tree is equivalent to a construction of the permutation by direct and skew sums, starting from the trivial permutation. As {{harvtxt|Bose|Buss|Lubiw|1998}} prove, separable permutations may also be characterized in terms of [permutation pattern](/source/permutation_pattern)s: a permutation is separable if and only if it contains neither 2413 nor 3142 as a pattern. The separable permutations also have a characterization from [algebraic geometry](/source/algebraic_geometry): if a collection of distinct real polynomials all have equal values at some number {{mvar|x}}, then the permutation that describes how the numerical ordering of the polynomials changes at {{mvar|x}} is separable, and every separable permutation can be realized in this way.{{harvtxt|Ghys|2017}}, p. 15. ==Combinatorial enumeration== The separable permutations are enumerated by the [Schröder number](/source/Schr%C3%B6der_number)s. That is, there is one separable permutation of length one, two of length two, and in general the number of separable permutations of a given length (starting with length one) is :1, 2, 6, 22, 90, 394, 1806, 8558, .... {{OEIS|A006318}} This result was proven for a class of [permutation matrices](/source/permutation_matrix) equivalent to the separable permutations by {{harvtxt|Shapiro|Stephens|1991}}, by using a canonical form of the separating tree in which the right child of each node has a different sign than the node itself and then applying the theory of [generating function](/source/generating_function)s to these trees. Another proof applying more directly to separable permutations themselves, was given by {{harvtxt|West|1995}}.See {{harvtxt|Kitaev|2011}}, Theorem 2.2.45, p. 60. ==Algorithms== {{harvtxt|Bose|Buss|Lubiw|1998}} showed that it is possible to determine in [polynomial time](/source/polynomial_time) whether a given separable permutation is a pattern in a larger permutation, in contrast to the same problem for non-separable permutations, which is [NP-complete](/source/NP-complete). The problem of finding the longest separable pattern that is common to a set of input permutations may be solved in polynomial time for a fixed number of input permutations, but is NP-hard when the number of input permutations may be variable, and remains NP-hard even when the inputs are all themselves separable.{{sfnp|Bouvel|Rossin|Vialette|2007}} ==History== Separable permutations first arose in the work of {{harvtxt|Avis|Newborn|1981}}, who showed that they are precisely the permutations which can be sorted by an arbitrary number of ''pop-stacks'' in series, where a pop-stack is a restricted form of [stack](/source/Stack_(data_structure)) in which any pop operation pops all items at once. {{harvtxt|Shapiro|Stephens|1991}} considered separable permutations again in their study of [bootstrap percolation](/source/bootstrap_percolation), a process in which an initial [permutation matrix](/source/permutation_matrix) is modified by repeatedly changing to one any matrix coefficient that has two or more [orthogonal neighbors](/source/Von_Neumann_neighborhood) equal to one. As they show, the class of permutations that are transformed by this process into the all-one matrix is exactly the class of separable permutations. The term "separable permutation" was introduced later by {{harvtxt|Bose|Buss|Lubiw|1998}}, who considered them for their algorithmic properties. ==Related structures== thumb|The separable permutation 43512 and its corresponding permutation graph Every permutation can be used to define a [permutation graph](/source/permutation_graph), a graph whose vertices are the elements of the permutation and whose edges are the [inversions](/source/Inversion_(discrete_mathematics)) of the permutation. In the case of a separable permutation, the structure of this graph can be read off from the separation tree of the permutation: two vertices of the graph are adjacent if and only if their [lowest common ancestor](/source/lowest_common_ancestor) in the separation tree is negative. The graphs that can be formed from trees in this way are called [cograph](/source/cograph)s (short for complement-reducible graphs) and the trees from which they are formed are called cotrees. Thus, the separable permutations are exactly the permutations whose permutation graphs are cographs.{{sfnp|Bose|Buss|Lubiw|1998}} The [forbidden graph characterization](/source/forbidden_graph_characterization) of the cographs (they are the graphs with no four-vertex [induced path](/source/induced_path)) corresponds to the two four-element forbidden patterns of the separable permutations. Separable permutations are also closely related to [series-parallel partial order](/source/series-parallel_partial_order)s, the [partially ordered set](/source/partially_ordered_set)s whose comparability graphs are the cographs. As with the cographs and separable permutations, the series-parallel partial orders may also be characterized by four-element forbidden suborders. Every permutation defines a partial order whose [order dimension](/source/order_dimension) is two, in which the elements to be ordered are the elements of the permutation, and in which ''x'' ≤ ''y'' whenever ''x'' has a smaller numerical value than ''y'' and is left of it in the permutation. The permutations for which this partial order is series-parallel are exactly the separable permutations. Separable permutations may also be used to describe hierarchical partitions of rectangles into smaller rectangles (so-called "slicing floorplans", used for instance in the design of [integrated circuits](/source/Very-large-scale_integration)) by using the positive and negative signs of the separating tree to describe horizontal and vertical slices of a rectangle into smaller rectangles.{{harvtxt|Szepieniec|Otten|1980}}; {{harvtxt|Ackerman|Barequet|Pinter|2006}} The separable permutations include as a special case the [stack-sortable permutation](/source/stack-sortable_permutation)s, which avoid the pattern 231. ==Notes== {{reflist}} ==References== *{{citation | last1 = Ackerman | first1 = Eyal | last2 = Barequet | first2 = Gill | last3 = Pinter | first3 = Ron Y. | doi = 10.1016/j.dam.2006.03.018 | issue = 12 | journal = Discrete Applied Mathematics | mr = 2233287 | pages = 1674–1684 | title = A bijection between permutations and floorplans, and its applications | volume = 154 | year = 2006| doi-access = free }} *{{citation | last1=Avis | first1=David | author1-link = David Avis | last2=Newborn | first2=Monroe | author2-link = Monty Newborn | title=On pop-stacks in series | mr = 0624050 | year=1981 | journal=Utilitas Mathematica | volume=19 | pages=129–140}}. *{{citation | contribution = Longest common separable pattern among permutations | first1 = Mathilde | last1 = Bouvel | first2 = Dominique | last2 = Rossin | first3 = Stéphane | last3 = Vialette | title = Combinatorial Pattern Matching (CPM 2007) | series = Lecture Notes in Computer Science | publisher = Springer | volume = 4580 | year = 2007 | pages = 316–327 | doi = 10.1007/978-3-540-73437-6_32| isbn = 978-3-540-73436-9 }}. *{{citation | last1=Bose | first1=Prosenjit | author1-link = Jit Bose | last2=Buss | first2=Jonathan | last3=Lubiw | first3=Anna | author3-link = Anna Lubiw | title=Pattern matching for permutations | mr = 1620935 | year=1998 | journal=[Information Processing Letters](/source/Information_Processing_Letters) | volume=65 | issue=5 | pages=277–283 | doi=10.1016/S0020-0190(97)00209-3 }}. *{{citation | last = Ghys | first = Étienne | author-link = Étienne Ghys | arxiv = 1612.06373 | isbn = 978-2-84788-939-0 | mr = 3702027 | publisher = ENS Éditions | location = Lyon | title = A Singular Mathematical Promenade | year = 2017}} * {{citation | last=Kitaev | author-link = Sergey Kitaev | first=Sergey | title=Patterns in permutations and words | zbl=1257.68007 | series=Monographs in Theoretical Computer Science. An EATCS Series | location=Berlin | publisher=[Springer-Verlag](/source/Springer-Verlag) | isbn=978-3-642-17332-5 | year=2011 | doi = 10.1007/978-3-642-17333-2 | contribution = 2.2.5 Separable permutations | pages = 57–66}}. *{{citation | last1=Shapiro | first1=Louis | last2=Stephens | first2=Arthur B. | title=Bootstrap percolation, the Schröder numbers, and the ''N''-kings problem | mr = 1093199 | year=1991 | journal=[SIAM Journal on Discrete Mathematics](/source/SIAM_Journal_on_Discrete_Mathematics) | volume=4 | issue=2 | pages=275–280 | doi=10.1137/0404025}}. *{{citation | last1 = Szepieniec | first1 = A. A. | last2 = Otten | first2 = R. H. J. M. | title = 17th Conf. on Design Automation (DAC 1980) | contribution = The genealogical approach to the layout problem | year = 1980 | pages = 535–542 | doi = 10.1145/800139.804582 | isbn = 0-89791-020-6 | s2cid = 2031785 }}. *{{citation | last = West | first = Julian | doi = 10.1016/0012-365X(94)00067-1 | issue = 1–3 | journal = [Discrete Mathematics](/source/Discrete_Mathematics_(journal)) | mr = 1360119 | pages = 247–262 | title = Generating trees and the Catalan and Schröder numbers | volume = 146 | year = 1995| doi-access = free }}. Category:Permutation patterns --- Adapted from the Wikipedia article [Separable permutation](https://en.wikipedia.org/wiki/Separable_permutation) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Separable_permutation?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.