Separable Permutation

A permutation is separable in combinatorics a permutation that can be represented by direct or oblique sums of trivial permutations. The permutation matrices separable permutations thus have a recursive block structure. Each separable permutation, a separation tree, a specially designated subordinate binary tree are assigned. The number of permutations of separable fixed length specified by Schroder numbers. Separable permutations are investigated, among others, in the sort theory.

• 4.1 Number
• 4.2 symmetries
• 4.3 Permutationsmuster

Definition

Separable permutations are as follows recursively defined:

In a direct sum while the second permutation of the second is appended moved to the top, moved the first permutation in an oblique sum prefixed. Separable permutations are thus characterized in that they can be represented by direct or oblique sums trivial permutations.

Examples

The two permutations of length two are separable, as they have with the trivial permutation representations

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

Of the 24 permutations of length four two are not separable, namely the permutations and.

Further illustrations

Permutation matrices

The permutation matrices separable permutations are characterized by the following recursive block structure. Is a permutation of the separable length and the corresponding permutation matrix, then there is an index, so that either the two sub-arrays

Or the two sub-arrays

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

And in the second case the display as an inclined sum

The two summands are each in turn, by definition separable permutations and therefore also have a corresponding block structure. The block decomposition can therefore be carried out recursively up to the trivial permutations form the blocks of size. The block decomposition of a given separable permutation, however, need not be unique, since the formation of purely direct and purely slate buzz is associative. For example, can be chosen as divisive index at an identical permutation of each number.

Separation trees

Each separable permutation can be assigned a separation tree (English Separating tree ), a specially designated subordinate binary tree. The leaves of the tree are called separation from left to right with the numbers. The internal nodes A or associated with, depending on whether the two associated sub-trees are combined with a direct or an inclined amount. In the first case all subsequent leaves of the left sub-tree are smaller than those of the right sub-tree, in the second case vice versa. Each subtree again represents a separable permutation with correspondingly shifted numbers, where the leaves are for trivial permutations. Therefore, the leaves of each subtree form a set of consecutive numbers.

After the sum representation of a separable permutation does not have to be unique, a given separable permutation various separation trees can be assigned. However, these trees can be converted by rotation of adjacent nodes with the same sign together. Thus, a separable permutation has exactly then a unique sum representation when in the associated separation tree each adjacent nodes have different signs.

The false readings of the permutation can be read from the separation tree. Two leaves exactly then form a faulty state when its smallest common ancestor has a negative sign.

Bracket notation

Separable permutations can also be written as follows bracket expression. First, the numbers of up in ascending order are listed next to each other. Now you can order two or more numbers are set brackets, provided they are correctly nested. By a clamp, the sequence of all the characters within the bracket is reversed. After evaluation of all the brackets from the outside is then produced the corresponding separable permutation Tupelschreibweise. For example, there are the permutations of the length of the following three possible parantheses:

Such bracketing can be converted into a separation tree by two adjacent numbers or clamp blocks each defining an interior node in the tree. Is the nesting straight, then it is a positive node, it is odd to have a negative node. Three or more juxtaposed numbers or clamp blocks can thereby be transformed into any order in nodes of the same sign.

Properties

Number

Through a list of possible separation trees the number separable permutations of given length can be determined. An unambiguous assignment of a separable permutation to a tree separation can be achieved by the additional condition that the right subtree of an internal node has a different sign than the node itself. Each separable permutations of length can now be generated from two separable permutations of smaller length by adding a new root node. If the root node denoted by, may be selected as the right subtree either the trivial permutation, for which there are opportunities, or a separable permutation of length with a negative root, for which there are options. As a left subtree can always be chosen with arbitrary root of a separable permutation of length, for which there are options. If the root node denoted by, is obtained again the same number of opportunities with the opposite sign. Overall, as for the number of separable permutations of length recursion

The numbers are (large ) called Schröder numbers and form the sequence

The generating function for the number of permutations is separable

Symmetries

The complementary to a permutation of length permutation and the corresponding reverse permutation caused by horizontal or vertical mirroring of the permutation matrix. If a permutation is separable, then so are their complementary and their reverse permutation is separable. The inverse of a separable permutation is separable again, as their permutation matrix is merely mirrored at the diagonal.

Permutationsmuster

A permutation is separable if and only if it contains neither of those two permutations and as Permutationsmuster, so as Teilpermutation with this relative order of the elements. Each permutation can also be assigned a Permutationsgraph whose nodes correspond to the elements of the permutation and the edges the failure stands of permutation. Separable permutations are precisely those permutations whose Permutationsgraphen are co- graphs. Co - graphs are characterized in that they have no path of length four as induced subgraphs, which just corresponds to the two illegal Permutationsmustern.

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