Separable permutation

A one-node tree represents the trivial permutation, a tree whose root node is positive represents the direct sum of permutations given by its two child subtrees, and a tree whose root node is negative represents the skew sum of the permutations given by its two child subtrees.

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 This result was proven for a class of permutation matrices equivalent to the separable permutations by 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 functions to these trees.

[5] Separable permutations first arose in the work of 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 in which any pop operation pops all items at once.

Shapiro & Stephens (1991) considered separable permutations again in their study of bootstrap percolation, a process in which an initial permutation matrix is modified by repeatedly changing to one any matrix coefficient that has two or more orthogonal neighbors equal to one.

The term "separable permutation" was introduced later by Bose, Buss & Lubiw (1998), who considered them for their algorithmic properties.

As with the cographs and separable permutations, the series-parallel partial orders may also be characterized by four-element forbidden suborders.