Separable permutation

Permutation matrices of all 22 separable permutations of length four with the associated block structure

In combinatorics, a separable permutation is a permutation that can be represented by direct or skewed sums of trivial permutations . The permutation matrices of separable permutations thus have a recursive block structure . A separation tree , a specially designated, ordered binary tree , can be assigned to each separable permutation . The number of separable permutations of fixed length is given by the Schröder numbers . Separable permutations are examined , among other things, in sorting theory.

definition

Separable permutations are defined recursively as follows:

1. The trivial permutation of length one is separable.
2. If the two permutations and are separable, then also their direct sum and their skew sum . ${\displaystyle \pi }$ ${\displaystyle \sigma }$ ${\displaystyle \pi \oplus \sigma }$ ${\displaystyle \pi \ominus \sigma }$

In the case of a direct sum, the second permutation is attached to the first in a shifted manner; in the case of an inclined sum, the first permutation is shifted in front of the second. Separable permutations are thus characterized by the fact that they can be represented by direct or skewed sums of trivial permutations.

Examples

The two permutations of length two are separable, as they have with the trivial permutation representations ${\displaystyle 1=(1)}$

${\displaystyle (1,2)=1\oplus 1}$

${\displaystyle (2,1)=1\ominus 1}$

The six permutations of length three are also all separable because they have the following representations:

${\displaystyle (1,2,3)=(1\oplus 1)\oplus 1=1\oplus (1\oplus 1)}$

${\displaystyle (1,3,2)=1\oplus (1\ominus 1)}$

${\displaystyle (2,1,3)=(1\ominus 1)\oplus 1}$

${\displaystyle (2,3,1)=(1\oplus 1)\ominus 1}$

${\displaystyle (3,1,2)=1\ominus (1\oplus 1)}$

${\displaystyle (3,2,1)=1\ominus (1\ominus 1)=(1\ominus 1)\ominus 1}$

Of the 24 permutations of length four, two are not separable, namely the permutations and . ${\displaystyle (2,4,1,3)}$ ${\displaystyle (3,1,4,2)}$

Further representations

Permutation matrices

Block decomposition of the transposed permutation matrix of the separable permutation (4,3,5,1,2,7,8,6)

The permutation matrices of separable permutations are characterized by the following recursive block structure . If there is a separable permutation of length and the associated permutation matrix, then there is an index such that either the two sub-matrices ${\displaystyle \pi }$ ${\displaystyle n>1}$ ${\displaystyle P\in \{0,1\}^{n\times n}}$ ${\displaystyle k\in \{1,\ldots ,n-1\}}$

${\displaystyle P_{\{1,\ldots ,k\},\{k+1,\ldots ,n\}}}$   and   ${\displaystyle P_{\{k+1,\ldots ,n\},\{1,\ldots ,k\}}}$

or the two sub-matrices

${\displaystyle P_{\{1,\ldots ,n-k\},\{1,\ldots ,k\}}}$   and   ${\displaystyle P_{\{n-k+1,\ldots ,n\},\{k+1,\ldots ,n\}}}$

Are zero matrices . In the first case, the permutation is represented as a direct sum

${\displaystyle \pi =(\pi (1),\ldots ,\pi (k))\oplus (\pi (k+1)-k,\ldots ,\pi (n)-k)}$

and in the second case the representation as a skewed sum

${\displaystyle \pi =(\pi (1)-k,\ldots ,\pi (n-k)-k)\ominus (\pi (n-k+1),\ldots ,\pi (n))}$.

The two summands are in turn separable permutations by definition and therefore also have a corresponding block structure. The block decomposition can thus be continued recursively up to the trivial permutations that form blocks of size . The block decomposition of a given separable permutation does not have to be unique, since the formation of purely direct and purely skewed sums is associative . For example, in the case of an identical permutation, any number can be chosen as the separating index. ${\displaystyle 1\times 1}$ ${\displaystyle k<n}$

Separation trees

Associated separation tree

Each separable permutation, a separation tree ( English separating tree ), a specially designated ordered binary tree , are assigned. The leaves of the separation tree are labeled with the numbers from left to right . One or one is assigned to the inner nodes , depending on whether the two associated subtrees are combined by a direct or an oblique sum. In the first case, all subsequent leaves of the left subtree are smaller than those of the right subtree, in the second case the other way round. Each subtree in turn represents a separable permutation with correspondingly shifted numbers, with the leaves standing for trivial permutations. The leaves of each subtree therefore form a set of consecutive numbers. ${\displaystyle \pi (1),\ldots ,\pi (n)}$ ${\displaystyle +}$ ${\displaystyle -}$

Since the sum representation of a separable permutation does not have to be unique, different separation trees can be assigned to a given separable permutation. However, these trees can be converted into one another by rotating neighboring nodes with the same sign. Accordingly, a separable permutation has an unambiguous summary representation precisely when adjacent nodes in the assigned separation tree each have different signs.

The missing permutation can also be read from the separation tree . Two leaves are defective if and only if their smallest common predecessor has a negative sign.

Bracketed spelling

