Separable permutation

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 Avis & Newborn (1981), who showed that they are precisely the permutations which can be sorted by an arbitrary number of pop stacks in series. Shapiro & Stephens (1991) 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 Bose, Buss & Lubiw (1998).

Separable permutations are the permutation analogues of complement-reducible graphs and series-parallel posets.

References

• Avis, David; Newborn, Monroe (1981), "On pop-stacks in series", Utilitas Mathematica, 19: 129–140, MR 0624050.

• Bose, Prosenjit; Buss, Jonathan; Lubiw, Anna (1998), "Pattern matching for permutations", Information Processing Letters, 65: 277–283, doi:10.1016/S0020-0190(97)00209-3, MR 1620935.

• Shapiro, Louis; Stephens, Arthur B. (1991), "Bootstrap percolation, the Schröder numbers, and the N-kings problem", SIAM Journal on Discrete Mathematics, 4: 275–280, doi:10.1137/0404025, MR 1093199.