Separable permutations can also be written in brackets as follows. First, the numbers from to are noted next to each other in ascending order. You can now put brackets around two or more numbers, provided they are nested correctly. A bracket reverses the order of all characters within the bracket. After evaluating all brackets from outside to inside, the associated separable permutation in tuple notation then results. For example, there are the following possible brackets for the permutations of length three: ${\displaystyle 1}$ ${\displaystyle n}$

Tuple notation	(1,2,3)	(1,3,2)	(2,1,3)	(2,3,1)	(3.1.2)	(3.2.1)
Bracketed spelling	1 2 3	1 [2 3]	[1 2] 3	[1 [2 3]]	[[1 2] 3]	[1 2 3]

Such brackets can be converted into a separation tree by having two adjacent numbers or blocks of brackets form an inner node in the tree. If the nesting depth is even, then it is a positive node, if it is odd, it is a negative node. Three or more adjacent numbers or blocks of brackets can be converted into nodes with the same sign in any order.

properties

number

Separable permutations can be recursively enumerated by adding a root node if the right subtree has a different sign than the root

The number of separable permutations of a given length can be determined by listing possible separation trees. A clear assignment of a separable permutation to a separation tree can be achieved by the additional condition that the right subtree of an inner node has a different sign than the node itself. Each separable permutation of length can now be generated from two separable permutations of smaller length by adding a new root node . If the root node is marked with , then either the trivial permutation can be chosen as the right subtree, for which there are possibilities, or a separable permutation of length with a negative root, for which there are possibilities. A separable permutation of length with any root can always be selected as the left subtree , for which there are options. If the root node is marked with , you get the same number of possibilities with the opposite sign. Overall, the recursion results for the number of separable permutations of the length ${\displaystyle n+1}$ ${\displaystyle +}$ ${\displaystyle S_{1}=1}$ ${\displaystyle k=2,\ldots ,n}$ ${\displaystyle S_{k}/2}$ ${\displaystyle n-k+1}$ ${\displaystyle S_{n-k+1}}$ ${\displaystyle -}$ ${\displaystyle S_{n}}$ ${\displaystyle n}$

${\displaystyle S_{n+1}=S_{n}+\sum _{k=1}^{n}S_{k}\cdot S_{n-k+1}}$.

The numbers are called (large) Schröder numbers and form the sequence ${\displaystyle S_{n}}$

${\displaystyle 1,2,6,22,90,394,1806,\ldots }$   (Follow A006318 in OEIS ).

The generating function for the number of separable permutations is

${\displaystyle g(x)=\sum _{n=1}^{\infty }S_{n}x^{n}={\frac {1-x-{\sqrt {1-6x+x^{2}}}}{2}}}$.

Symmetries

The permutation complementary to a permutation of the length and the corresponding reverse permutation arise through horizontal or vertical mirroring of the permutation matrix. If a permutation is separable, its complementary and reverse permutation are also separable. The inverse of a separable permutation is also separable again, since its permutation matrix is ​​only mirrored on the main diagonal . ${\displaystyle \pi }$ ${\displaystyle n}$ ${\displaystyle \pi ^{-}=(n-\pi (1)+1,\ldots ,n-\pi (n)+1)}$ ${\displaystyle \pi '=(\pi (n),\pi (n-1),\ldots ,\pi (1))}$ ${\displaystyle \pi ^{-1}}$

Permutation pattern

A permutation is separable if and only if it contains neither of the two permutations and as a permutation pattern, i.e. as a partial permutation with this relative order of the elements. Each permutation can also be assigned a permutation graph whose nodes correspond to the elements of the permutation and whose edges correspond to the errors of the permutation. Separable permutations are precisely those permutations whose permutation graphs are co-graphs . Co-graphs are characterized in that they do not have a path of length four as an induced subgraph , which corresponds precisely to the two impermissible permutation patterns. ${\displaystyle (2,4,1,3)}$ ${\displaystyle (3,1,4,2)}$

Whether a given separable permutation forms a pattern within a longer permutation can be checked in polynomial time. For non-separable permutations, this problem is NP-complete .

literature

• Miklós Bóna: Combinatorics of Permutations (=  Discrete Mathematics and Its Applications . No. 72 ). 2nd Edition. CRC Press, 2012, ISBN 1-4398-5051-8 .
• Sergey Kitaev: Patterns in Permutations and Words (=  Monographs in theoretical computer science ). Springer, 2011, ISBN 978-3-642-17333-2 , Chapter 2.2.5.

Individual evidence

1. ↑ D. Avis, M. Newborn: On pop stacks in series . In: Utilitas Mathematica . No. 19 , 1981, p. 129-140 .
2. ↑ ^{a b c} P. Bose, JF Buss, A. Lubiw: Pattern matching for permutations . In: Information Processing Letters . tape 65 , 1998, pp. 277-283 .
3. ^ L. Shapiro, AB Stephens: Bootstrap percolation, the Schröder numbers, and the N-kings problem . In: SIAM Journal on Discrete Mathematics . tape 4 , 1991, pp. 275-280 .
4. ^ MH Albert, MD Atkinson, V. Vatter: Subclasses of the separable permutations . In: Bulletin of the London Mathematical Society . tape 43 , no. 5 , 2011, p. 859-870 .